Recursion: Base Cases and Smaller Problems
Count pages by solving a smaller count
A school booklet has three pages to review. We can describe the count as one current page plus the count of the remaining pages, until no pages remain.
A recursive function calls itself. A base case returns without another recursive call. Every repeating call must move toward a base case for the supported inputs.
Trace calls
Follow the smaller argument supplied by each call.
Trace returns
Explain how waiting calls combine their results.
Check termination
State the accepted input and compare recursion with iteration.
Go down to the base case, then return upward
Smaller calls
Each step asks for one fewer remaining page.
3 → 2 → 1 → 0Base case
No pages remain, so return zero.
countPages(0) → 0Returning results
Each waiting call adds its own page.
1 → 2 → 3
A recursive call must return a result to its caller
For remaining > 0, return 1 + countPages(remaining - 1). The current call waits for the smaller call, then adds one. At zero, return 0 directly.
Supported inputs here are small nonnegative integers. A negative or fractional argument would not follow this decreasing-by-one path to exactly zero; validate it before using the recursive rule.
Before starting, review calls and returned values. These examples use JavaScript; other languages can use different syntax and rules.
Trace the calls and the final count
The log prints each argument as its call begins: 3, 2, 1, 0. The zero call returns immediately, then the waiting calls return 1, 2 and 3.
The final console.log displays the completed result 3. Calls and returns happen in different directions; the last output is not another recursive call.
JavaScript · local teaching example
function countPages(remaining) {
console.log(remaining);
if (remaining === 0) return 0;
return 1 + countPages(remaining - 1);
}
console.log(countPages(3));Expected output
3
2
1
0
3The same flat task can use a loop
Recursion is not required for a simple page count. This loop has a fixed bound and updates a total, producing the same result without a chain of function calls.
Recursion becomes especially natural for nested structures, such as a school folder containing subfolders. A flat counter is often simpler as iteration.
JavaScript · local teaching example
const pageCount = 3;
let reviewed = 0;
for (let page = 0; page < pageCount; page++) {
reviewed += 1;
}
console.log(reviewed);Expected output
3Apply the rule to a small change
Call a result-only recursive version with zero and two pages. Predict both outputs without logging every intermediate call.
Worked answer
Zero immediately returns zero. Two requires a chain through one and zero, then returns two. Removing diagnostic output does not change the count.
JavaScript · local teaching example
function countPages(remaining) {
if (remaining === 0) return 0;
return 1 + countPages(remaining - 1);
}
console.log(countPages(0));
console.log(countPages(2));Expected output
0
2Recognize mistakes and limits
A base case somewhere in the source is not enough: each supported input must reach it. A call with the same argument makes no progress; a wrong-direction update can move away from the exit.
Each active call uses execution resources. Deep recursion can exhaust the call stack, and JavaScript tail-call optimization is not portable enough to assume for this lesson. Use iteration or an explicit stack for large depths where needed.
For the language or tool rules used here, see JavaScript functions and scope.
Check the core idea
JavaScript · code for this question
function countPages(remaining) {
console.log(remaining);
if (remaining === 0) return 0;
return 1 + countPages(remaining - 1);
}
console.log(countPages(3));Apply the idea to a new situation
Check both the base case and progress toward it
A recursive function solves a smaller version and combines its returned result. Trace both directions, validate accepted input and consider the depth cost before choosing recursion.
Connect this idea with last-in-first-out pending work and iterative alternatives.
Reaching the recap and completing the quizzes are separate milestones.