Recursion Visualized

Recursion is a function that calls itself on a smaller version of the problem until it hits a base case. It’s elegant, but it’s easy to write a recursive function that does an astonishing amount of repeated work. The classic example is the Fibonacci sequence.

What you’ll learn

how a recursive call branches into a tree of sub-calls
why naive fib(n) is exponentially slow (it recomputes the same values)
how memoization collapses that tree

Naive Fibonacci

fib.py

def fib(n):
    if n < 2:          # base case
        return n
    return fib(n - 1) + fib(n - 2)   # two recursive calls
 
print(fib(5))   # 5

Each call to fib(n) spawns two more calls. Draw that out and you get a tree — and the same sub-problems (fib(2), fib(3)) show up over and over:

sketch The fib(5) call tree p5.js

Every call branches into two. Green leaves are base cases. Notice how fib(3) and fib(2) get recomputed many times.

Fifteen calls for fib(5); fib(30) makes over 2.6 million. The fix is memoization — cache each result so every sub-problem is computed once:

fib_memo.py

from functools import lru_cache
 
@lru_cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
 
print(fib(30))   # instant

Recursion Visualized

What you’ll learn

Naive Fibonacci

Try it: Recursion Exercises

Exercise 1 – Factorial

Exercise 2 – Recursive sum

Exercise 3 – Countdown

pch.feedbackHeading