Без условия остановки рекурсия заполняет стек вызовами

Что именно программа хранит при рекурсивном вызове

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

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

Зачем нужно условие остановки

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

Если проверка отсутствует или задана неверно, цепочка не начинает обратный ход. Функция снова и снова создаёт новый вызов, а прежние остаются незавершёнными. Так происходит, например, если функция каждый раз передаёт себе то же значение. Рано или поздно для очередного кадра может не хватить доступной памяти, и программа получит ошибку переполнения стека или завершится аварийно.

Почему ошибка может скрываться

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

Для задач с очень длинной последовательностью вызовов иногда используют цикл: он повторяет действие, не создавая отдельный кадр функции на каждом шаге. А отладчик, показывающий цепочку вызовов, помогает увидеть, какие функции продолжают ждать завершения своих вложенных копий.