Attack on Stack

How the Stack Works and Why it Matters

Introduction

The stack data structure is a crucial topic for all programmers to know, and yet is one of the toughest concepts for new programmers to come to grips with. The goal of this article is to demystify the stack data structure and explain its applications in everyday programming. We’ll explore what the stack exactly is, how it is utilized by programming languages such as JavaScript, and how you can apply it yourself to make better code.

What is the stack?

When first learning about the stack data structure, it’s helpful to think of an analogy. We’ll start with one that everyone is familiar with — ice cream! When you start making an ice cream, you start off with an empty ice cream cone — an empty stack. Then, you put on your first scoop of ice cream — let’s say, peanut butter. Next, you’ll put on the second scoop — mint (eww). This continues until you’ve loaded up your ice cream cone with several scoops of different flavours.

Now it’s time to eat all that delicious ice cream. Obviously you can’t eat the first scoop you placed on the cone, since it’s supporting the other scoops above. You always eat the top scoop first, which was the last scoop you placed on top. This is a fundamental concept of the stack data structure — first in, last out (FILO). FILO means that whatever sits on the top of the stack is also the first to be removed, and the data resolves in the reverse order to which it is added. You eat the top scoop first, then the next, and the last scoop you eat is the one you placed on the cone first.

This is the core of the stack data structure — you are setting up the data one on top of the other, and resolving them in the reverse order to which you placed them. First in, last out.

Okay, now I’m craving ice cream, but how is this relevant to programming?

Great question. Many programming languages, such as JavaScript, rely on the stack data structure to resolve function calls — this is called the call stack. You can also structure your own functions to utilize a stack-based data approach, most commonly in the form of recursive functions. Let’s start with the former.

The Call Stack

One of the coolest things that learning the stack data structure gives you is the ability to better understand the programming language you’re writing in. In JavaScript, function calls are handed in the stack model. Chrome Developer Tools has a fantastic functionality that provides a visualization of the call stack — we’ll be using this for the remainder of this guide.

This simple program first calls the hello() function, which prints “hello” to the console, followed by the world() function, which prints “world” to the console. Pay attention to the (currently empty) call stack on the right side of the image.

The first item added to the call stack in an anonymous function, which is the main function that represents the entire program. Think of this as the ice cream cone — it remains at the bottom on the stack, and only resolves once the program has finished running.

First, the hello() function is added to the stack. Since it relies on no other functions to execute, it will be ran immediately.

The hello() function resolves immediately, and is removed from the stack. The program moves on from the hello() function call. Notice that “hello” is now printed to the console below.

Next is the world() function. It is added to the top of the empty stack.

Once again the world() call resolves instantly, and the anonymous function resolves after, since the program is finished running. Notice that “world” prints to the console below.

This is an example of how synchronous code with no dependencies operates on the call stack. Since there are no nested callbacks in the code, each “scoop” is loaded on to the cone and instantly “eaten”. The code operates as you’d expect — each piece of code is executed the moment it is called.

How about if there are nested callbacks? This is where the stack model really comes into effect. Let’s look at a slightly more complicated program and how the call stack interacts with it.

This is the new program we’ll be going through. Take a moment to understand how it works — first we’ll call greeting(), which with then call helloWorld(), which will then call hello() and world().

First up we call greeting(), which is added as the first function at the bottom of the stack. Remember that (anonymous) is the “ice cream cone”, which represents the main file. It is the root of our program, and will only resolve once the program has finished running.

Unlike the previous example, greeting does not resolve right away — first, it needs to determine the value of helloWorld(). Therefore it remains on the stack, and helloWorld() is placed on top of it.

In a similar manner, helloWorld() cannot return without first learning the values of hello() and world(). Therefore it too remains on the stack, and it checks these values first, starting with the first value called - hello(), which goes on top of the stack

hello() does not rely on any other callbacks, and so resolves instantly. It is removed from the stack, and now helloWorld() knows the value of hello().

helloWorld() is still not done however — it next needs to determine the value of world(). world() is therefore placed on top of the stack.

Just as before, world() does not rely on a callback, and so resolves instantly. helloWorld() is next on the stack, and since it now knows the values for both of its callbacks…

helloWorld() finally resolves, and is removed from the stack. Now greeting() knows the value for helloWorld(), and can be executed.

greeting() resolves, and the message is printed to the console below. The call stack is now clear, and the program will continue on to the next line of code. Once it is completed, the (anonymous) function resolves, and we know the program has finished running.

Understanding the call stack provides numerous benefits. First, it is invaluable when debugging — understanding the order in which code resolves allows the programmer to identify potential issues before they even occur, and allows controlled use of side effects within functions to alter how your program runs. If you’ve ever used console.log() statements within functions to determine the value of something while debugging, you’ve interacted with the call stack — you intuitively knew that the console.log() statement would be run whenever that function is called as a side effect, and would print to the console before the rest of the function was executed.

