C++ recursive factorial
Trace recursive calls and their return values.
C++
#include <iostream>
#include <stdexcept>
#include <cassert>
unsigned long factorial(int n) {
if (n < 0 || n > 12) throw std::out_of_range("use 0 through 12");
if (n == 0) return 1;
return static_cast<unsigned long>(n) * factorial(n - 1);
}
int main() {
std::cout << factorial(4) << '\n';
assert(factorial(0) == 1);
}Output
24
Explanation
Recursion needs a base case and progress toward it. The function accepts 0 through 12, keeping the result within the minimum range guaranteed for unsigned long.
Each non-base call waits for the next call, then multiplies on the return path. Invalid input throws rather than silently overflowing this example's chosen bound.
Explore the dry run
Guided walkthroughReady
1
#include <iostream>2
#include <stdexcept>3
#include <cassert>4
unsigned long factorial(int n) {5
if (n < 0 || n > 12) throw std::out_of_range("use 0 through 12");6
if (n == 0) return 1;7
return static_cast<unsigned long>(n) * factorial(n - 1);8
}9
int main() {10
std::cout << factorial(4) << '\n';11
assert(factorial(0) == 1);12
}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Start factorial(4). | calls: 4 | — | |
| Descend through 3, 2, 1, and 0. | calls: 4 -> 3 -> 2 -> 1 -> 0 | — | |
| Return the base value. | factorial(0) = 1 | — | |
| Unwind with products 1, 2, 6, and 24. | factorial(4) = 24 | — | |
| Print the result. | factorial(4) = 24 | 24 |
Cost and common mistakes
O(n) calls and O(n) stack space within the accepted range.
- A fixed-width integer cannot store arbitrarily large factorials.
- The exception is not caught in this small program; invalid input would terminate unless the caller handles it.
Try it yourself
Evaluate factorial(5) and factorial(0).
Reveal answer and reasoning
They return 120 and 1.