Fibonacci + Memoization

The same recursive Fibonacci, but every result is cached the first time it is computed. The exponential call tree collapses to a straight line — O(2ⁿ) becomes O(n).

Category: Dynamic Programming
Time complexity: O(n)
Space complexity: O(n)

Pseudocode

if n ≤ 1: return n
if n in cache: return cache[n]
compute fib(n−1) + fib(n−2)
cache and return

Reference implementation

cache = {}
def fib(n):
    if n &lt;= 1: return n
    if n in cache: return cache[n]
    cache[n] = fib(n-1) + fib(n-2)
    return cache[n]

Open the interactive Fibonacci + Memoization visualisation →