C++ · Course navigation

C++ recursive factorial

Trace recursive calls and their return values.

On this page

Before you start

Functions and conditions.

Trace recursive calls and their return values.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1#include <iostream>

2#include <stdexcept>

3#include <cassert>

4unsigned 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}

9int 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

Prepared trace of the published program. Some rows group repeated iterations.
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

Behind the scenes

How C++ processes this code

The C++ compiler produces a native executable. Execution enters main, where objects and function calls perform the work.

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.