Call Stacks and Recursions
This week, I’ve been immersing myself in the world of Data Structures and Algorithms. One thing I have come to find refreshing is that the more practice you put into the work, the more it begins to make sense. I was introduced to the concept of recursion while studying at FlatIron Coding Bootcamp. One thing I wish someone would have told me when I was starting was that “It will all makes sense in due time”. I remember obsessively taking hand written notes, thinking I would look back on them and they would make concepts clearer. And more times than not it wasn’t the case. Now, a little further along into my journey as a Software Engineer, I’m seeing that nothing replaces the value of experience.
In this blog, I will share my insights and perspectives into a data structure called a Stack as well as my insights into Recursions. A call stack is a magical data structure built into many languages that works behind the scenes. One way to think about a call stack is like a stack of papers on a desk.
Before moving on with stacks let me go into Recursions. Recursions are like loops in that they are repeated until a condition is satisfied. But more broadly, recursions are a type of function; a function that calls on itself in some way. So for example: let’s create a function that takes in a number, and prints all the numbers in between the input number and “0”. The function will call on itself inside the body of the function like so:
function countDown(num){
if (num <= 0){
return "End of CountDown"
}
console.log(num)
num--
return countDown(num) //Recursion
}countDown(10)
//In the console this will print out the numbers:
//10, 9, 8, 7, 6, 5, 4, 3, 2, 1
//and end with "End of CountDown"
Tying it all together… What does the Recursion actually look like? And how is the call stack working?
Let’s break it all down.
Starting with our Recursion, let’s look at all that’s going on under the hood:
countDown(10)
//because 10 is not less than or equal to 0 we skip the first line
//we print 10 into the console
//then decrement 10 - 1
//Then return countDown(9)
//we print 9 into the console
//Then decrement 9 - 1
//Then Return countDown(8)
//Then Return countDown(7)
//countDown(6)
//countDown(5)
//countDown(4)
//countDown(3)
//countDown(2)
//countDown(1)
//we print 1 into the console
//Then decrement 1 - 1
//Then return countDown(0)
//which returns "End of CountDown" Now for the Call Stack:
Until we get to the condition or the Base Case, which returns “End of CountDown” when our input equals 0, the function will continue to execute and add to the stack. Think of the call stack as a server at a restaurant taking orders from the table. The base case (inside our function) is like when all the orders at the table have been taken by the server. Until everyone’s order at the table is accounted for, the server won’t put in the order and the customers won’t get their food. So even though we are seeing the numbers printed, the function isn’t actually executing until we hit our base case. Where our function is like the orders from the table, the call stack is the server adding the orders into a piece of paper. Until the final order is taken or the condition is met, the server will continue to take orders or the function will continue to run and the length of the order, or the stack will continue to grow. The stack will continue to grow until the conditions of the function are met. And when that condition is met, the server will return the orders in the reverse order to the kitchen. Although it appears that the purpose of the function is to count down, the computer thinks the main purpose is to return “End of CountDown”, which you can think of as the last order that the server takes from a table. Thinking of recursion and call stacks in this way, although it looks like we are counting down, the functions are actually returning the base case value in reverse like so:
countDown(10) ***Hold until we find countDown(9)
//countDown(9) ***Hold until... countDown(8)
//countDown(8) ***Hold until... countDown(7)
//countDown(7) ***Hold until... countDown(6)
//countDown(6) ***Hold until... countDown(5)
//countDown(5) ***Hold until... countDown(4)
//countDown(4) ***Hold until... countDown(3)
//countDown(3) ***Hold until... countDown(2)
//countDown(2) ***Hold until... countDown(1)
//countDown(1) ***Hold until... countDown(0)
//we print 1 into the console
//Then decrement 1 - 1
//Then return countDown(0)
//HERE WE ARE AT THE TOP OF THE STACK
//***Finally we return "End of CountDown"
//and then close all functions starting from countDown(1) which returns "End of CountDown" from countDown(0)
//close countDown(2) which returns "End of CountDown" from countDown(1)
//close countDown(3) which returns "End of CountDown" from countDown(2)
//etc.
//until we get to the initial function, which is at the bottom of the stack. In our example, countDown(10) is the first function to get added to the stack. And even though it prints a value, it does not fully execute until we reach the top of the stack.
This is my understanding of Call Stacks and Recursions. I hope this is a helpful resource for anyone looking into Call Stack Data Structures and Recursive Algorithms. I hope to continue adding to my knowledge. As always deeper insights or feedback are always welcome.
Happy Coding.
