Рекурсия и стек вызовов: почему функция, что зовёт сама себя, может уронить программу

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

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

Представьте, что вы стоите в огромной очереди и хотите узнать, какой вы по счёту. Можно спросить переднего: «А ты какой?». Он не знает — и спрашивает своего переднего. И так до самого начала. Первый отвечает «я первый», передаёт назад, каждый прибавляет единицу — и ответ возвращается к вам. Вы только что выполнили рекурсию.

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

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

• Базовый случай — ситуация, когда задача настолько проста, что решается без дальнейших вызовов. Это дно, до которого спускается рекурсия. В очереди это первый человек: ему некого спрашивать.
• Шаг к базовому случаю — каждый рекурсивный вызов должен решать задачу меньше предыдущей, постепенно приближаясь ко дну.

def factorial(n):
    if n == 1:        # базовый случай
        return 1
    return n * factorial(n - 1)  # шаг поменьше

print(factorial(5))  # 120

Чтобы вычислить факториал 5, функция зовёт себя для 4, та — для 3, и так до 1. Достигнув дна, ответы начинают возвращаться обратно, перемножаясь по дороге: 1 → 2 → 6 → 24 → 120.

Где живут все эти вызовы

Вот ключевой момент. Пока factorial(5) ждёт ответа от factorial(4), она не завершилась — она приостановлена, и её состояние нужно где-то хранить. Это место — стек вызовов. Каждый вызов кладёт на стек свой кадр: локальные переменные и точку, куда вернуть результат.

В пике нашего примера на стеке лежат сразу пять кадров: factorial(5), (4), (3), (2), (1). Как только самый верхний возвращает значение, его кадр снимается, и стек постепенно «схлопывается» обратно.

Откуда берётся переполнение

Стек — не бесконечный. Операционная система выделяет под него ограниченную область, обычно несколько мегабайт. Каждый кадр занимает место. Если рекурсия слишком глубокая — или, что хуже, забыли базовый случай и она бесконечна — кадры копятся, пока не упрутся в границу.

В этот момент программа падает с ошибкой переполнения стека (stack overflow). В Python вы увидите RecursionError: maximum recursion depth exceeded — язык специально ставит мягкий предел (обычно около тысячи вызовов), чтобы поймать ошибку раньше, чем рухнет вся память. В C или C++ предохранителя нет — программа просто аварийно завершится.

Классическая ошибка

def countdown(n):
    print(n)
    countdown(n - 1)   # нет базового случая!

countdown(5)   # 5, 4, 3, 2, 1, 0, -1, -2... до краха

Здесь нет условия остановки, поэтому функция уходит в минус бесконечность — и стек переполняется. Достаточно добавить if n < 0: return, и всё встанет на место.

Рекурсия против цикла

Многое из того, что делает рекурсия, можно записать обычным циклом — и цикл не нагружает стек. Зачем же рекурсия? Потому что некоторые задачи по своей природе рекурсивны, и решать их циклом мучительно. Обход дерева папок, разбор вложенных выражений, алгоритмы вроде быстрой сортировки — здесь рекурсия выражает мысль естественно и коротко.

Правило простое: если глубина вложенности невелика и предсказуема — рекурсия читается элегантно. Если она может оказаться огромной (миллионы шагов) — лучше цикл, иначе рискуете переполнить стек.

Что унести с собой

Рекурсия красива, но не бесплатна: за каждый виток вы платите кадром на стеке. Помните про два обязательных условия — базовый случай и движение к нему — и вы избежите бесконечного спуска. А увидев stack overflow, вы теперь точно знаете, что произошло: стопка отложенных вызовов выросла выше отведённого ей потолка.