Резюме

В этой теме вы узнали, что такое рекурсия. Какие преимущества и недостатки в её использовании.

Чтобы решить задачу рекурсивным методом, нужно определить базовый и рекурсивный случаи. Базовый случай — ситуация, при которой нужно завершить рекурсию. Рекурсивный — произвести рекурсивный вызов функции с другими параметрами.

Ошибка, которую часто допускают, применяя рекурсию, — запуск бесконечного цикла. Обычно это происходит, если забыть указать базовый случай или неверно обозначить изменение параметров в рекурсивном случае.

С помощью рекурсии иногда удобно реализовывать алгоритмы. Код получается простым, кратким и понятным. Рекурсия экономит время программиста.

Однако при работе рекурсивных программ может использоваться большой объём стека вызовов. Иногда он даже переполняется.

Есть особый тип рекурсии — хвостовая. Так называют рекурсию, в которой любой рекурсивный вызов — последняя операция перед возвратом из функции. Некоторые компиляторы оптимизируют код, в котором есть рекурсивно хвостовые функции, заменяя такую рекурсию на итерацию.

Вы познакомились с принципом «разделяй и властвуй». Этот приём широко применяют в алгоритмах. Суть метода заключается в рекурсивном разбиении задачи на подзадачи меньшего размера и комбинировании их решений для получения ответа к исходной задаче. Вы ещё встретитесь с этим методом при изучении сортировок.

Также вы узнали, что такое Основная теорема рекурсии. Она помогает узнать сложность рекурсивного алгоритма. Для этого нужно знать количество подзадач, на которые разбивается задача, во сколько раз уменьшается размер подзадачи на каждом шаге и сложность консолидации.

Также вы разобрались, как вычислять факториал, числа Фибоначчи и количество сочетаний. Познакомились с алгоритмом Евклида.

Тем временем ребята почти дошли до Удотинска, где их ждёт Кондратий. А по пути Тимофей рассказал друзьям много интересных и полезных алгоритмов.