What is Factorial?
The factorial of a non-negative integer $N$ (denoted as $N!$) is the product of all positive integers less than or equal to $N$.
N! = N * (N - 1) * (N - 2) * ... * 1
Factorial naturally lends itself to recursion because it can be defined in terms of a smaller sub-problem:
- Base Case: $1! = 1$ and $0! = 1$. The recursion stops here.
- Recursive Case: $N! = N \times (N-1)!$. The function calls itself with $N-1$.
Trace of fact(3)
When we call fact(3), the execution builds up stack frames and then resolves back down:
fact(3)is called. Since $3 > 1$, it spawnsfact(2)and waits.fact(2)is called. Since $2 > 1$, it spawnsfact(1)and waits.fact(1)is called. Since $1 \le 1$, the base case is met. It returns 1.fact(2)receives 1, calculates $2 \times 1 = 2$, and returns 2.fact(3)receives 2, calculates $3 \times 2 = 6$, and returns 6.
Complexity Analysis
Time Complexity: O(N)
The function calls itself $N$ times, performing a constant amount of work (comparison and multiplication) in each call.
Space Complexity: O(N)
Since it pushes $N$ stack frames onto the Call Stack before popping them during the return phase, it requires $O(N)$ auxiliary stack memory.