Understanding How Recursion Actually Runs (The Call Stack)

In the previous lesson, we learned how to write recursive functions in C.

We saw that a recursive function always contains:

• A base case (when the function stops)

• A recursive case (when the function calls itself with a smaller problem)

But many beginners still struggle with one question:

What actually happens inside the computer when a recursive function runs?

To understand recursion fully, we need to understand something called the call stack.

1. What is the Call Stack?

Whenever a program runs a function, the system temporarily stores information about that function:

• its parameters

• its local variables

• where it should return after finishing

This information is stored in a structure called the call stack.

You can imagine the call stack like a stack of books.

When a new function runs:

• it is placed on top of the stack

When a function finishes:

• it is removed from the top

Because of this, the last function called is the first one to finish.

This is known as Last In, First Out (LIFO).

2. What Happens During Recursion?

In recursion, the same function is called again and again.

Each call is placed on the call stack.

Example function:

void countdown(int n)
{
    if (n == 0)
    {
        printf("Done\n");
        return;
    }

    printf("%d\n", n);
    countdown(n - 1);
}

If we call:

countdown(3);

The system creates several function calls.

3. Step-by-Step Execution

The stack grows like this:

countdown(3)
countdown(2)
countdown(1)
countdown(0)

Each function waits for the next one to finish.

The base case happens when:

n == 0

At this point, recursion stops.

Then the stack starts unwinding.

4. What Does "Unwinding the Stack" Mean?

Once the base case returns, functions start finishing one by one.

The stack now works in reverse order.

countdown(0) finishes
countdown(1) finishes
countdown(2) finishes
countdown(3) finishes

This process is called unwinding the call stack.

The program returns step by step until it reaches the original call.

5. Visualizing the Stack

You can imagine the call stack like this:

Top of Stack
-------------
countdown(0)
countdown(1)
countdown(2)
countdown(3)
-------------
Bottom of Stack

Once the base case is reached, the top function finishes and is removed.

Then the next function continues execution.

This continues until the stack becomes empty again.

6. Why Understanding the Stack Matters

Many recursive algorithms rely on the fact that the stack stores intermediate states.

Each function remembers:

• where it paused

• what value it was working with

• what to do after the recursive call returns

Because of this, recursion can solve problems that require building results step by step.

7. Recursion vs Loops

At this point you might wonder:

Why use recursion when loops already exist?

Loops repeat actions directly.

Recursion breaks a problem into smaller copies of itself.

Some problems are naturally recursive, such as:

• navigating tree structures

• processing nested data

• breaking problems into smaller subproblems

In those cases, recursion can make solutions much clearer.

8. A Simple Thinking Exercise

Imagine a function that repeatedly reduces a number until it reaches 1.

Conceptually the calls would look like this:

process(8)
process(4)
process(2)
process(1)

Each call waits for the next one to finish.

Once the smallest case is reached, the stack unwinds.

Thinking about recursion this way makes it much easier to understand.

9. The Danger of Infinite Recursion

If the base case is missing or incorrect, recursion will never stop.

Example of a dangerous recursive function:

void badFunction(int n)
{
    badFunction(n - 1);
}

This function has no stopping condition.

The call stack will continue growing until the program crashes.

This is called a stack overflow.

10. How to Check If Your Recursion Is Correct

Whenever you write a recursive function, always verify three things:

1. There is a clear base case

The function must know when to stop.

2. The problem becomes smaller each time

Each recursive call must move closer to the base case.

3. The base case will eventually be reached

If the problem never reaches the base case, recursion will fail.

Key Ideas From This Lesson

Recursion works because of the call stack.

During recursion:

1. Each function call is placed on the stack

2. The base case stops the recursion

3. The stack then unwinds step by step

Understanding this process is what makes recursion easier to reason about.

What Comes Next

Now that you understand:

• what recursion is

• how recursive functions are written

• how recursion executes inside the computer

You are ready to start applying recursion to real problems.

In upcoming exercises, you will practice identifying:

• the base case

• the recursive step

without relying on loops.

The goal is to train your brain to recognize problems that naturally fit recursive thinking.