Выбор задачи
Стек вызовов и текущая глубина
Глубина
0
Макс. глубина
0
Шагов
0
Результат
—
Исходный код
Рекурсивная функция
Опасность переполнения стека. Каждый вызов функции добавляет в стек
параметры, локальные переменные и адрес возврата. Слишком глубокая рекурсия приводит к
аварийному завершению программы (stack overflow).
Задание
- Запустите факториал для n = 5, затем для n = 8. Во сколько раз выросла максимальная глубина?
- Сравните количество вызовов у Фибоначчи при наивной рекурсии и при использовании массива-мемоизации. Оцените сложность.
- Для Ханойских башен при n дисках: сколько шагов нужно сделать? Найдите формулу.
- Перепишите одну из рекурсивных функций итеративно, чтобы избежать переполнения стека.