A girl and a robot thinking together

Think together · Start with a little story

How many ways can three different toys be lined up? There are 3 choices for the first spot, then 2, then 1.

Lay out the process

Follow the steps, then explain them in your own words
  1. 3!3 times 2!
  2. 2!2 times 1!
  3. 1!1 times 0!
  4. 0! = 1Return to get 1, 2, 6

The factorial n! is the product of the integers from 1 to n, with 0! defined as 1.

Recursion expresses this as n! = n × (n−1)!, making the task smaller at each step. The result of 3! is 6.

See both the calls and the returns

The task cards go from the bottom of the stack on the left to the top on the right. The rightmost card is the call currently running.

Step 1 · Enter factorial(3)
f(3)

This call must compute 3 × f(2), so it waits for f(2).

Step 2 · Enter factorial(2)
f(3) waitingf(2)

This call must compute 2 × f(1), so it adds another call.

Step 3 · Continue to the base case
f(3) waitingf(2) waitingf(1) waitingf(0) = 1

f(0) returns 1 directly, without adding another call.

Step 4 · Return to factorial(1)
f(3) waitingf(2) waitingf(1) = 1

Compute 1 × 1, get 1, and return.

Step 5 · Return to factorial(2)
f(3) waitingf(2) = 2

Compute 2 × 1, get 2, and return.

Step 6 · Return to factorial(3)
f(3) = 6

Compute 3 × 2, get 6. This call is complete.

01What is a factorial?

The factorial of a positive integer is written n!:

4! = 4 × 3 × 2 × 1 = 24

By definition:

0! = 1

02Why does a factorial naturally use recursion?

Because:

n! = n × (n - 1)!

For example:

4!=4 × 3!=4 × 3 × 2!

03How do you write the recursive code?

long long factorial(int n) {
    if (n == 0) {
        return 1;
    }

    return n * factorial(n - 1);
}

This assumes that the input satisfies n >= 0.

04How does factorial(4) call downward?

factorial(1)factorial(2)factorial(3)factorial(4)

It continues until factorial(0). That call stops recursing and returns 1 directly.

05How does the answer come back step by step?

0! = 1↑1! = 1 × 1 = 1↑2! = 2↑3! = 6↑4! = 24

06Why must you consider the input range?

If you pass a negative number, the function keeps going to -1, -2, -3, ... and never reaches 0.

A real program should define the function’s valid inputs or check them explicitly.

07Can long long calculate very large factorials?

It cannot grow without limit.

A typical 64-bit long long can safely represent values only up to 20!; 21! already exceeds the maximum signed 64-bit integer.

08Must you use recursion for factorials?

No. You can also use a loop:

long long result = 1;

for (int i = 2; i <= n; i++) {
    result *= i;
}

Factorials are mainly useful for learning recursive structure; recursion is not necessarily the best implementation.

What have you learned?

  • A factorial follows n! = n × (n-1)!.
  • 0! = 1 can be the base case.
  • Recursive calls decrease n one step at a time, then multiply as they return.
  • A function must account for its valid input range.
  • Factorials grow quickly, so even long long overflows soon.
  • You can also calculate a factorial with a loop.

Next: Solving Smaller Problems with Recursion

Your turn to try

Why would defining 0! as 0 make all the answers above it incorrect?

Ready? Open to see the explanation

Every level multiplies by the next level’s result. Multiplying by 0 would make every result 0. The correct starting value for multiplication is 1.