Как добавить кэш, чтобы ускорить рекурсивный Фибоначчи?

Question

Accepted Answer

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

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

Или top-down с замыканием / bottom-up массив O(n).

Без кэша дерево вызовов экспоненциально; с кэшем — O(n) различных состояний.

## Итог

Кэш по `n` превращает наивный fib в линейный по числу уникальных подзадач.