Recursion

Foundation drill for this topic

Drill #47 — Fibonacci (memoized)

Easy Base + Memo

In plain English: Compute the nth Fibonacci number without redundantly recalculating the same sub-values.

Naive recursion recomputes fib(k) exponentially many times — memoization stores each result once, collapsing O(2^n) to O(n).

Prompt

Compute the nth Fibonacci number efficiently.

Try to write it from scratch before scrolling down.

Solution

# Recursive + memo
def fib(n, memo={}):
    if n &lt;= 1:
        return n
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)  # store to avoid recomputation
    return memo[n]

# Iterative (O(1) space)
def fib_iter(n):
    if n &lt;= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Test: fib(10) == 55

O(n) time · O(n) space (memo) / O(1) space (iter)

Related Micro Drills

Quick recall drills to reinforce this pattern.

80 Fibonacci iterative Divide & Conquer 10s

Iterative Fibonacci is O(n) time, O(1) space. Classic DP introduction pattern.

a, b = 0, 1
for _ in range(n):
    a, b = b, a + b
# a is fib(n)

See all drills in Recursion →