Factorial using recursion in Python

A recursive function is a function that calls itself. Factorial fits this well, because n! = n × (n - 1)!. For example, 5! = 5 × 4!.

The program

def factorial(n):
    if n < 0:
        raise ValueError("factorial is not defined for negative numbers")
    if n <= 1:
        return 1
    return n * factorial(n - 1)


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

0! = 1
1! = 1
5! = 120
10! = 3628800

How it works

• if n <= 1: return 1 is the base case. It stops the function from calling itself forever. Both 0! and 1! are 1.
• return n * factorial(n - 1) is the recursive call. Each call works on a smaller number, so the calls always reach the base case.
• For factorial(4), Python calculates 4 * factorial(3), which needs 3 * factorial(2), which needs 2 * factorial(1). factorial(1) returns 1, and then the waiting calls finish in reverse order: 2, 6, 24.

The recursion limit

Every call that is still waiting uses memory. To protect the program, Python stops after about 1,000 nested calls and raises a RecursionError:

import sys


def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)


print("Limit:", sys.getrecursionlimit())

try:
    factorial(5000)
except RecursionError:
    print("factorial(5000) failed: too many nested calls")

Limit: 1000
factorial(5000) failed: too many nested calls

For large numbers, use the loop version or math.factorial(). Both work for 5000 without any problem. Recursion is still worth learning, because some problems (trees, folders inside folders) are much easier to write with it.