Python

Factorial in Python: Iterative, Recursive and math.factorial

Python · Published 2026-10-24

In real code, use math.factorial(n): it is exact, validates its input and is several times faster than anything you write by hand. If you need to implement it yourself, a simple for loop is the best choice; the recursive version is elegant but slower and fails beyond Python's recursion limit.

The factorial of a non-negative integer n, written n!, is the product 1 × 2 × … × n, with 0! defined as 1. All examples below were run on Python 3.13.

Iterative factorial

def factorial_iterative(n: int) -> int:
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

print([factorial_iterative(n) for n in range(8)])
print(factorial_iterative(20))

[1, 1, 2, 6, 24, 120, 720, 5040]
2432902008176640000

Starting the product at 1 handles both 0! and 1! without a special case, because range(2, 1) and range(2, 2) are empty. The loop uses constant stack space and works for any n that fits in memory.

Recursive factorial

The mathematical definition, n! = n × (n − 1)!, translates directly into recursion:

import sys

def factorial_recursive(n: int) -> int:
    if n <= 1:          # base case: 0! = 1! = 1
        return 1
    return n * factorial_recursive(n - 1)

print(factorial_recursive(10))
print(sys.getrecursionlimit())
try:
    factorial_recursive(5000)
except RecursionError as e:
    print("RecursionError:", e)

3628800
1000
RecursionError: maximum recursion depth exceeded

Each call adds a frame to the call stack, and CPython caps the depth at sys.getrecursionlimit(), 1000 by default. Since a few frames are already in use, the practical ceiling is slightly under 1000. Python does not perform tail-call optimization, so rewriting the function in tail-recursive style does not help.

You can raise the limit:

import sys

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

sys.setrecursionlimit(10_000)
print(len(str(factorial_recursive(1500))))

4115

Treat this as a workaround, not a fix. A very high limit can crash the interpreter with a real C stack overflow instead of a clean RecursionError, and it applies to the whole process. Recursion is worth knowing for teaching and for problems that are naturally recursive (trees, divide-and-conquer), but not for factorial in production.

The standard library: math.factorial

import math
from functools import reduce
from operator import mul

print(math.factorial(10))
print(reduce(mul, range(1, 11), 1))
print(reduce(mul, range(1, 1), 1))     # 0! with the initial value
print(math.prod(range(1, 11)))         # Python 3.8+

3628800
3628800
1
3628800

math.factorial is implemented in C with a divide-and-conquer algorithm that multiplies balanced halves of the product, which keeps the big-integer multiplications efficient. For large n it beats a Python loop by a wide margin (see the timings below).

functools.reduce(mul, range(1, n + 1), 1) is a functional one-liner; the initial value 1 is essential, otherwise reduce raises TypeError on the empty range for n = 0. math.prod expresses the same thing more readably. Related helpers in math: comb(n, k) and perm(n, k) compute binomial coefficients and permutations without building full factorials.

Memoization

If a program needs many factorials (for example in a combinatorics loop), caching avoids recomputing shared prefixes:

from functools import cache

@cache                       # Python 3.9+; use lru_cache(maxsize=None) before
def fact(n: int) -> int:
    return 1 if n <= 1 else n * fact(n - 1)

