Drag across the tree. Click it, then use ← → to step and Space to play.
A function that calls itself, one frame at a time. A recursive call goes down until it hits a base case, then comes back up, handing each answer to the call that was waiting for it. Every waiting call keeps a frame on the stack, so the pile of trays is always the red path through the tree of calls.
FIG. 3 · The call stack drawn as a pile of trays, beside the tree of every call the function makes; each disc in the tree is one call, marked with its n. Each tray is one frame: the expression it is working on, with an empty hole where the answer of the call it is waiting on will land. Calls not made yet are dotted outlines; a value climbs back up a groove when a call returns. Callouts: A running frame, B waiting frame and its hole, C base case, D repeated work or the memo.
def factorial(n):
if n <= 1: # 1. base case: stop
return 1
return n * factorial(n - 1) # 2. smaller input, 3. combine
def fib(n): # two branch, no memo
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
def fib(n, memo=None): # two branch + memoization
if memo is None:
memo = {}
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
def climbStairs(n, memo=None): # LeetCode 70
if memo is None:
memo = {}
if n <= 2: # 1 way to climb 1 step, 2 ways to climb 2
return n
if n in memo:
return memo[n]
memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
return memo[n]
def myPow(x, n): # LeetCode 50, here x = 2
if n == 0: # base case
return 1
half = myPow(x, n // 2) # one call on half the input
if n % 2 == 0:
return half * half
return half * half * x
You climb 1 or 2 steps at a time. The ways to reach step n are the ways to reach n − 1 plus the ways to reach n − 2: the same tree as Fibonacci, so memoize it. Trigger: "how many ways", "nth step".
Instead of multiplying x by itself n times, square the answer for n // 2. Every call halves n, so the stack is only about log n deep: O(log n) time and space instead of O(n).
Time is the number of calls times the work in each. Space is the deepest the call stack ever gets, because every waiting call keeps its frame. The last column fills in when a run on the bench finishes.
| Function | Time | Space | Why | Last run on the bench |
|---|---|---|---|---|
| Factorial | O(n) | O(n) | One call per step, n calls in a single chain. All n frames are on the stack at the deepest point. | not run yet |
| Fibonacci, plain | O(2ⁿ) | O(n) | Every call makes two more, so the tree roughly doubles each level and the same subproblems are solved again and again. The stack is still only as deep as the longest path, n. | not run yet |
| Fibonacci, memoized | O(n) | O(n) | Each fib(k) is computed once and stored. Every later call for k returns from the dictionary, which cuts off its whole subtree. The memo itself adds O(n) space. | not run yet |
| n | Plain calls | Memoized calls | Plain ÷ memo |
|---|
A call cannot finish until the call it made returns, so every unfinished call keeps a frame on the stack. Factorial(n) holds n frames at its deepest point. Plain Fibonacci makes exponentially many calls, but only one path is open at a time, so its stack is also n deep. Python stops at about 1,000 frames by default (RecursionError), which is why very deep recursion is often rewritten as a loop.
Find the base case, make the input smaller, combine the answers.
If the call tree computes the same input more than once, store each answer the first time.
def factorial(n):
if n <= 1: # 1. base case: stop
return 1
return n * factorial(n - 1) # 2. smaller input, 3. combine
def fib(n, memo=None): # two branch + memoization
if memo is None:
memo = {}
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]