Factorial

Problem Statement

Compute the factorial of a non-negative integer n, i.e., n! = n × (n-1) × ... × 1.

Example: Input: n = 5 → Output: 120

Approach 1: Simple Recursion

Explanation: Multiply n with factorial of (n-1) until base case 0! = 1.

Time Complexity: O(n)

Space Complexity: O(n) (call stack)

function factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n-1)

Approach 2: Iterative

Explanation: Use a loop to multiply numbers from 1 to n.

Time Complexity: O(n)

Space Complexity: O(1)

fact = 1
for i from 2 to n:
    fact = fact * i
return fact

Approach 3: Using Memoization (for repeated calls)

Explanation: Store computed factorials to avoid recomputation.

Time Complexity: O(n) overall

Space Complexity: O(n) (stack + memo)

memo = {}
function factorial(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return 1
    memo[n] = n * factorial(n-1)
    return memo[n]