Recursion

How Recursion works

Before you start

Stack
Each call waits on the call stack until the calls it made return. That lesson covers push and pop.
Open lesson

Why it matters

Recursive definitions appear in tree traversals, parsers, graph searches, and optimization code. They are compact enough to hide explosive repeated work: a function can return the right value while making millions of duplicate calls. Fibonacci isolates that risk before it reappears in larger problems. For inputs such as n = 30, the result must arrive without an exponentially growing call tree.

Example

Fibonacci Number

Compute the nth Fibonacci number. Write the recursive definition first — base cases F(0)=0 and F(1)=1, then trust F(n-1) and F(n-2). Memo is optional here.

Input: n = 5
Output: 5

Approach 1 · Brute force

Plain recursion

Same example

n = 5

Translate the definition directly. It is correct, but it recomputes the same values again and again, and the number of calls grows exponentially with n.

Time O(2ⁿ) · Space O(n)

Python

Fibonacci Number

1def fib(n):
2 if n <= 1:
3 return n
4 return fib(n - 1) + fib(n - 2)

Each node is one call, labeled with its n. fib(4) calls fib(3) and fib(2). Each of those makes two more calls, down to the base cases fib(1) and fib(0).

1 / 3

Approach 2 · Resolve the bottleneck

The idea

Keep one example in view

Fibonacci Number

n = 5→5

The baseline, Plain recursion, is O(2ⁿ) · O(n). The better model below keeps this exact input and removes that bottleneck.

For n = 5, plain recursion computes fib(3) from both fib(5) and fib(4). Store fib(0) through fib(5) as each returns, so repeated branches become lookups instead of rebuilding the brute call tree.

For n = 5, start with memo = {0: 0, 1: 1}. go(5) is missing, so it waits for go(4), which waits for go(3), until go(2) can read both base cases and store 1.

Returning upward fills memo[3] = 2, memo[4] = 3, and memo[5] = 5. When go(3), go(2), or go(1) is needed again, its stored value returns immediately. The call stack still handles the unfinished additions, but no k from 0 through 5 is solved twice.

Visual anchor

Fibonacci Number

fib(5)waiting
go(5)waiting
go(4)waiting
go(3)waiting
go(2)calling

go(2) gets go(1) = 1 and go(0) = 0 straight from the memo. Store memo[2] = 1 and return.

Run the same example

Walkthrough

1.Start memo with the base cases, 0 and 1.
2.go(k) computes go(k − 1) + go(k − 2) only if k is not in memo.
3.Store the result in memo[k] before returning it.
4.Return go(n).

Python

Fibonacci Number

Input:: n = 5
Output:: 5

1def fib(n):
2 memo = {0: 0, 1: 1}
3 def go(k):
4 if k not in memo:
5 memo[k] = go(k - 1) + go(k - 2)
6 return memo[k]
7 return go(n)

fib(5)calling

Seed the memo with the two base cases. Every other answer will be stored the first time it is computed.

1 / 9

Complexity

TimeO(n)

SpaceO(n)

Each value from 2 to n is computed once, with O(1) work besides its two calls, so time is O(n). The memo stores n + 1 values and the call stack reaches depth n, so space is O(n). Plain recursion makes about 2ⁿ calls.

Where this breaks

Memoization helps when the same arguments repeat. A walk over distinct nodes stores nothing it can reuse.

Brute force

Plain recursion

O(2ⁿ) time

O(n) space

This technique

Memoized recursion

O(n) time

O(n) space

177

22k

2.7M

n=10

n=20

n=30

Plain recursionMemoized recursion

Function calls on a log scale. Plain recursion multiplies by about 1.6 for every step in n.

Your turn

Fibonacci Number

Same problem, your code.

Solve Fibonacci Number

Then branch out

Same technique, different problems. Try them without the walkthrough.