Что такое рекурсия

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

Пример рекурсивной функции для вычисления факториала:

def factorial(n):
    if n == 0:  # базовый случай
        return 1
    return n * factorial(n - 1)  # рекурсивный случай

Ключевые моменты:

1. Базовый случай — условие выхода из рекурсии (без него будет бесконечная рекурсия и переполнение стека).
2. Рекурсивный случай — вызов функции с изменёнными аргументами, приближающими к базовому случаю.

Осторожно: Рекурсия может быть менее эффективной по памяти, чем итеративные решения, из-за накопления вызовов в стеке. В Python глубина рекурсии ограничена (обычно ~1000). Для глубокой рекурсии лучше использовать итерации или хвостовую рекурсию (которую Python не оптимизирует).