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)fib(n) is exponentially slow (it recomputes the same values)
• how memoization collapses that tree

Naive Fibonacci

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

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)fib(n) spawns two more calls. Draw that out and you get a tree — and the same sub-problems (fib(2)fib(2), fib(3)fib(3)) show up over and over:

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

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

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

Try it: Recursion Exercises

Exercise 1 – Factorial

Exercise 2 – Recursive sum

Exercise 3 – Countdown