Optional: recursion and pending work
Trace a base case, the return journey, total calls, and peak call depth.
A smaller problem and a stopping case
Recursion means a function calls itself directly or indirectly. For factorial, 0! = 1 is the base case and n! = n × (n − 1)! supplies a smaller problem. Every recursive step must move toward a base case under the stated input domain.
factorial(3) waits for factorial(2), which waits for factorial(1), which waits for factorial(0). The results then return as 1, 1, 2, and 6. Each unfinished call has its own n and local state.
// Complete C++23 program. Input: 0 <= n <= 20.
#include <iostream>
long long factorial(int n) {
if (n == 0) return 1;
long long smaller = factorial(n - 1);
return n * smaller;
}
int main() {
int n = 0;
std::cin >> n;
std::cout << factorial(n) << '\n';
}Time and simultaneous calls answer different questions
Factorial makes n + 1 calls including its base case, so time is O(n + 1). Up to n + 1 calls can be pending together, giving O(n + 1) auxiliary space in the ordinary call-stack model. An iterative factorial uses a running product and O(1) auxiliary space.
The call stack models pending function work; C++ does not mandate a particular physical stack layout or promise elimination of recursion. Code after a recursive call runs on the return journey, not before the smaller call finishes.
Branching can repeat work
Naive Fibonacci computes F(n − 1) and F(n − 2) independently. For F(5), F(3) is recomputed in separate branches. A valid upper bound is O(2ⁿ) time, but this is not a claim that Θ(2ⁿ) is the tight bound or that the exact call count is 2ⁿ.
Only one branch executes at a time, so peak pending depth is linear, not exponential. A missing base case, a recursive call with the same positive input, or an out-of-domain negative input can break termination.
Value or reference?
The helper executes x += 10. Compare the caller’s value before and after the call.
The parameter is a copy. Changing it leaves the caller’s variable untouched.
Guided simulation · Change the inputs to test your understanding.
Why can naive recursive Fibonacci have exponential total work but only linear peak call depth?
Turn the idea into code
A helper prints n, recursively processes n − 1, then prints n again. It returns immediately for zero. Predict the output for n = 3 and implement it for 0 ≤ n ≤ 20.
Give me a hint
Write a separate line for each unfinished call. The second print waits for the smaller call to return.
Show the explained solution
The output is 3, 2, 1, 1, 2, 3 on separate lines. There are n + 1 calls and 2n output lines, so time and ordinary call-stack space are O(n + 1). For zero, it prints no lines.
// Complete C++23 program. Input: 0 <= n <= 20.
#include <iostream>
void downAndUp(int n) {
if (n == 0) return;
std::cout << n << '\n';
downAndUp(n - 1);
std::cout << n << '\n';
}
int main() {
int n = 0;
std::cin >> n;
downAndUp(n);
}Your notes
Mark complete when you can explain it yourself.