Factorial using Recursion

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

With the special base cases:

0! = 1
1! = 1

Recursive Definition

We can define Factorial mathematically in a clean recursive format:

Base Case

If N <= 1, Factorial(N) = 1

Recursive Case

If N > 1, Factorial(N) = N × Factorial(N - 1)

For example, to calculate 4!:

4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1 (Base case reached)

Now, we substitute values back up:

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

The Call Stack in Memory

When a recursive function calls itself, the computer cannot finish the current function call until the inner call finishes. Therefore, the active call is suspended, and its state (local variables, parameters, and return address) is saved in an area of memory called the Call Stack as an Activation Record (Stack Frame).

Winding Phase (Push): Function calls are pushed onto the Call Stack one by one until the Base Case is met.
Unwinding Phase (Pop): Once the base case returns a value, the stack frames are popped off the stack one by one, substituting values back into the expression.

If a recursive function lacks a base case or has an incorrect base case, the recursion continues infinitely, eventually filling up the stack space. This critical runtime error is called a Stack Overflow.

Complexity Analysis

Time Complexity: O(N) since we perform exactly N recursive calls, and each call takes constant O(1) time.
Space Complexity: O(N) because of the Call Stack memory usage. At the deepest level of recursion, there are N frames stored concurrently on the Call Stack.