Фибоначчи: рекурсия
Дерево вызовов fib(n): наивная рекурсия пересчитывает одно и то же экспоненциально много раз.
1function fib(n: number): number {2 if (n <= 1) return n3 return fib(n - 1) + fib(n - 2)4}5 6// с мемоизацией — каждый считается один раз7function fibMemo(n: number, memo: Map<number, number>): number {8 if (n <= 1) return n9 if (memo.has(n)) return memo.get(n)!10 11 const value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo)12 memo.set(n, value)13 return value14}Проблема
Дерево вызовов fib(n): наивная рекурсия пересчитывает одно и то же экспоненциально много раз.
Что вы видите
Дерево растёт на глазах: одинаковые подзадачи появляются снова и снова — мемоизация оставила бы по одной.
Как это работает
fib(n) = fib(n−1) + fib(n−2) порождает перекрывающиеся подзадачи: fib(2) в дереве fib(5) встречается трижды. Кэш превращает O(2ⁿ) в O(n) — главная проповедь всей динамики.
Пошаговый разбор
- 01
Разбиение
Задача делится на две меньшие.
- 02
Перекрытие
Подзадачи повторяются.
- 03
Мемоизация
Каждая подзадача — один раз.
Complexity и ограничения
Сложность см. в шапке страницы.
Edge cases
- Пустой вход
Корректная тривиальная обработка.
- Вырожденный случай
Минимум работы — сразу ответ.
Где встречается в реальности
Введение в DP
Классическая демонстрация мемоизации.
Финансы
Рекуррентные соотношения в моделях.
Код-ревью
Понимание, когда рекурсия с кэшем спасает.
Связанные алгоритмы
«Почему рекурсия тормозит: дерево фибоначчи»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.