Рекурсия — это когда функция вызывает сама себя для решения более простой версии той же задачи.
У любой рекурсивной функции должны быть два компонента: базовый случай (остановка) и рекурсивный случай (приближение к базовому).
Python хранит каждый вызов в стеке вызовов; при слишком глубокой рекурсии возникает RecursionError.
Хвостовая рекурсия в Python не оптимизируется, поэтому глубокие задачи лучше решать итеративно или с мемоизацией.
Топ-3 ошибки: забыть базовый случай; не приближать аргумент к базовому случаю; путать поверхностное и глубокое копирование вложенных структур.
О чём этот урок
Рекурсия — один из фундаментальных приёмов в программировании. Вместо того чтобы решать задачу целиком, функция решает маленький кусочек и передаёт остальное «себе же, но проще». Такой подход естественно описывает вложенные структуры, деревья, комбинаторные задачи и алгоритмы «разделяй и властвуй».
В уроке разберём, как устроена рекурсия в Python, почему важен базовый случай, как работает стек вызовов и когда рекурсию стоит заменить циклом.
Цели
Понимать разницу между базовым и рекурсивным случаем.