Recursion needs a smaller problem
Trace recursive calls through base cases, progress, stack frames, factorial, and Fibonacci limitations.
After this lesson
You should be able to
- Identify a base case and prove that each call moves toward it.
- Explain repeated work and stack-depth costs in naive recursion.
Base case plus progress
A recursive function calls itself on a smaller instance. It needs a base case that returns directly and a recursive step that must move toward that case. Without both, recursion can continue until stack space is exhausted.
Each active call has a stack frame containing its parameters and local state. For factorial(4), calls wait for factorial(3), then 2, then 1; results return in reverse order.
unsigned long long factorial(unsigned int n) {
if (n <= 1u) {
return 1u;
}
return n * factorial(n - 1u);
}Elegant does not mean efficient
Naive recursive Fibonacci calls fib(n - 1) and fib(n - 2), recomputing the same values many times. The call tree grows exponentially, while an iterative solution keeps only the previous two values and runs in linear time.
Use recursion when the problem is naturally recursive and depth is controlled. Prefer iteration when it expresses the same process more clearly or avoids unnecessary stack and repeated-work costs.
Try it yourself
Trace factorial(4) and list the return values as calls unwind.
Need a hint?
The base returns 1, then multiply by 2, 3, and 4.
Check the worked solution
factorial(1)=1, factorial(2)=2, factorial(3)=6, factorial(4)=24.
Quick check
What two properties are essential for terminating recursion?
Why this lesson exists
Syllabus mapping
Recursion · Factorial · Fibonacci · Limitations of recursion
Maps to course outcomes CO1, CO3, CO4.