Think together · Start with a little story
The robot keeps saying, “Please ask the next person to help,” but no one ever completes the smallest task. The line never ends.
Lay out the process
- Task n = 2Pass to n = 1
- Task n = 1Pass to n = 0
- Base caseAnswer n = 0 directly
- ReturnDo not add another task
A base case answers the simplest problem directly, without another recursive call.
You must also check that every call really moves closer to it. Writing n == 0 as the base case does not help if each call increases n.
01What is a stopping condition?
A more precise term in recursion is the base case:
if (n == 0) {
return;
}It tells the function: “There is nothing more to split here, so you can finish directly.”
02Is a stopping condition enough?
No.
void f(int n) {
if (n == 0) {
return;
}
f(n + 1); // moves farther away
}Starting with f(3), n becomes 4, 5, 6, ... and never reaches 0.
03Two things correct recursion needs
A destination
There is a base case that can finish directly.
Progress toward it
Every recursive call moves the problem closer to the base case.
04What happens if it never stops?
The number of active calls keeps growing, using more and more call-state space.
Real systems have limited call-stack space. A common result is a stack overflow or an abnormal program termination.
05Must the stopping condition be n == 0?
Of course not.
if (left > right) {
return;
}Or:
if (node == nullptr) {
return;
}The base case depends on the problem.
06How can you check whether recursion will stop?
Ask three questions:
What is the destination?
When does recursion stop?
What changes at each step?
Does the problem get smaller?
Will it definitely get there?
Will every valid input eventually reach the base case?
What have you learned?
- Recursion needs a base case to stop making calls.
- A base case alone is not enough; the recursive steps must move toward it.
- Infinite recursion keeps increasing the number of active calls.
- Too many nested calls can cause a stack overflow.
- The form of the base case depends on the problem.
Next: What Happens to the Call Stack During Recursion?
Your turn to try
The rule stops when n == 0, and each call subtracts 2. Starting from 3, will it reach 0?
Ready? Open to see the explanation
No. The sequence is 3, 1, -1, ... Redesign the decrement or the base case, and define the valid input range clearly.