Почему рекурсия может переполнить стек
При каждом вызове функции программа должна запомнить, откуда продолжить работу после её завершения. Для этого она сохраняет данные вызова в специальной области памяти — стеке. Пока функция вызывает себя снова, предыдущие вызовы остаются там незавершёнными и ждут ответа.
Например, функция может считать число вниз: сначала обработать 5, затем вызвать себя для 4, потом для 3. Чтобы цепочка когда-нибудь закончилась, нужен базовый случай — условие, при котором функция перестаёт вызывать себя и возвращает результат. Здесь им может быть достижение нуля.
Важно не только условие, но и движение к нему
Одного условия выхода недостаточно: выполнение должно действительно до него доходить. Если функция каждый раз передаёт себе прежнее число или условие сформулировано неверно, цепочка не оборвётся. То же произойдёт, если условие выхода достижимо лишь для части входных данных, а для остальных — нет.
Когда стек заполняется, очередной вызов уже некуда сохранить. Среда выполнения сообщает о переполнении стека, а приложение обычно прекращает работу. Точный предел зависит от платформы и настроек, поэтому проблема может проявиться не сразу и меняться при запуске в другой среде.
Проверять рекурсию полезно на простом вопросе: каждый ли вызов приближает входные данные к условию выхода? Если цепочка может быть очень длинной, вместо рекурсии иногда используют цикл: он не сохраняет целый ряд незавершённых вызовов в стеке.
