In the previous lesson, we introduced the idea of recursion.
We learned that recursion happens when:
A function calls itself to solve a smaller version of the same problem.
But understanding the concept is only the first step.
Now we need to learn how recursive functions are actually written in C.
In this lesson we will focus on:
The structure of recursive functions
The importance of the base case
How recursive calls move toward the solution
How recursion executes inside the program
We will focus on understanding the pattern, not memorizing specific solutions.
1. The Structure of a Recursive Function
Almost every recursive function follows the same pattern.
if (base case)
return result
else
return function(smaller problem)
This means every recursive function must answer two questions:
When should the recursion stop?
How does the problem become smaller each time?
If you cannot clearly answer both questions, recursion will not work.
2. Understanding the Base Case
The base case is the stopping condition.
It is the simplest version of the problem that can be solved directly.
For example, imagine a function that repeatedly reduces a number until it reaches zero.
The base case would be:
when number == 0
Once that condition is reached, the function stops calling itself.
Without a base case, the function would call itself forever.
This would eventually cause the program to crash.
3. Understanding the Recursive Case
The recursive case is where the function calls itself.
But it must call itself with a smaller version of the problem.
For example:
solve(n) calls solve(n - 1)
Each step moves the problem closer to the base case.
Eventually the smallest case is reached and recursion stops.
4. A Simple Example of Recursion
Let’s imagine a function that counts down from a number to zero.
The idea would be:
Print the number
Call the function again with a smaller number
Stop when the number reaches zero
A recursive version could look like this:
void countdown(int n)
{
if (n == 0)
{
printf("Done\n");
return;
}
printf("%d\n", n);
countdown(n - 1);
}
Notice the structure:
Each call moves closer to the stopping condition.
5. Tracing Recursive Execution
Understanding recursion requires tracing how functions execute.
Let’s imagine we call:
countdown(3)
The calls happen like this:
countdown(3)
countdown(2)
countdown(1)
countdown(0)
Once the base case is reached, the function stops calling itself.
This chain of calls is managed by something called the call stack.
6. The Call Stack
Every time a function runs, it is placed on the call stack.
When a function calls another function:
For recursion, the same function is placed on the stack multiple times.
Example stack progression:
countdown(3)
countdown(2)
countdown(1)
countdown(0)
Once the base case returns, the functions start finishing one by one.
Understanding this stack behavior is key to understanding recursion.
7. A Second Example to Think About
Imagine a function that repeatedly halves a number until it reaches 1.
Conceptually the steps would be:
halve(16)
halve(8)
halve(4)
halve(2)
halve(1)
Again we see the same pattern:
This structure appears in many recursive algorithms.
8. Common Mistakes When Writing Recursion
Students often struggle with recursion because of a few common mistakes.
Missing Base Case
If you forget the base case, the function never stops calling itself.
This leads to infinite recursion.
Recursive Step Does Not Reduce the Problem
If the recursive call does not make the problem smaller, the base case will never be reached.
Example mistake:
function(n)
{
return function(n);
}
This will run forever.
Base Case That Is Never Reached
Sometimes the base case exists but the logic never reaches it.
Always verify that each recursive call moves closer to the stopping condition.
9. How to Approach Recursive Problems
When writing a recursive function, start with these steps.
Step 1: Identify the Smallest Case
What is the simplest version of the problem?
That becomes the base case.
Step 2: Break the Problem Into a Smaller Version
How can the function reduce the problem slightly?
That becomes the recursive call.
Step 3: Make Sure the Problem Shrinks
Every recursive call must move closer to the base case.
10. Practice Thinking Recursively
Before writing full solutions, try reasoning through these problems conceptually.
For example:
If you wanted to repeatedly remove the first character of a word until nothing remains, what would the base case be?
If a function repeatedly subtracts 2 from a number until it becomes zero or negative, how would the recursive step work?
If a number is repeatedly divided by 3 until it becomes 1, what condition should stop the recursion?
Focus on identifying:
the base case
the smaller problem
That thinking process is more important than the exact code.
Key Ideas to Remember
Recursive functions always contain:
And every recursive call must move closer to the base case.
What’s Next
In the next lesson, we will apply recursion to strings and arrays.
You will see how recursion can be used to process data step by step, such as examining one character of a string at a time.
Those examples will help you build the thinking needed for the upcoming project tasks.
