Factorial - Implementation

Here's the complete recursive factorial function:

function factorial(n)
    if n = 0 then
        return 1
    return n × factorial(n - 1)

Check the base case first: if $n = 0$, return $1$. Otherwise, you multiply $n$ by factorial(n - 1). For factorial(5), the function calls factorial(4), which calls factorial(3), down to factorial(0), which returns $1$. Then the results multiply back up: $1 \times 1 \times 2 \times 3 \times 4 \times 5 = 120$.

Time complexity: $O(n)$ since you make $n$ recursive calls.

Space complexity: $O(n)$ due to the call stack depth.

Before moving on, try to trace factorial(3) yourself. How many function calls happen? What value does each one return?