Factorial

阶乘

≈ 15 min · python-recursion · Open in WolfCode

The most-quoted recursion in computer science. Two-line body, induction-style correctness.

Python · runnable

def factorial(n):
    if n == 0:
        return 1                       # base case
    return n * factorial(n - 1)        # recursive case

for x in [0, 1, 5, 6, 10]:
    print(f"factorial({x}) = {factorial(x)}")

Loading Python runtime (~5 MB, one-time)…

Trace once, for understanding

factorial(3)        → 3 * factorial(2)
  factorial(2)      → 2 * factorial(1)
    factorial(1)    → 1 * factorial(0)
      factorial(0)  → 1                          ← BASE
    factorial(1)    → 1 * 1 = 1
  factorial(2)      → 2 * 1 = 2
factorial(3)        → 3 * 2 = 6