Basic

The call stack

Each call waits for the one below it to finish. Those waiting calls stack up, which is why recursion has a depth limit and can overflow.

What you will see

5000

About 2 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Observe the call stack of a recursion.

Depth of 3.

def depth(n): if n == 0: return 0 return 1 + depth(n - 1) print(depth(3))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Peak frames for 4.

def d(n): if n <= 0: return 0 return 1 + d(n - 1) print(d(4))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Fib of 4.

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

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Raise the limit.

import sys sys.setrecursionlimit(5000) print(sys.getrecursionlimit())

Before you run it, say out loud what it will print. Then open the answer.

What it prints

5000

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

Each recursive call waits for the one below it, so frames stack up. The peak depth is the most frames open at once and can overflow.

1 open a frame

↓

2 wait for the call below

↓

3 base returns

↓

4 frames unwind

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

def depth(n): sets nothing on screen

if n == 0: sets nothing on screen

return 0 sets nothing on screen

return 1 + depth(n - 1) sets nothing on screen

print(depth(3)) 3

Why this works

Frames are the cost

Recursion uses memory for every open call. The peak depth is the most frames held at once, and that is what can overflow.

Longest path sets depth

When a frame makes two calls, the stack depth follows the longest chain, not the total number of calls.

Examples

Frames stack up

def depth(n):
    if n == 0:
        return 0
    return 1 + depth(n - 1)
print(depth(3))

Four frames are open at once before the base returns. Each waits for the next.

One waits for the next

def f(n):
    if n == 0:
        return 0
    return f(n - 1)
print(f(2))

f(2) cannot finish until f(1) finishes, which waits on f(0). The calls nest like cups.

Unwind on return

def g(n):
    if n == 0:
        return 0
    return g(n - 1)
print(g(3))

When the base returns, frames close one by one from the inside out. That is the unwind.

Deep call overflows

def f(n):
    if n == 0:
        return 0
    return f(n - 1)
print(f(5))

A very large n opens too many frames and the program crashes. The stack has a fixed size.

Tail calls still stack

def t(n):
    if n == 0:
        return 0
    return t(n - 1)
print(t(3))

Python does not reuse the tail frame, so even tail recursion stacks up. Some languages do not.

Depth is the peak frames

def d(n):
    if n <= 0:
        return 0
    return 1 + d(n - 1)
print(d(4))

The deepest point equals the starting n. That peak is the most frames open at once.

Two calls per frame

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

Each frame can wait on two calls. The stack grows along the longest path, not the count.

Limit is adjustable

import sys
sys.setrecursionlimit(5000)
print(sys.getrecursionlimit())

You can raise the cap, but very deep recursion can still crash the program.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Recursion versus a loop

Previous Lesson

Recursion versus a loop

Next Lesson

Recursion on nested data

Recursion on nested data →