In the previous weeks, you learned how to control program flow using:
Conditions (if, else)
Loops (for, while)
Functions
Functions helped us break large problems into smaller pieces.
Now we take this idea one step further.
In this lesson, we introduce recursion one of the most powerful concepts in programming.
At first, recursion can feel confusing. But once you understand the idea behind it, many complex problems suddenly become much easier to solve.
1. What is Recursion?
Recursion is when:
A function calls itself to solve a smaller version of the same problem.
Instead of solving a problem all at once, recursion solves it step by step, making the problem smaller each time until it reaches a point where it can stop.
That stopping point is very important.
Without it, the function would keep calling itself forever.
2. A Simple Real-World Analogy
Imagine you are using a video conference platform like Microsoft Teams, Zoom, or Google Meet.
You share your screen during a meeting.
But the screen you share is the same meeting window.
So inside the shared screen, everyone sees the meeting again.
And inside that view… the meeting appears again.
And again.
And again.
Each screen contains another version of the same screen.
This continues until something interrupts it, usually when the screen becomes too small to see.
Recursion works in a similar way.
A function calls itself repeatedly, each time working on a smaller version of the same task, until it reaches a condition where it stops.
3. The Two Parts of Every Recursive Function
Every recursive function must contain two essential parts.
1. Base Case
The base case is the stopping condition.
It tells the function:
“Stop calling yourself and return a result.”
Without a base case, recursion would never stop.
This would cause your program to crash.
2. Recursive Case
The recursive case is where the function calls itself again, but with a slightly smaller problem.
Each recursive call should move the problem closer to the base case.
4. Thinking About Recursion Step by Step
To understand recursion, it helps to imagine the process as a series of function calls stacked on top of each other.
Each call:
Waits for the next call to finish
Receives the result
Continues execution
This stack of function calls is called the call stack.
You do not manage it manually, the system does it for you.
But understanding that it exists helps explain how recursion works internally.
5. A Conceptual Example
Imagine a function that prints numbers counting down.
The task is simple:
3
2
1
Done
Instead of using a loop, we could imagine solving it like this:
Print the number
Ask the function to print the next smaller number
Stop when the number reaches zero
Each step reduces the problem.
Eventually the base case is reached.
6. Recursion vs Iteration
Many problems that use recursion can also be solved using loops.
For example:
| Approach |
Technique |
| Iteration |
Uses loops (for, while) |
| Recursion |
Function calls itself |
Both approaches can work.
The choice depends on the problem.
Recursion is especially useful when problems naturally break into smaller identical subproblems.
You will see examples of this later in algorithms like:
7. Why Recursion Can Be Powerful
Recursion allows programmers to:
Solve complex problems with simpler logic
Express solutions more clearly
Work naturally with hierarchical structures
Break problems into smaller identical tasks
However, recursion must be used carefully.
If the base case is missing or incorrect, the function will continue calling itself indefinitely.
This can lead to a stack overflow, where the program runs out of memory.
8. Thinking Recursively
When approaching a recursive problem, ask yourself three questions:
What is the smallest version of this problem?
This becomes the base case.
How can I reduce the problem slightly?
This becomes the recursive step.
Does each step move closer to the base case?
If the answer to the third question is no, your recursion will never stop.
9. Practice Thinking Recursively
Before writing code, try thinking about these questions conceptually.
For example:
If you had to print numbers counting down from a number to zero, how could the problem become smaller each step?
If you had a word, how might you process one character at a time until the entire word has been handled?
If you had a number and wanted to repeatedly divide it until it reached 1, how might each step reduce the problem?
You don't need to implement these yet.
The goal is to practice thinking in smaller steps.
10. Key Ideas to Remember
Recursion works because of three ideas:
A function can call itself.
Every recursive function must have a base case.
Each recursive call must move closer to the base case.
Once you understand these three ideas, the rest of recursion becomes much easier to learn.
What’s Next
In the next lesson, we will move from the concept to actual recursive functions in C.
You will learn:
How recursive functions are written
How the call stack behaves during recursion
How recursive results are built step by step
Understanding that execution flow is the key to mastering recursion.
