Recursion & the Call Stack

Trees, divide-and-conquer sorting, backtracking and DFS are all recursion. Once you can picture the call stack, these algorithms stop feeling like magic.

beginner⏱ 12 min read

←Builds on

0Big-O & Growth RatesCounting the calls in a recursion tree is how you price a recursive function.

Leads to→

2Merge Sort: Divide & ConquerMerge sort calls itself on each half and merges on the way back up.3Stack (LIFO) & Expression EvaluationThe call stack is a stack: recursion is LIFO in disguise.4Generating Subsets & PermutationsGenerating subsets is recursion that branches twice: take the element or skip it.5Trees: Concepts, Properties, TraversalsEvery tree traversal is the same function called recursively on each child.6Depth-First Search (DFS)Recursive DFS lets the call stack remember the way back.9GCD & the Sieve of Eratosthenesgcd(a, b) = gcd(b, a mod b) is a one-line recursion.9Fast Exponentiation & Modular Arithmeticaⁿ = (a^(n/2))² is a recursion that halves n on each call.10DP Fundamentals: Memo & TableMemoization is a recursive function that writes its answers down.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01A smaller copy of the same problem

A recursive function solves a problem by calling itself on a smaller input. Every recursive function has two parts:

Base case: an input so small the answer is known directly. fact(1) = 1.
Recursive case: reduce the problem and combine. fact(n) = n × fact(n−1).

Think of it like nested boxes: fact(4) contains a call to fact(3), which contains fact(2), down to fact(1), which answers immediately. Then the answers travel back out: 1, 2, 6, 24.

The trick is to trust the smaller call. When you write n × fact(n−1), assume fact(n−1) already works and only ask: does my step turn its answer into mine?

02What the computer actually does: the call stack

Each call gets its own frame: its own copy of n and a note of where to continue. Frames live on the call stack.

A call pushes a new frame on top. The caller pauses and waits.
A return pops the top frame and hands its value to the frame below, which resumes.

While computing fact(4), the stack grows to four frames. Only the top one is running; the others are all waiting for an answer. Then it shrinks back, one return at a time.

This is a real stack, last in first out. That is why recursion and an explicit stack are interchangeable: any recursive function can be rewritten with a loop and a stack, and DFS is exactly that.

03The cost: depth and the recursion tree

Two numbers describe a recursive function:

Depth: the tallest the stack gets. fact(n) has depth n, so it uses O(n) memory.
Total calls: draw every call as a node of a recursion tree. Time is the sum of the work in all nodes.

fact makes one call per level, so the tree is a chain: O(n) time. But fib(n) = fib(n−1) + fib(n−2) makes two calls, and its tree explodes. fib(5) already computes fib(3) twice and fib(2) three times; fib(n) takes about O(2ⁿ) time.

The fix is to remember answers you have already computed (memoization). That single idea is the doorway to dynamic programming.

Pink and violet nodes are repeated subproblems.

04Pitfalls and when to use it

Recursion shines when the data or the problem is itself recursive: trees (a tree is a root plus smaller trees), divide and conquer (merge sort, quicksort), backtracking (try a choice, recurse, undo) and DFS on graphs.

Common mistakes:

Missing or unreachable base case: the calls never stop and the program crashes with a stack overflow.
Not shrinking: f(n) calling f(n) again loops forever.
Too deep: the stack is limited (often a few MB; Python stops at 1000 by default). A chain of 10⁶ calls can crash even when the logic is right. Rewrite it as a loop or with an explicit stack.
Repeated work: overlapping calls like in fib need memoization.

Cost at a glance

fact(n) timeO(n)

fact(n) stack depthO(n)

naive fib(n)O(2ⁿ)

fib(n) with memoO(n)

Remember

Every recursive function needs a base case and a recursive case that makes the input smaller.
Each call is a frame on the call stack, so recursion depth costs memory and is limited.
Draw the recursion tree to find the running time and spot repeated subproblems.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the stack grow on the way down and shrink on the way up; each return hands its value to the frame below.

Interactive visualizerfocus here, then space ← →

Call stack: factorial(5)

fact(5)

Returned values

Recursion: a function that calls itself on a smaller input. We compute factorial(5). Each call gets its own frame on the call stack.

Pseudocode

 1 fact(n): 2   if n <= 1: return 1     // base case 3   else: 4     return n * fact(n-1)  // recursive call

1 / 1

Check

Three questions. Pick an answer to see why.

While computing fact(5), how many frames of fact are on the stack at the deepest moment?

What happens if you call this with n = 3? f(n): if n == 0: return 0; return f(n − 2) + 1

Why is the naive recursive fib(n) so slow?

Practice

Real problems to lock it in, easiest first.

LeetCodeFibonacci Number beginner↗LeetCodePow(x, n) intermediate↗CSESTower of Hanoi intermediate↗CSESCreating Strings intermediate↗CSESApple Division intermediate↗