Recursion

No. 03 · SVG · Nested traysone branch · two branch · call stack · memoization

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.

Input n = 4
READY
Call stackdepth 0
Call tree
Step 1 / 1
Calls made
Stack depth
Repeated calls
Result
Codefactorial
def factorial(n):
    if n <= 1:                     # 1. base case: stop
        return 1
    return n * factorial(n - 1)    # 2. smaller input, 3. combine

Examples

Two branch + memo · LeetCode 70

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".

O(n) timeO(n) spaceeach step count is solved once (O(2ⁿ) without memo); memo plus a stack up to n deep
One branch, halving · LeetCode 50

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).

O(log n) timeO(log n) spacen halves on every call; the stack holds about log₂ n frames

Time and space: what recursion costs

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.

FunctionTimeSpaceWhyLast run on the bench
FactorialO(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, plainO(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, memoizedO(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

How many calls fib(n) makes

nPlain callsMemoized callsPlain ÷ memo

Why the stack is the space cost

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.

Trigger words: when the problem wants recursion

Recursion

  • defined in terms of a smaller version
  • nth term
  • tree
  • try every way

Find the base case, make the input smaller, combine the answers.

Memoization

  • repeated subproblems

If the call tree computes the same input more than once, store each answer the first time.

Template

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]