Рекурсия

Рекурсия — это вызов функцией самой себя в ходе своей работы. Сложная задача сводится к такой же, но меньшей задаче, и так продолжается, пока не будет достигнут простейший случай. В любой правильной рекурсивной функции есть две части: условие остановки (простейший случай, ответ на который даётся без рекурсии) и рекурсивный шаг (функция вызывает себя с меньшими данными).

Классический пример — факториал: n! = n · (n − 1)!, 0! = 1. На Python это записывается так: def f(n): return 1 if n == 0 else n * f(n - 1). При вызове f(3) вычисляется 3 * f(2), затем 2 * f(1), затем 1 * f(0); дойдя до f(0), ответы возвращаются в обратном порядке, и получается 6. Без условия остановки функция вызывала бы себя бесконечно.

Числа Фибоначчи тоже определяются рекурсивно: fib(n) = fib(n - 1) + fib(n - 2), fib(0) = 0, fib(1) = 1. Но при простой записи одни и те же значения вычисляются много раз, и с ростом n время растёт очень быстро; например, fib(40) таким способом считается заметно долго. В таких случаях эффективнее запоминать промежуточные результаты или использовать цикл.

Каждый рекурсивный вызов занимает место в памяти, поэтому слишком глубокая рекурсия приводит к переполнению. В Python глубина ограничена (обычно примерно 1000 вызовов), и при превышении возникает ошибка RecursionError. Рекурсия удобна для древовидных данных и алгоритмов «разделяй и властвуй», а для простого повторения цикл часто быстрее и безопаснее.

Главное

• Рекурсия — вызов функцией самой себя с меньшими данными.
• В рекурсии обязательны условие остановки и рекурсивный шаг.
• Без условия остановки рекурсия не завершится и возникнет ошибка.
• Простая рекурсивная запись чисел Фибоначчи медленна, так как значения вычисляются повторно.
• Глубина рекурсии в Python ограничена (около 1000).