Fibonacci with memoisation

Easy TimeO(n) SpaceO(n)

Return the nth Fibonacci number, counting from 0, with each result stored the first time it is worked out and read back afterwards, so every distinct subproblem is computed at most once. The shape of the recursion is unchanged; only the repeated work goes.

Examples

Example 1

Input
n = 12memo = {}
Output
144
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 — position 12 counting from 0.

Example 2

Input
n = 0memo = {}
Output
0
Counting starts at 0, and position 0 holds 0 rather than 1.

The Code

function fibMemo(n, memo) {
  if (memo[n] !== undefined) return memo[n];
  if (n <= 1) return n;
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo[n] = result;
  return result;
}
fibMemo(12, {});
Done

The first 17 calls, of 23. This one does not fit on a page.

Step through fibMemo(12, {}) call by call

More like this

All dynamic programming examples (20) →