print(fact(100) % 1_000_007)
print(fact.cache_info())
print(fact(101) // fact(100))
print(fact.cache_info())

323756
CacheInfo(hits=0, misses=100, maxsize=None, currsize=100)
101
CacheInfo(hits=2, misses=101, maxsize=None, currsize=101)

After the first call, fact(101) needs just one new multiplication. Caveats: the cache keeps every result alive, and the factorials grow quickly (1000! is about 1 KB, 100,000! is about 190 KB), so an unbounded cache can use a lot of memory. The first call to a large uncached value still recurses and hits the recursion limit. An alternative is a precomputed table built iteratively, which is common in competitive programming together with modular arithmetic.

Input validation

Factorial is only defined here for non-negative integers. A hand-written function should reject everything else explicitly:

import math

def factorial(n):
    if isinstance(n, bool) or not isinstance(n, int):
        raise TypeError(f"factorial() expects an int, got {type(n).__name__}")
    if n < 0:
        raise ValueError("factorial() not defined for negative values")
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

for bad in (-3, 4.0, "5"):
    try:
        factorial(bad)
    except (TypeError, ValueError) as e:
        print(f"{bad!r}: {type(e).__name__}: {e}")

for bad in (-3, 4.0, "5"):
    try:
        math.factorial(bad)
    except (TypeError, ValueError) as e:
        print(f"math {bad!r}: {type(e).__name__}: {e}")
print(math.factorial(True))

-3: ValueError: factorial() not defined for negative values
4.0: TypeError: factorial() expects an int, got float
'5': TypeError: factorial() expects an int, got str
math -3: ValueError: factorial() not defined for negative values
math 4.0: TypeError: 'float' object cannot be interpreted as an integer
math '5': TypeError: 'str' object cannot be interpreted as an integer
1

Without validation, the naive loop silently returns 1 for negative numbers (the range is empty), and the recursive version does the same through its n <= 1 base case. Both are wrong answers rather than errors.

Version note: math.factorial(4.0) used to return 24. Accepting integral floats was deprecated in Python 3.9 and removed in 3.10, so it now raises TypeError. bool is a subclass of int, so math.factorial(True) returns 1; the custom function above rejects booleans deliberately. For a non-integer generalization, math.gamma(x + 1) gives the gamma function as a float.

Big integers

Python integers have arbitrary precision, so factorials never overflow as integers. They do grow very fast:

import math

big = math.factorial(1000)
print(big.bit_length())
print(len(str(big)))
print(str(math.factorial(25)))
print(float(math.factorial(170)))
try:
    float(math.factorial(171))
except OverflowError as e:
    print("OverflowError:", e)
print(math.lgamma(1001) / math.log(10))

8530
2568
15511210043330985984000000
7.257415615307999e+306
OverflowError: int too large to convert to float
2567.6046442221323

• 170! is the largest factorial representable as a 64-bit float; 171! overflows on conversion.
• For the magnitude of a huge factorial, use math.lgamma(n + 1), the natural log of n!. Dividing by log(10) gives the number of decimal digits minus a fraction (1000! has 2568 digits).
• Since Python 3.11, converting an int with more than 4300 digits to str raises ValueError as a denial-of-service safeguard. 2000! has 5736 digits:

import math, sys

n = math.factorial(2000)
try:
    s = str(n)
except ValueError as e:
    print("ValueError:", str(e)[:60], "...")
sys.set_int_max_str_digits(10_000)
print(len(str(n)))

ValueError: Exceeds the limit (4300 digits) for integer string conversio ...
5736

Raise the limit with sys.set_int_max_str_digits() (or the PYTHONINTMAXSTRDIGITS environment variable) only when you trust the input. Arithmetic on the integer itself is unaffected; only decimal string conversion is limited.

Timing comparison

The following script compares the approaches with timeit, taking the best of five repeats:

import math, sys, timeit
from functools import reduce
from operator import mul

sys.setrecursionlimit(5000)

def iterative(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

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

def with_reduce(n):
    return reduce(mul, range(1, n + 1), 1)

def with_prod(n):
    return math.prod(range(1, n + 1))

for n in (20, 500, 3000):
    assert iterative(n) == recursive(n) == with_reduce(n) == with_prod(n) == math.factorial(n)
    print(f"n = {n}")
    for f in (iterative, recursive, with_reduce, with_prod, math.factorial):
        number = 2000 if n <= 500 else 50
        t = min(timeit.repeat(lambda: f(n), number=number, repeat=5)) / number
        print(f"  {f.__name__:12s} {t*1e6:10.2f} µs")

Results on the container used to build this article (Python 3.13, microseconds per call). They are indicative: absolute numbers depend on your CPU and Python build, but the ranking is consistent.

For small n, function-call overhead dominates, so recursion is roughly twice as slow as the loop. For large n, the cost of multiplying ever-larger integers dominates and the pure-Python approaches converge, while math.factorial stays four to five times faster thanks to its balanced multiplication order.

Common pitfalls

• Forgetting the base case in the recursive version leads straight to RecursionError.
• Starting the product at 0 makes every result 0.
• Off-by-one ranges: range(1, n) computes (n − 1)!; the upper bound must be n + 1.
• No validation: negative inputs silently return 1 from naive implementations.
• Computing factorial(n) // (factorial(k) * factorial(n - k)) for combinations: use math.comb(n, k), which is faster and avoids huge intermediates.

Summary

Use math.factorial(n) whenever possible. If you must write your own, use an iterative loop starting at 1, validate that the input is a non-negative int, and avoid recursion for anything beyond small inputs because of the default limit of 1000 frames. Add functools.cache when you need many related factorials, use math.lgamma to estimate sizes, and remember the 4300-digit string conversion limit introduced in Python 3.11.

Read next

More in Python

Python

Random integers

Generate random integers in Python with random.randint, randrange, sample, secrets.randbelow and NumPy's rng.integers, plus seeding, uniqueness and speed.

Python

Trigonometric functions

Use math.sin, cos, tan, atan2 and hypot correctly in Python: radians vs degrees, inverse function ranges, float rounding, NumPy vectorization and cmath.

Python

Nested dictionary values

Get values from nested dictionaries in Python: chained indexing, safe .get() chains, a deep_get helper, lists in dicts, recursion, json_normalize and glom.