Как рекурсия использует стек вызовов и чем опасна глубокая рекурсия?

Каждый рекурсивный вызов кладёт на стек новый фрейм с локальными переменными и адресом возврата; при слишком глубокой рекурсии стек переполняется — stack overflow.

Что происходит при вызове

• Фрейм хранит параметры, локальные переменные и точку возврата.
• Потребление памяти — O(глубина): наивный факториал за n вызовов ест O(n) стека.

Как бороться с переполнением

• Переписать итеративно с явным стеком на куче.
• Хвостовая рекурсия: если вызов — последнее действие функции, некоторые языки переиспользуют фрейм (в Python её нет; в JS она есть в спецификации ES2015, но реализована только в Safari).
• Увеличение лимита стека — костыль, а не решение.

Когда рекурсия оправдана

Задачи с естественной рекурсивной структурой: обход деревьев, divide and conquer, backtracking — итеративная версия вышла бы заметно сложнее и подверженнее ошибкам.

Коротко для собеседования

Каждый вызов занимает фрейм на стеке, так что рекурсия стоит O(глубины) памяти, а стек ограничен примерно мегабайтом на поток. Для глубоких структур переписывайте рекурсию на цикл с явным стеком — в Python хвостовой оптимизации нет, а в JS она работает только в Safari.