Here's the complete recursive factorial function:
plaintext function factorial(n) if n = 0 then return 1 return n × factorial(n - 1)
Check the base case first: if , return . Otherwise, you multiply by factorial(n - 1). For factorial(5), the function calls factorial(4), which calls factorial(3), down to factorial(0), which returns . Then the results multiply back up: .
Time complexity: since you make recursive calls. Space complexity: 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? the call stack.