The Mystery of Recursion: Call Stacks

Introduction

The idea of calling a function within a function... within a function may be hard to wrap your mind around at first.

I know that when I was first introduced to the concept of recursion, it was something completely alien to me.

Luckily, understanding call stacks, the hierarchy of function calls, can help clear up some of the confusion surrounding recursion.

What Happens When a Function is Called?

We're used to our computer compiling and then outputting our code in a mere matter of seconds. Under the hood, however, lots of processes are taking place.

When we call a function, some memory is set aside for that function. This memory is called a stack frame (or function frame).

If multiple functions are called at the same time, memory is set aside for all of them (i.e all of the functions have frames). However, at one time, only one frame is active (running).

So how does the computer decide which function is active?

Well, these function calls are arranged in a stack--think a stack of trays, where the newest tray placed is the first one picked up. In the same way, the newest function called is the first one active.

In technical terms, a function is popped off the stack when it's done its processes and the function below it is pushed to the top.

For instance, let's create a recursive function that builds a staircase:

#include <stdio.h>

void printStaircase(int height)
{
	// recursively calls function until height would be 0
	if (height > 1)
		printStaircase(height - 1);

	for (int i = 0; i < height; i++)
	{
		printf("#");
	}
	printf("\n");
}

int main(void)
{
	printStaircase(5);
}

Let's think about this through the lens of a call stack:

1. main( ) is called by default

2. printStaircase(5) is called in main( )

3. printStaircase(4) is called recursively

4. printStaircase(3) is called recursively

5. printStaircase(2) is called recursively

6. printStaircase(1) is called recursively

Now, just like a stack of cafeteria trays, the sixth step, printStaircase(1), is the active function at the top of the stack, and so on...

*There are also technically printf( ) functions between each step, but you get the idea.

If you were wondering, the output looks like this in the termal:

Final Thoughts

Hopefully now recursion is slightly more digestible, even if you don't quite get it all the way. Thanks for reading!