Recursion & the Call Stack

Recursion is a pause button

The confusing part of recursion isn’t the function calling itself. It’s that a paused call is still alive, holding its own variables, waiting. When factorial(5) calls factorial(4), the first call doesn’t disappear — it freezes mid-expression with n = 5 and waits.

The visualizer above makes this visible. Play it and watch two distinct phases:

• Going down — frames pile onto the stack. Nothing has been computed yet.
• Coming back up — the base case returns, and each frozen frame wakes up, does its one multiplication, and returns to its parent.

Everything hard about trees, graphs, backtracking and DP is this picture with a different label on the boxes.

The one question

Before you write any recursive function, answer this in one sentence:

What does this call return to its parent?

That’s it. That’s the technique. If you can answer it, the code writes itself. If you can’t, you don’t understand the problem yet and writing code will not help.

Examples, so it’s concrete:

• maxDepth(node) returns the height of the subtree rooted at node.
• isBalanced(node) returns the height, or -1 if this subtree is unbalanced.
• dfs(node) in Diameter of a Binary Tree returns the longest downward path from node, while separately recording the best answer seen anywhere.

Notice the last one: what a call returns is not always the answer to the problem. That distinction trips up more people than any syntax issue, and it’s why Binary Tree Maximum Path Sum is hard.

The three moments

Every recursive function on a tree has exactly three places work can go:

void dfs(Node* node) {
    if (!node) return;
    // PREORDER  — before recursing. Pass information DOWN to children.
    dfs(node->left);
    // INORDER   — between the two calls. On a BST this yields sorted order.
    dfs(node->right);
    // POSTORDER — after recursing. The children's answers have come UP.
}

Choosing the moment is choosing the algorithm:

Every recursive function has three parts

1. Base case — when do you stop? Get this wrong and you get a stack overflow.
2. Recursive step — a strictly smaller version of the same problem.
3. Combine — what do you do with what came back?

If you can’t name all three, you don’t have a recursive solution yet.

Why fib is the most important trace on this page

Play the fib(n) visualizer and watch the amber panel. fib(2) gets computed three times for n = 5; for n = 30 the waste is astronomical. Two identical subtrees in that drawing are the entire justification for memoisation, and memoisation is the entire justification for dynamic programming.

When you reach week 10 and DP feels like a wall, come back to this page. DP is not a new topic. It is this call tree, with a cache.

The exercises

Do each in both C++ and JavaScript, and draw the stack on paper before you run it:

1. factorial(n) — draw all 5 frames for n = 5.
2. fib(n) — draw the full call tree for n = 5 and count the nodes. Circle two identical subtrees.
3. sum(arr, i) — recursion over an array. What’s the base case?
4. reverse(str) — recursion producing a value rather than a number.
5. power(x, n) — then make it O(log n) by halving. Notice the call tree changes shape.
6. Print 1..n recursively, then n..1 — the only difference is whether the print happens before or after the recursive call. Sit with that; it’s preorder vs postorder in miniature.
7. Add a memo to fib. Watch the call tree collapse.

The three mistakes

1. No base case, or the wrong one. Every recursion needs a floor. Check it first.
2. Not shrinking the problem. f(n) calling f(n) recurses forever. The argument must strictly move toward the base case.
3. Ignoring the return value. People write the recursive call and then throw away what came back. If you answered “what does this call return to its parent?”, you’ll notice.

Done when

You can draw the call stack for factorial(5) and the call tree for fib(5) on paper without running anything, and you can state — before coding — what any recursive function you write returns to its parent.

Week 6 (trees) is where this pays off, and it will pay off completely.