A new perspective on recursion and the call stack

Every explanation of recursion I read told me the same thing: a function that calls itself, with a base case so it stops. Which is accurate, and which taught me nothing, because it never answered the question I actually had.

The question was: at this exact moment, what is sitting on the call stack?

First of all, let's talk a bit about the call stack.

Let's say you have this code

const a = () => {}

const b = () => {
    a()
}

const c = () => {
    b()
}

c()

When you call c(), c is pushed onto the call stack.

While c() is running, it calls b(), so b is pushed on top of c.

Then b() calls a(), so a is pushed on top of b.

a() - finishes first and is popped
b() - finishes second and is popped
c() - finishes third and is popped

This means that the last function pushed onto the call stack is the first one to finish and be popped off. - keep this idea in mind, as it's important to understand recursion.

Also remember that the statements inside each function execute normally. For example:

const c = () => {
    console.log('first')
    b()
}

When c() starts, the stack contains:

c()

Then console.log() is called and is temporarily pushed on top:

console.log('first')
c()

console.log() finishes almost immediately and is popped, leaving:

c()

Execution then continues to b(), which is pushed on top of c(), and eventually a() is pushed on top of b():

a()
b()
c()

Now, let's dive deep into recursion

Let's look in a DFS pre order traversal.

function preOrder(node, result = []) {
    if (!node) return result;

    result.push(node.value);       // visit the node
    preOrder(node.left, result);   // go left
    preOrder(node.right, result);  // go right

    return result;
}

And the tree I'll trace it on. I numbered the nodes in the order they get visited, so you can check yourself as we go:

        1
       / \
      2   7
     / \
    3   6
   / \
  4   5

Two rules run everything, and there are only two.

A call puts a frame (a function call) on the call stack. A return takes one off.

I'll draw the stack with the newest frame on top and the first call at the bottom, and I'll name each frame after the node it's working on, so frame(4) is the call that got node 4 as its argument.

The trace

We start with preOrder(1).

frame(1)          result = [1]

Node 1 got pushed into result, and now line 4 runs: preOrder(node.left), where node.left is 2. That's a call, so a frame goes on.

frame(2)          result = [1, 2]
frame(1)

And now you might think, "hey, but it's also preOrder(node.right, result); right under preOrder(node.left, result); - why doesn't this go on the stack?"

The reason is, because preOrder(node.left, result) calls other functions in a chain. And it will get deeper in the first called function of each called function, until the last of those called functions returns. Meaning it will keep pushing on the stack that chain of called functions.

Let's continue: Same thing happens inside frame(2). It pushes 2, then calls left, which is 3.

frame(3)          result = [1, 2, 3]
frame(2)
frame(1)

And again, left of 3 is 4.

frame(4)          result = [1, 2, 3, 4]
frame(3)
frame(2)
frame(1)

Now node 4 has no children. preOrder(4.left) still gets called, with undefined. A real frame goes on the stack, runs if (!node) return result, and comes straight back off:

frame(∅)          ← pushed, hits the base case, popped
frame(4)
frame(3)
frame(2)
frame(1)

Now it's the important part, we are still on frame(4) and as I said, the all of the statements in the function get called in order, and the function has another call preOrder(node.right, result) meaning that frame(4) moves to its next line and does the same for 4.right. Another empty frame on, another off.

After that, frame(4) has no lines left, so it hits return result and gets popped too:

frame(3)          result = [1, 2, 3, 4]
frame(2)
frame(1)

We're back inside the body of frame(3), on the line right after the call that just finished. That line is preOrder(node.right), and the right of 3 is 5:

frame(5)          result = [1, 2, 3, 4, 5]
frame(3)
frame(2)
frame(1)

Node 5 is a leaf as well, so it does its two empty calls and pops. Now frame(3) is out of lines, so it returns, and we land back inside frame(2) on its preOrder(node.right) line, where the right of 2 is 6:

frame(6)          result = [1, 2, 3, 4, 5, 6]
frame(2)
frame(1)

That one pops, frame(2) runs out of lines and pops, and we're back in frame(1) on its right call:

frame(7)          result = [1, 2, 3, 4, 5, 6, 7]
frame(1)

7 pops, 1 pops, the stack is empty, and result is [1, 2, 3, 4, 5, 6, 7].

Two orders, not one

Look back at the snapshots and you'll see two separate sequences.

The order the non-empty node frames went on the stack is: 1 2 3 4 5 6 7. That's preorder, and it's exactly the numbering in the tree diagram.

The order those node frames came off is: 4 5 3 6 2 7 1. That's postorder,

That's why, if you want to capture the post order, you push in the array after the first function call.

    preOrder(node.left, result);   // go left
    preOrder(node.right, result);  // go right
    result.push(node.value);       // gets called after the last  preOrder returns on the stack for that specific frame

And if you've ever wondered where postorder physically comes from, this is it.

You get both from one traversal, which is worth remembering because React uses both, and I'll come back to that.

In the next blog post, I will show you how the React fiber gets walked

What I'd tell myself a year ago

Don't start by asking what recursion is.

Ask:

What's on the stack right now?

A call pushes a frame.

A return removes one.

When a recursive call happens, the previous frame doesn't disappear. It waits underneath, paused at the point where it made the call.

And when the recursive call returns, that old frame continues from exactly where it left off.

Once I could see that happening frame by frame, recursion stopped feeling like a function somehow teleporting through a tree.

It became much more mechanical.

Just a stack of unfinished function calls.