Factorial of a Number

Problem Statement

Compute the factorial of a non-negative integer n, denoted as n!, which is the product of all positive integers less than or equal to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120. This is an easy-level problem that introduces recursion by breaking down the problem into smaller subproblems (n! = n × (n-1)!), with a base case of 0! = 1. It’s a classic starting point for understanding recursive thinking!

Example

Input: n = 5

Output: 120 (5 × 4 × 3 × 2 × 1 = 120)

Input: n = 0

Output: 1 (by definition, 0! = 1)

Input: n = 3

Output: 6 (3 × 2 × 1 = 6)

Code

public class Solution {
    public int factorial(int n) {
        if (n < 0) return -1; // Invalid input
        if (n == 0 || n == 1) return 1; // Base cases
        return n * factorial(n - 1); // Recursive step
    }
}
            

def factorial(n):
    if n < 0:
        return -1  # Invalid input
    if n == 0 or n == 1:
        return 1   # Base cases
    return n * factorial(n - 1)  # Recursive step

# Example usage
print(factorial(5))  # 120
print(factorial(0))  # 1
print(factorial(3))  # 6
            

function factorial(n) {
    if (n < 0) return -1; // Invalid input
    if (n === 0 || n === 1) return 1; // Base cases
    return n * factorial(n - 1); // Recursive step
}

// Example usage
console.log(factorial(5)); // 120
console.log(factorial(0)); // 1
console.log(factorial(3)); // 6
            

Explanation

• Base Case: If n is 0 or 1, return 1, as these are the smallest factorials defined.
• Recursive Case: For n > 1, compute n × factorial(n-1), reducing the problem size by 1 each time.
• Flow Example (n=3): factorial(3) → 3 × factorial(2) → 3 × (2 × factorial(1)) → 3 × (2 × 1) → 3 × 2 → 6.
• Termination: The recursion stops when it hits the base case, unwinding the call stack to produce the result.
• Edge Case: Handle negative inputs by returning an error or invalid indicator (e.g., -1).

Note