How does the call stack work?

In JavaScript, or any language, whenever a function is called it is pushed onto the call stack, and whenever a function returns it is popped off the call stack.

We hear this term a lot – call stack – especially in certain contexts like recursive programming among others.

This call stack goes all the way down to computer architecture.

To understand what the call stack is, we have to understand how computer memory (RAM) is internally represented and organized.

The operating system uses some of the total memory (RAM) a computer has. But still, the vast majority is available for other programs to use.

This available memory is classified into two. The stack and the heap.

Let's write a simple declaration in JavaScript: var num = 10;

When we run this code, the memory for the variable num is allocated in the heap.

Another simple script:

function square(num){
return num*num;
}

Since this is a function, memory is allocated on the stack.

All right. For global variables, memory is allocated in the heap. For functions, and function variables, it is on the stack.

In languages like C, we can explicitly ask the compiler to allocate memory for us in runtime. C programmers can specify this memory to be in the heap or the stack.

The heap grows from a lower memory address to a higher memory address (upward), and the stack goes from a higher memory address to a lower memory address (downward).

The stack is also a data structure. Imagine a stack of books. If we put another book onto the stack, it will the first to come out of it (LIFO).

Heap is also another data structure. But, heap memory has nothing to do with the heap data structure. It usually implies a ‘heap’ of memory the programs, and low-level programmers, can use.

Coming back to the call stack, see this recursive JavaScript function to find the factorial of natural numbers:

function factorial(num) {

    if (num == 0)return 1;
    else return num * factorial(num - 1);

}
factorial(10)

When this function is first called, since the ‘base condition’ is not met, the return function is also pushed onto the stack.

So memory is allocated somewhere on top of the available memory (higher memory address).

It recursively runs for the second time, again the ‘base condition’ is not met.

Again, the return function is pushed onto the top of the stack.

This happens again and again until num is decremented down to zero (the 'base condition' here).

Afterward, a return value is generated and the functions pop one after another off the stack.

Each time a function gets pushed onto the stack, it is allocated a contiguous chunk of memory on the stack called the stack frame.

Although it is pushed ‘onto’ the stack, since the stack grows from top to the bottom, the newer stack frames will have lower memory addresses.

The heap grows toward the top and the stack grows toward the bottom.

Some compilers can decide to allocate a function’s memory in the heap. But stack-grows-toward-the-bottom and heap-grows-toward-the-top are easy to explain, understand, and widely accepted.

So looking at recursive functions, we find out that, technically, there is a limit.

Though rare in everyday usage, we may get the maximum stack frames exceeded error even with the correct code (which happens all the time when we write bad recursive functions).

Since JavaScript is made with ‘C’, and every JavaScript code is ultimately compiled down to machine code, I wrote the above recursive function in C.

#include <stdio.h>

int factorial(int num){

if(num == 0) return 1;
else return num*(factorial(num-1));

}

int main(int argc, char** argv){

int result = factorial(10);
printf("%d\n", result);
return 0;

}

I then compiled this with gcc, and used gdb to disassemble it. This is x86 assembly code in AT&T syntax.

(gdb) disassemble/m

Dump of assembler code for function factorial:
3       int factorial(int num){
=> 0x0000555555555149 <+0>:     endbr64 
   0x000055555555514d <+4>:     push   %rbp
   0x000055555555514e <+5>:     mov    %rsp,%rbp
   0x0000555555555151 <+8>:     sub    $0x10,%rsp
   0x0000555555555155 <+12>:    mov    %edi,-0x4(%rbp)
4
--Type <RET> for more, q to quit, c to continue without paging—c

5       if(num == 0) return 1;
   0x0000555555555158 <+15>:    cmpl   $0x0,-0x4(%rbp)
   0x000055555555515c <+19>:    jne    0x555555555165 <factorial+28>
   0x000055555555515e <+21>:    mov    $0x1,%eax
   0x0000555555555163 <+26>:    jmp    0x555555555176 <factorial+45>
6       else return num*(factorial(num-1));
   0x0000555555555165 <+28>:    mov    -0x4(%rbp),%eax
   0x0000555555555168 <+31>:    sub    $0x1,%eax
   0x000055555555516b <+34>:    mov    %eax,%edi
   0x000055555555516d <+36>:    callq  0x555555555149 <factorial>
   0x0000555555555172 <+41>:    imul   -0x4(%rbp),%eax
7
8       }
   0x0000555555555176 <+45>:    leaveq 
   0x0000555555555177 <+46>:    retq   

End of assembler dump.

See the start of the function: 0x000055555555514d <+4>: push %rbp The first hex number is the memory address, the number in angular brackets is the offset from the start, and then the actual instructions. The rbp is the base pointer (bp for base pointer).

At the start of the function, the base pointer is pushed, and saved, onto the stack, and by 0x000055555555514e <+5>: mov %rsp,%rbp it is then made to point to the current function’s stack frame. The rsp is the stack pointer (sp for stack pointer).

After the function returns, the base pointer is popped off the stack, and then it points toward the previous stack frame: 0x0000555555555176 <+45>: leaveq

Speaking in assembly language, whenever rbp and rsp are the same, it means that the current stack frame (it can be the only one on the stack) is empty.

Happy coding!