Мемоизация простыми словами: как ускорить рекурсию на Python

Коротко

Мемоизация — это запоминание результатов функции, чтобы не считать одно и то же дважды. Одна строка кода может превратить алгоритм за O(2ⁿ) в алгоритм за O(n).

Проблема на примере

Классическая рекурсивная реализация чисел Фибоначчи:

def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Код красивый и полностью соответствует определению. И катастрофически медленный. Посмотрим, почему.

Развернём вызов fib(5):

                    fib(5)
              /              \
         fib(4)              fib(3)
        /      \             /      \
   fib(3)     fib(2)     fib(2)    fib(1)
   /    \      /   \      /   \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
 /  \
fib(1) fib(0)

fib(3) считается дважды. fib(2) — трижды. fib(1) — пять раз. Дерево вызовов растёт экспоненциально, хотя различных значений всего n.

Для fib(40) это около 331 миллиона вызовов ради 41 уникального результата.

Решение: запоминаем посчитанное

def fib_memo(n: int, cache: dict[int, int] | None = None) -> int:
    if cache is None:
        cache = {}

    if n in cache:
        return cache[n]      # уже считали — берём готовое

    if n < 2:
        return n

    result = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    cache[n] = result        # запоминаем перед возвратом
    return result


print(fib_memo(100))
# 354224848179261915075

Теперь каждое значение вычисляется ровно один раз. Дерево вызовов схлопывается в линейную цепочку: O(2ⁿ) → O(n).

Обратите внимание на cache=None вместо cache={} в сигнатуре. Это важно: изменяемый объект по умолчанию в Python создаётся один раз при определении функции и переживает все вызовы. Такой кэш будет общим для разных вызовов, что здесь случайно сработает, но в общем случае приводит к трудноуловимым багам.

Готовое решение: lru_cache

В Python не нужно писать кэш руками — есть декоратор из стандартной библиотеки:

from functools import lru_cache


@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


print(fib(100))          # мгновенно
print(fib.cache_info())  # CacheInfo(hits=98, misses=101, ...)

Одна строка над функцией — и экспоненциальный алгоритм стал линейным. Исходный код при этом не изменился вообще.

maxsize=None означает неограниченный кэш. Если поставить число, лишние записи будут вытесняться по принципу LRU — реже всего используемые уходят первыми.

С Python 3.9 есть более короткий синоним для безлимитного варианта:

from functools import cache

@cache
def fib(n: int) -> int:
    ...

Метод cache_info() очень полезен при отладке: если hits близок к нулю, значит мемоизация не работает — обычно из-за того, что аргументы каждый раз разные.

То же на JavaScript

Встроенного декоратора нет, но обёртка пишется за пять строк:

function memoize(fn) {
  const cache = new Map();

  return function (...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);

    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

const fib = memoize((n) => (n < 2 ? n : fib(n - 1) + fib(n - 2)));

fib(100); // 354224848179261900

Важная деталь: рекурсивный вызов внутри должен идти через обёрнутую версию (fib), а не через исходную функцию. Иначе кэшируется только внешний вызов, а вся рекурсия внутри останется медленной. Это самая частая ошибка при ручной мемоизации.

Когда мемоизация работает

Не любую функцию можно кэшировать. Нужны два условия.

Функция должна быть чистой. Один и тот же вход всегда даёт один и тот же выход, и функция ничего не меняет снаружи. Кэшировать функцию, которая читает время, генерирует случайные числа или ходит в базу, — прямой путь к багам.

@lru_cache          # так делать нельзя
def get_user(user_id):
    return db.query(user_id)   # данные в базе меняются

Подзадачи должны повторяться. Если каждый вызов уникален, кэш только займёт память. Мемоизация помогает именно там, где дерево рекурсии содержит одинаковые ветви.

Подводные камни

Аргументы должны быть хешируемыми. lru_cache использует их как ключ словаря, поэтому список или словарь передать не получится:

@lru_cache
def process(items):
    ...

process([1, 2, 3])   # TypeError: unhashable type: 'list'
process((1, 2, 3))   # работает — кортеж хешируемый

Кэш растёт неограниченно. При maxsize=None записи копятся всё время работы программы. Для долгоживущих процессов ставьте разумный лимит.

Кэш на методах держит объект в памяти. lru_cache на методе класса запоминает self как часть ключа, и объект не соберётся сборщиком мусора, пока запись в кэше. Для свойств лучше использовать functools.cached_property.

Глубина рекурсии никуда не девается. Мемоизация убирает лишние вычисления, но не уменьшает глубину стека. fib(10000) всё равно упадёт с RecursionError. Лечится либо sys.setrecursionlimit, либо переходом к итеративной версии.

Мемоизация и динамическое программирование

Это две стороны одной медали.

Мемоизация — подход «сверху вниз». Пишем естественную рекурсию и добавляем кэш. Считаются только реально нужные подзадачи.

Табличное ДП — подход «снизу вверх». Заполняем массив от базовых случаев к ответу, без рекурсии.

def fib_table(n: int) -> int:
    if n < 2:
        return n

    prev, curr = 0, 1
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

Практический совет: начинайте с мемоизации — она пишется быстрее и меньше шансов ошибиться. Если упрётесь в глубину стека или память, переписывайте в таблицу.

Что запомнить

• Мемоизация запоминает результаты, чтобы не пересчитывать одинаковые подзадачи.
• Превращает экспоненциальную рекурсию в линейную, часто одной строкой.
• В Python используйте @lru_cache или @cache из functools.
• Работает только для чистых функций с повторяющимися подзадачами.
• Аргументы должны быть хешируемыми — списки не подойдут, кортежи да.
• Глубину рекурсии мемоизация не уменьшает.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→