Что такое рекурсия и мемоизация?

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

• базовый случай — когда ответ известен без рекурсии;
• шаг — сведение к меньшей задаче, который гарантированно приближает к базовому случаю.

Каждый вызов кладёт кадр в стек вызовов (параметры, локальные переменные, адрес возврата). При слишком большой глубине стек переполняется: RecursionError в Python (лимит около 1000 по умолчанию), StackOverflowError в Java. Тогда рекурсию переписывают на цикл с явным стеком.

Проблема повторных вычислений. fib(n) = fib(n-1) + fib(n-2) порождает дерево вызовов, где fib(n-2) считается дважды, fib(n-3) — трижды и так далее: число вызовов растёт экспоненциально, примерно как 1,6ⁿ.

Мемоизация — запоминать результат для каждого аргумента и при повторном вызове брать из кэша. Дерево вызовов «схлопывается» в цепочку: O(n) времени и O(n) памяти. Это подход «сверху вниз» к динамическому программированию.

Хвостовая рекурсия — рекурсивный вызов последний в функции. Некоторые языки (Scheme, Scala с аннотацией) превращают её в цикл без роста стека; Python и Java так не делают.

from functools import lru_cache

def fib_slow(n):                     # O(2^n)
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)

@lru_cache(maxsize=None)
def fib_fast(n):                     # O(n): каждое значение — один раз
    return n if n < 2 else fib_fast(n - 1) + fib_fast(n - 2)

fib_fast(90)   # мгновенно; fib_slow(90) не дождаться