Call stack & Stack overflow explained

Call stack, recursion and stack overflow(not the website, but the stack overflow exception) are some of the words you would have heard in interviews. In this post, we will see what are they, how they behave in C# and how to avoid the stack overflow exception in your code.

What is a stack & How it works?

Let’s forget programming for a moment, what is stack in real life? Google’s dictionary provides the following meaning,

a pile of objects, typically one that is neatly arranged "a stack of boxes"

Consider, a pile of books. Now you are arranging them neatly on top of one another. This is a stack of books. The book you are placing at the very last would be on the top. It will also be the first one available when removing items in order.

Stack in C# also works in the same way. A stack will contain multiple items that are inserted/pushed into it. When removing or popping those items, the one that entered the stack last will come out first. In other words, it follows a last in first out order.

TLDR, It is a datatype similar to Array & List, the main difference being that you can add or remove items only from the top of the stack and in the LIFO order.

What is a call stack?

Consider the following C# code,

public static void main(){
    var name = getName();
    var age = getAge();
    var address = getAddress();
}

The compiler starts executing the main method. As soon as it reads the first line, it will jump to the getName function and start executing it. After the completion of getName function the computer must return to the 1st line of the main function and resume it.

How will it know where to return after executing the getName functions? The compiler stores this information in a stack and this stack is known as, you guessed it CallStack. Here is an image of how the call stack looks like for the above code,

What is recursion and how does it cause stack overflow?

Recursion occurs when a function calls itself. Consider the following code,

public void getThemAll(Stack Pokemons){
        Pokemons.Pop();
        if(Pokemons.Count > 0){
                getThemAll(Pokemon);
        }
}

This function recursively calls itself until there is no Pokémon name left. Each time a function call is made, the compiler will insert a record into the call stack. This is used by the compiler to return to the previous iteration of the function after executing the current one.

Here is how the call stack of a recursive function looks in Visual Studio after a few iterations.

How many records can a stack hold? 10K, 20K? The code in the above screenshot ran slightly more than 19K times. It depends on the memory allocated for your stack. Typically it is around 1 MB. But sooner or later you will hit the limit. When you hit the limit, you will get the StackOverflow exception.

How do you avoid this?

Typically, you will not see this error often even if you use recursive functions as call stack can handle thousands of recursions. However, if possible replace the recursive function with a loop, any loop. Unlike function calls loops will not add an entry to call stack and it will not cause this exception.

Consider the above code. It can be rewritten into,

public void getThemAll(Stack Pokemons){
        do{
                Pokemons.Pop();
        }while(Pokemons.Count > 0);
}