Unraveling Recursion: A Practical Look at the Call Stack and Heap
Tags: codinghallenges, software, recursion, callstack
Published: 2023-11-11 11:01:24

If you’ve been following me, you might recall a harrowing tale of a developer coming to grips with recursion. The aptly titled 'Decoding Recursion: The Concept That Had Me Stumped'. But your cogitation and feedback suggest we dig a tad deeper. Brave ones have emerged requesting a practical walkthrough of recursion. In this sequel, we'll take a hands-on approach to recursion using the call stack/heap. Here's a [link to the original post.](https://www.balysnotes.com/decoding-recursion-part-2)

Let's hoist the mainsail and dive in.

### Under the Hood: What Happens When Functions Run?

So, matcha latte in hand, (or is it an afternoon beer?), let’s unravel what’s going on 'under the hood' when functions are involved. Every function in its operation has an allocated memory space. Avoiding the technical jargon for the sake of our shared sanity, let's visualize this as tiny compartments in your computer's brain.

When a function runs, it's like the computer opens that compartment and dumps everything the function needs inside – the variables, calculations, and that little reminder of your lunch break at 12 pm.

This "compartment" goes by a couple of names in the programming world: Stack and Heap. While they are both for storage, they differ slightly in usage. The stack is used for static memory allocation and the heap for dynamic memory allocation.

### Enter Recursion: A Practical Look

Since we're all here for recursion, let's take a prime example - factorial computation. A factorial is the product of a number (n) and all the integers below it. Remember 5! (factorial) equaling 5x4x3x2x1? Yes, that one.

In code form, a basic recursive function for a factorial would look something like (javascript this time, cause turns out, it has a much larger audience):

```javascript
function factorial(n) {
  if (n === 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
```

Now, let's visualize this on the call stack.

Every recursive call will add a layer to the stack. It's like a pile of dishes. The first call (n=5) is the first plate. Then n=4, then 3, 2, and finally 1. After that, the result bubbles up, washing the dirty dishes one by one from the top until you reach the clean plate at the bottom, i.e., the final answer.
Remember that in heaps/stacks, data is added in a first come last serve basis.
Here's a visualization:

| Heap         | Result | Code explanation                                                                        |
|--------------|--------|-----------------------------------------------------------------------------------------|
| n==1         | 1      | base case: (n==1) return 1;                                                             |
| n==2         | 1 * 2  | n is 1 (n * factorial(n-1) which comes from previous call above. result then becomes 2. |
| n==3         | 2 * 3  | n is 2, which again comes from previous call above. the result becomes 6.               |
| n==4         | 6 * 4  | n is 6, which again comes from the call above. the result becomes 24.                   |
| n==5         | 24 * 5 | n is 24, the result becomes 120.                                                        |
| final result | 120    | This is what is finally returned. 120.                                                  |


### Stack Overflow: Recursion's Gotcha!

Stack overflow – it isn't just a popular website, folks; it's recursion's Achilles heel. This happens when our recursion burrows too deep, causing the application to run out of memory space. This is because every OS assigns a running program a fixed memory allocation (i.e. 4MB worth of space). If you exhaust this space, you then might get a stack overflow /segmentation fault error. There goes the stack of dirty dishes tumbling down!

This potential drawback highlights how deep understanding of recursion can help developers optimize for performance.

### Wrapping It Up

There you have it - a code soup stirred with the call stack/heap and topped off with a sprinkle of recursion. Hopefully, this has helped demystify the concept a bit. But who knows? Perhaps our odyssey is just starting - linked lists, binary trees, sorting algorithms - all served with that recursion spice, are waiting!

Remember, fellow devs, recursion is a powerful tool and understanding how it works at every level aids in writing better, cleaner, more intuitive and more efficient code... even if it stumps us occasionally!

As always, sail through your coding voyage, one recursion at a time.