Рекурсивная функция
Рекурсивная функция — это функция, которая во время выполнения вызывает саму себя, передавая задачу с изменёнными данными. Такие вызовы продолжаются, пока не будет достигнуто условие остановки.
Рекурсивная функция является частным случаем рекурсивного алгоритма: алгоритм может быть описан рекурсивно, а функция реализует такое описание в программе. При каждом вызове сохраняются текущие значения переменных и место возврата. После завершения вложенного вызова выполнение продолжается в предыдущем.
Схема рекурсии
В общей схеме \(b\) — результат базового случая, а \(G\) задаёт обработку результата предыдущего вызова. Важно, чтобы каждый следующий вызов приближал аргумент к базовому случаю. Иначе функция может вызывать себя бесконечно и завершится ошибкой переполнения стека.
Факториал можно определить так: \(0! = 1\), а \(n! = n\cdot(n-1)!\) при \(n>0\). Поэтому вызов factorial(3) образует цепочку \(3\cdot factorial(2)\), затем \(2\cdot factorial(1)\) и \(1\cdot factorial(0)\). После достижения базового случая результаты возвращаются обратно: \(1\), затем \(2\), затем \(6\).
Рекурсивная функция не обязана вызывать себя последним действием. Если вызов выполняется последним и после него уже нечего вычислять, это хвостовая рекурсия. Также не следует смешивать саму функцию с её возвращаемым значением: функция выполняет вызовы, а значение является результатом её работы.
Что обязательно должно быть в корректной рекурсивной функции?
Главное
- Рекурсивная функция вызывает саму себя для решения уменьшенной подзадачи.
- Корректная рекурсия содержит базовый случай и шаг, приближающий к нему.
- Результаты вложенных вызовов возвращаются в обратном порядке; глубина таких вызовов связана со стеком рекурсивных вызовов.