---
title: "Рекурсия с мемоизацией"
url: https://algopath.pro/ru/patterns/memoization
language: ru
summary: "Рекурсия, которая записывает каждый посчитанный ответ. Когда тот же аргумент приходит снова, отдаётся сохранённое значение."
updated: 2026-08-24
---

# Рекурсия с мемоизацией

Рекурсия, которая записывает каждый посчитанный ответ. Когда тот же аргумент приходит снова, отдаётся сохранённое значение.

## Рекурсия с мемоизацией: как это работает?

Сначала напишите обычную рекурсию. Добейтесь правильности до попыток ускорить.

Посмотрите, что на самом деле является аргументами. Если два вызова их делят, ответ у них общий.

Добавьте кеш с ключом по этим аргументам. Подойдёт и словарь, и обычный массив.

В начале функции возвращайте сохранённый ответ, если он есть. Дальше ничего не выполняется.

Перед возвратом сохраните ответ под его ключом. Следующий вызов прочитает его вместо пересчёта.

Теперь каждый различный аргумент считается один раз. Дерево вызовов схлопывается в граф.

- `fib(5) требует fib(4) и fib(3)` Наивная версия расходится на два вызова.
- `fib(4) требует fib(3) и fib(2)` Теперь fib(3) нужен уже дважды.
- `кеш = {2: 1, 3: 2}` Первый fib(3) посчитан и сохранён.
- `fib(3) это чтение из кеша` Второй fib(3) читает кеш. Всё его поддерево пропущено.
- `15 вызовов стали 9` Без кеша fib(50) занял бы миллиарды вызовов.

## Рекурсия с мемоизацией: когда применять?

- рекурсивные вызовы повторяют одни и те же аргументы (пересекающиеся подзадачи)
- обычная рекурсия работает верно, но слишком медленно / экспоненциальный взрыв
- мало различных состояний, хотя дерево рекурсии огромное
- закешировать результат (i, ...) перед возвратом
- формулировка вроде Фибоначчи / подъём по лестнице / путь по сетке с намёком на кеш

## Рекурсия с мемоизацией: с чем путают?

- **Рекурсия** - Обычная рекурсия каждый раз пересчитывает повторный аргумент. Кеш это вся разница.
- **Динамическое программирование (1-D)** - Динамика снизу заполняет таблицу в заданном порядке. Здесь она заполняется по требованию, сверху.
- **Хеш-множество / словарь** - Кешем обычно служит словарь. Эта страница про то, когда его вообще заводить.
- **Бэктрекинг** - Бэктрекинг обходит пути, которые все разные, поэтому ничего не повторяется. Кеш там хранит ключи, которых больше не спросят.

## Рекурсия с мемоизацией: сложность по времени и памяти

Стоимость это число различных аргументов на работу одного вызова. Кеш в 1e6 ключей нормален.

## Рекурсия с мемоизацией: разбор примера

### Наименьшее число монет на сумму

Даны номиналы монет и сумма. Верните наименьшее число монет, дающее эту сумму.

Если набрать сумму нельзя, верните минус один.

Задайте тот же вопрос про меньшую сумму. Каждая монета даёт одну ветку.

Подзадачу определяет только остаток суммы. Значит по нему и делается ключ кеша.

```javascript
function coinChange(coins, amount) {
    const cache = new Map();

    function best(left) {
        if (left === 0) return 0;
        if (left < 0) return Infinity;
        if (cache.has(left)) return cache.get(left); // computed before

        let answer = Infinity;
        for (const coin of coins) {
            answer = Math.min(answer, best(left - coin) + 1);
        }

        cache.set(left, answer); // store the failure too
        return answer;
    }

    const result = best(amount);
    return result === Infinity ? -1 : result;
}
```

## Рекурсия с мемоизацией: частые ошибки

- **В ключ не попал один из аргументов** В ключ входит всё, от чего зависит ответ. Неполный ключ вернёт ответ другого вызова.
- **Кешируют изменяемый объект** Сохранённую ссылку может испортить более поздний вызов. Храните копию или простое значение.
- **Не кешируют неудачу** Провалившаяся ветка это тоже ответ, который стоит сохранить. Иначе тупики обходятся заново.
- **Кешируют там, где ничего не повторяется** Если все аргументы разные, кеш только тратит память. Сначала проверьте пересечение подзадач.

## Рекурсия с мемоизацией: задачи с собеседований

- **Числа Фибоначчи** Кратчайший пример пересекающихся подзадач.
- **Подъём по лестнице** Та же форма с другим базовым случаем.
- **Размен монет** Ключ это оставшаяся сумма.
- **Ограбление домов** Ключ это индекс, на котором вы стоите.
- **Разбиение строки на слова** Ключ это позиция начала в строке.
- **Число путей в сетке** Ключ это пара координат.
- **Самый длинный возрастающий путь в матрице** Ключ это клетка, и множество посещённых не нужно.

## JavaScript

```javascript
function fib(n, memo = new Map()) {
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n);
    const result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.set(n, result);
    return result;
}
```

## Python

```python
def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]
```

## PHP

```php
function fib(int $n, array &$memo = []): int {
    if ($n <= 1) return $n;
    if (isset($memo[$n])) return $memo[$n];
    return $memo[$n] = fib($n - 1, $memo) + fib($n - 2, $memo);
}
```