StackOverflow

Recursion Refresh

Recursion is a fundamental concept in computer programming both because it provides an intuitive and clean way to write code, but also because it offers a glimpse into the way that code executes.

I've written a bit before about recursion before - first with a focus on dynamic programming and again later in my post about the Fibonacci sequence. As a refresher, a recursive program is one that calls itself. It is composed of a "base case" and a "recursive case". We make successive recursive calls until we reach the base case, at which point we return.

Here I will explore a different aspect of recursion: the stack.

The stack

We can think of the call stack as an underlying data structure that holds the local execution context for a program. The call stack has the same LIFO ("Last In First Out") properties of a stack data structure that we would use in our code (the opposite of a queue FIFO data structure). This makes sense when we think about how a recursive program executes: once we reach the base case, we want to return the output to the most recent recursive call, and build up our solution from there.

The call stack lives in memory, but unlike the heap, it is finite in size and is managed automatically by your OS. By default, the stack size on Mac OS is 8MB - you can see your current stack and memory limits by running:

ulimit -a

When I run this command on my MacBook Pro, I see the following:

// ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
file size               (blocks, -f) unlimited
max locked memory       (kbytes, -l) unlimited
max memory size         (kbytes, -m) unlimited
open files                      (-n) 256
pipe size            (512 bytes, -p) 1
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 1392
virtual memory          (kbytes, -v) unlimited

StackOverflow

When most programmers hear "StackOverflow" in 2020, our minds jump to the Q&A forum that has helped us solve so many problems. But a stack overflow is a type of exception that occurs when a recursive program opens too many frames. In other words, if our program exceeds the memory limits allocated to the stack, we will see this exception. This is a safeguard against infinite recursion - if your program has a bug and never reaches the recursive case, it will encounter this exception.

Here is a sample program that encounters a stack overflow (in JS, a RangeError):

function helloWorld(i) {
  if (i == 1) {
    return "Hello";
  } else {
    return helloWorld(i);
  }
}

The bug here is that our recursive case doesn't modify the input variable, so we will never reach the base case. When I execute this program, I see the following:

> helloWorld(2)
Thrown:
RangeError: Maximum call stack size exceeded
    at helloWorld (repl:1:20)
    at helloWorld (repl:5:8)
    at helloWorld (repl:5:8)
    at helloWorld (repl:5:8)
    at helloWorld (repl:5:8)
    at helloWorld (repl:5:8)
    at helloWorld (repl:5:8)
    at helloWorld (repl:5:8)
    at helloWorld (repl:5:8)
    at helloWorld (repl:5:8)

Conclusion

Understanding the underlying data structures used to execute our code can help to inform our decisions as programmers. And in this case, it also gives us an understanding of the naming behind one of the most commonly used tools in a programmer's kit: StackOverflow.

Resources:

1. Recursion and stack
2. The JavaScript Call Stack - What It Is and Why It's Necessary - Charles Freeborn
3. Understanding Execution Context and Execution Stack in Javascript - Sukhjinder Arora
4. Stack Overflow logo
5. Memory : Stack vs Heap - Paul Gribble