Рекурсия для чайников: Как функция вызывает саму себя и почему это не бесконечный ад
Вы когда-нибудь смотрели в зеркало, которое стоит напротив другого зеркала? Там бесконечная глубина - отражение отражения отражения. Вот это и есть рекурсия.
Только в программировании мы обычно не хотим бесконечности (иначе сервер упадет). Мы хотим, чтобы функция углублялась ровно столько раз, сколько нужно, а потом аккуратно возвращалась обратно - как матрешка, которая раскрывается до последней куклы, а затем собирается снова.
Рекурсия на пальцах: Правило трёх вопросов
Прежде чем писать код, ответьте себе на три вопроса (они спасут от stack overflow):
- Базовый случай - когда мы останавливаемся? (Самая маленькая матрешка, которую больше не раскрыть).
- Рекурсивный случай - как мы сводим большую задачу к точно такой же, но меньшей?
- Движение к базе - каждый шаг действительно уменьшает проблему? (иначе бесконечность).
Если эти три пункта есть - рекурсия безопасна. Если нет - вы сделаете RecursionError: maximum recursion depth exceeded.
Пример №1: Факториал - классика жанра (идеально для новичка)
Факториал числа 5 (5!) = 5 × 4 × 3 × 2 × 1 = 120.
Итеративно (циклом):
python
def factorial_iter(n):
result = 1
for i in range(2, n+1):
result *= i
return result
Рекурсивно (красиво, как формула из учебника):
python
def factorial_rec(n):
if n <= 1: # Базовый случай: 1! = 1, 0! = 1
return 1
return n * factorial_rec(n - 1) # Рекурсивный случай
Как это работает под капотом (по шагам) для factorial_rec(5):
- Вы зовете factorial_rec(5): n=5 → не базовый, надо вернуть 5 * factorial_rec(4).
- factorial_rec(4) → 4 * factorial_rec(3).
- factorial_rec(3) → 3 * factorial_rec(2).
- factorial_rec(2) → 2 * factorial_rec(1).
- factorial_rec(1) → Базовый случай! Вернуть 1. 🛑 Дно достигнуто.
Теперь идем обратно (раскручиваем стек):
6. factorial_rec(2) получает 2 * 1 = 2.
7. factorial_rec(3) получает 3 * 2 = 6.
8. factorial_rec(4) получает 4 * 6 = 24.
9. factorial_rec(5) получает 5 * 24 = 120.
Вуаля. Матрешка собралась.
Пример №2: Дерево папок - где рекурсия незаменима
Представьте, что у вас есть папка. Внутри - другие папки и файлы. Внутри тех - еще папки. Глубина неизвестна заранее. Как вывести все пути ко всем файлам?
Циклом это сделать практически невозможно (потребуется поддерживать свой собственный бесконечный список и вложенные циклы). А рекурсия справится легко:
python
import os
def scan_folder(path):
# Пытаемся перебрать содержимое папки
for item in os.listdir(path):
full_path = os.path.join(path, item)
if os.path.isfile(full_path):
print(f"Файл: {full_path}")
else:
print(f"Вход в папку: {full_path}")
scan_folder(full_path) # 🔁 Рекурсивный вызов
print(f"Выход из папки: {full_path}")
Проход по вашему диску С:
Сначала функция заходит в C:/, видит папку Users - заходит в нее. В Users видит John - заходит. В John видит Desktop - заходит. Находит там файл todo.txt - печатает. Потом возвращается в John и продолжает. Глубина может быть любой, и код не разбухает. Это и есть красота рекурсии.
Главная боль рекурсии: Стек вызовов
Каждый раз, когда функция вызывает саму себя до того, как завершилась предыдущая, компьютер кладет «закладку» (адрес возврата и локальные переменные) в стек вызовов.
Стек - это как стопка тарелок. Вы кладете тарелку на тарелку (глубокий рекурсивный спуск). Потом снимаете по одной (возврат).
Проблема: Стек не резиновый. В Python по умолчанию нельзя глубже 1000 вызовов. Если написать рекурсивную функцию, которая не движется к базовому случаю (или база слишком далеко) - программа крашится с ошибкой переполнения стека.
Пример смертельной ошибки (не повторять):
python
def oops():
return oops() # Базового случая нет! Бесконечность...
oops() # RecursionError
Когда рекурсию можно (и нужно) использовать?
Хаки и лайфхаки
1. Хвостовая рекурсия
Некоторые языки (Haskell, Scala, JS с оптимизацией) умеют превращать рекурсию в цикл, если рекурсивный вызов - самое последнее действие в функции. Python не умеет, так что в Python рекурсия - красивая, но медленная игрушка для небольших глубин.
Пример хвостовой рекурсии (если бы Python её оптимизировал):
python
def factorial_tail(n, accumulator=1):
if n <= 1:
return accumulator
return factorial_tail(n-1, n * accumulator) # Вызов в конце
2. Рекурсия + кэш (мемоизация)
Если вы считаете числа Фибоначчи наивной рекурсией (fib(n) = fib(n-1)+fib(n-2)), то получите O(2^n) и ужас. Но если добавить словарик с запомненными значениями - станет O(n):
python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_good(n):
if n <= 1:
return n
return fib_good(n-1) + fib_good(n-2)
Главный вывод, который останется с вами навсегда
Рекурсия - это не «про скорость». Рекурсия - это «про ясность» для вложенных структур.
Вы никогда не будете писать рекурсию, чтобы перебрать массив из 10 элементов. Вы будете писать её, когда задача сама по себе рекурсивна: папки, деревья, графы, парсинг JSON.
И всегда, всегда начинайте с базового случая. Как в анекдоте про программиста: «Чтобы понять рекурсию, нужно сначала понять рекурсию». Но шутка смешная только до первого RecursionError.