In the previous lesson, we learned how to write recursive functions in C.
We saw that a recursive function always contains:
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:
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:
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:
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:
Each function call is placed on the stack
The base case stops the recursion
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:
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.
