# 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 ```typescript 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`. ```typescript 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: ```typescript const c = () => { console.log('first') b() } ``` When `c()` starts, the stack contains: ```typescript c() ``` Then `console.log()` is called and is temporarily pushed on top: ```typescript console.log('first') c() ``` `console.log()` finishes almost immediately and is popped, leaving: ```typescript c() ``` Execution then continues to `b()`, which is pushed on top of `c()`, and eventually `a()` is pushed on top of `b()`: ```typescript a() b() c() ``` ## Now, let's dive deep into recursion Let's look in a DFS pre order traversal. ```typescript 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: ```typescript 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)`. ```typescript 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. ```typescript 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. ```typescript frame(3) result = [1, 2, 3] frame(2) frame(1) ``` And again, left of 3 is 4. ```typescript 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: ```typescript 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: ```typescript 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: ```typescript 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: ```typescript 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: ```typescript 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. ```typescript 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.