Recursion Factorial

Write a function factorial(n) that returns $n!$ (n factorial). $n! = n \times (n-1) \times (n-2) \times \cdots \times 1$. By definition, $0! = 1$. Input: 5 → Output: 120. You must use recursion — no for or while loops allowed.

Recursion breaks a problem into smaller versions of itself. Factorial has a natural recursive definition: $n! = n \times (n-1)!$. The base case is $0! = 1$. Each recursive call reduces $n$ by 1, and results multiply on the way back up the call stack.

1. Base case: if $n = 0$, return 1.
2. Recursive case: return $n \times \text{factorial}(n - 1)$.
3. Validate: raise an error for negative numbers (factorial is undefined for $n < 0$).

• Forgetting the base case ($n = 0$), causing infinite recursion and a stack overflow
• Using $n = 1$ as the base case, which makes factorial(0) recurse infinitely
• Not handling negative inputs (factorial undefined for $n < 0$)
• Confusing recursion depth with time complexity — they are both $O(N)$ here

Factorial is the "Hello World" of recursion. It teaches the two essential components: a base case that stops recursion, and a recursive case that reduces the problem. Watch out for Python's default recursion limit of 1000 for large $N$.