I believe that new programmers do actually instinctively understand the call stack before they’ve ever heard of it. Once you spend some time writing in JavaScript, you can predict the order that functions are called just by looking at the code beforehand. Learning the call stack allows you to put that intuition to words, and allows you to explain why the functions are resolving in a specific order.

Recursion

Now that we understand how the call stack operates within our language, how can we go about utilizing the model for ourselves? Although there are myriad ways one can utilize a stack data structure, one of the most common is the use of recursion.

Recursion is where a function calls itself continuously until it reaches a “base state”, at which point the recursion ceases and the chain resolves. As you may have guessed, this is simply a stack consisting of multiple calls of the same function, which resolves once the base case is placed on top.

Recursion can be an extremely confusing topic for new programmers, but understanding the stack data structure makes understanding recursion much simpler. Recursion is a function calling itself, and each call brings it closer and closer to the base case — similar to how in the above helloWorld() example, each call brought us closer and closer to a function without a function call — in that case, hello() and world() just returned simple strings. Once we had those pieces of the puzzle, the lower functions on the stack were able to slot them into their own return statements, and a chain of resolving functions finished off the sequence.

Let’s take a look at an example and watch how the call stack operates together.

Let’s say we have an interview question — write a recursive function that takes in a number, and sums all the numbers between that number and 1. For example, if we provided the number 5 as an argument, the program would return 5 + 4 + 3 + 2 + 1 = 15. Here’s an example of a possible recursive solution:

So, how does this work? Well, we know the base case — if the number is 1, the answer is 1. In all other cases, we have to figure out how to get closer to 1.

recursiveFunc(2) = 2 + 1 = 3

recursiveFunc(3) = 3 + 2 + 1 = 6

recursiveFunc(4) = 4 + 3 + 2 + 1 = 10

Notice how each time we go up a number, the result is increasing by that number. That means we can rewrite this as:

recursiveFunc(4) = 4 + recursiveFunc(3)

or

recursiveFunc(number) = number + recursiveFunc(number - 1)

This is our recursive case. Each time we call the function, the input number is reduced by one for the next call, steadily getting closer and closer to our base case. Let’s run it and watch the call stack.

First up the program will add the function to the call stack and check to see if number === 1. Since it does not, it will use the recursive case, which in this case is the value of 5 + addNumbersRecursive(4). It doesn’t yet know the value of addNumbersRecursive(4), so it first needs to add that call to the stack.

The same function is added to the top of the stack, and again the recursive state triggers. This time the return value is 4 + addNumbersRecursive(3). Since the program doesn’t yet know the value of addNumbersRecursive(3), it will need to call it and add it to the top of the stack. This continues on several times…

After several function calls in this loop, the inputted number is finally 1. This results in the base case, which simply returns 1. Since there are no new function calls in this base case, the function is applied to the top of the stack and resolves immediately.

Once the previous function has resolved the next function on top of the stack, which is addNumbersRecursion(2), now knows that addNumbersRecursion(1) = 1. It can now resolve itself by adding 2 + 1 = 3. This means that the next function in the chain can also now resolve, in a cascading chain down to the bottom of the stack.

Now we are at the bottom of the stack, the correct answer is printed into our console thanks to Chrome Dev Tools being smart enough to print our answer without us having to specifically console.log it.

Recursive algorithms work by utilizing the stack model to constantly call a function until that function reaches a base case. That base case is the missing puzzle piece that then solves the previous puzzle, and that previous puzzle is then used as the missing piece for the puzzle before that. This continues until the whole puzzle has been completed.

Here is the exact same recursive algorithm, but with a call stack of 600 function calls! It is paused on the exact moment the program finally reached the base case, and from this point would resolve each function call with the return value from the previous function call. If you are curious, the answer is 180,300.

As you can see from the above image, the call stack can be heavily loaded before resolving. Note that the call stack is not infinite, and your program can throw a “call stack exceeded” error when too many functions are placed on the stack. This is usually because a recursive algorithm is not able to reach its base case, and infinitely loops through the recursive case. This call stack limit depends on the browser or software running it — at the time of this writing, Chrome supports a call stack limited to 10,300 function calls.

Reaching the Bottom of the Stack (article)

You may still be confused by the call stack and recursion — don’t be discouraged, this is a tough concept to wrap your head around! Take some time to play around with it in the Chrome Dev Tools (Sources >> Snippets to write JS directly into the testing area), or look back on a previous program you wrote and see if you can guess what the call stack will do. Chances are you can, and now you have the knowledge to explain why the program is running in that specific order.

You now know what a stack data structure is and the principal of first in, last out. You can apply that knowledge to how JavaScript executes code in sequence on the call stack, and how nested function calls operate on the call stack. Finally, you can now apply this data structure to make your own recursive algorithms and identify how the call stack is resolving when you run these recursive algorithms.

Understanding the stack data structure is an important step towards learning the call stack. Understanding the call stack is an important step towards becoming good with recursion. Becoming good with recursion is an important step towards becoming an excellent programmer. You now understand the stack data structure, so… resolve your way down the chain on the path towards programming excellence!

Resources

JavaScript Call Stack

Stack Data Structure | Studytonight