Find the Factorial of a Number using Recursion

The factorial rule becomes one smaller recursive call

The factorial of 5 is written as 5!, and its product is 5 * 4 * 3 * 2 * 1. The same product can be described using a smaller factorial: 5! = 5 * 4!. For any positive n, factorial(n) is n multiplied by factorial(n - 1). That rule becomes a recursive call because the function asks for the factorial of one smaller value.

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

static int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

When factorial(5) reaches the return statement, n is 5 and the smaller call is factorial(4). The expression therefore matches 5! = 5 * 4!. The current value of n does not disappear while the smaller call runs. The function keeps the multiplication waiting until factorial(4) produces its result.

Returning 1 at factorial(0) stops the descent without changing the product

The calls for factorial(5) use smaller arguments in this order: factorial(5), factorial(4), factorial(3), factorial(2), factorial(1), and factorial(0). At factorial(0), the base case returns 1 instead of making another recursive call. This is the stopping point that prevents the arguments from continuing below zero.

The base case returns 1 because 1 is the multiplicative identity. The pending expression at factorial(1) is 1 * factorial(0). If factorial(0) returns 1, that product stays equal to 1, so the earlier factors are preserved. Returning 0 would erase the entire product, while making another call would never reach a stopping point.

factorial(5) waits for 5 * factorial(4)
factorial(4) waits for 4 * factorial(3)
factorial(3) waits for 3 * factorial(2)
factorial(2) waits for 2 * factorial(1)
factorial(1) waits for 1 * factorial(0)
factorial(0) returns 1

The multiplications finish only while the calls return

The downward sequence only creates pending expressions. It does not yet multiply 5 by 4, or 4 by 3. Each call must first receive the result of its smaller recursive call. Once factorial(0) returns 1, the waiting calls resolve in reverse order, so the first multiplication to finish is at factorial(1), not at factorial(5).

Downward calls:
factorial(5) -> factorial(4) -> factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)

Upward returns:
factorial(0) returns 1
factorial(1) returns 1 * 1 = 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24
factorial(5) returns 5 * 24 = 120

At factorial(3), the multiplication is still pending until factorial(2) returns 2. Then factorial(3) computes 3 * 2 and returns 6 to factorial(4). Only after that does factorial(4) compute 4 * 6 and return 24. Finally, factorial(5) computes 5 * 24 and returns 120. The belief that 5 is multiplied during the descent is wrong, because factorial(5) has no result from factorial(4) yet.

factorial(4) = 4 * factorial(3)

One call per reduced value makes factorial linear in time and stack space

Each non-base call reduces n by one and does constant work besides its recursive call. That gives the recurrence T(n) = T(n - 1) + O(1). For factorial(5), the calls use the six values 5, 4, 3, 2, 1, and 0, so the work grows with the number of values from n down to 0.

The time complexity is O(n), because there is one call for each reduced value and one multiplication for each positive value. The call stack also holds one frame for each active call during the descent. For a general non-negative n, the auxiliary stack space is O(n). The returned integer itself is not extra stack space, but the pending calls are.