Calculate the Factorial of a Number
The first recursive function most programmers ever write — and the one that quietly teaches stack limits, big-integer arithmetic, and why iteration sometimes wins.
- What a factorial is, and where it comes from
- The recursive definition
- The iterative version — and why it scales better
- Code in Python, C, and Haskell
- The growth problem: factorials get huge fast
- Stack depth, overflow, and other failure modes
- Where factorials actually get used
What a factorial is, and where it comes from
The factorial of a non-negative integer n, written n!, is the product of every positive integer from 1 up to n. So 5! is 5 × 4 × 3 × 2 × 1, which works out to 120. By convention, 0! is defined as 1 — not because multiplying nothing gives 1 in any literal sense, but because that definition keeps a whole family of combinatorics formulas consistent without special-casing zero everywhere.
Factorials show up first in counting problems: the number of distinct ways to arrange n distinct objects in a row is exactly n!. Shuffle five cards, and there are 120 possible orderings. For programmers, the factorial function earns its place in almost every introductory course as the simplest possible example of a function defined in terms of a smaller version of itself — the canonical first lesson in recursion.
The recursive definition
Written directly from the mathematical definition, the recursive version reads almost like the formula itself: a base case that stops the recursion, and a recursive case that reduces the problem by one step each time.
def factorial(n): if n < 0: raise ValueError("factorial undefined for negative numbers") if n == 0: return 1 return n * factorial(n - 1)
This is the version most people meet first, and it’s a genuinely good way to learn what recursion looks like: each call hands off a slightly smaller problem to itself, and the chain of calls eventually bottoms out at the base case, after which every pending multiplication gets resolved on the way back up.
The catch is that this elegance has a cost. Every recursive call needs its own stack frame. Calling factorial(100000) in a language without special handling for this pattern will exhaust the call stack and crash with a stack overflow long before the arithmetic itself becomes the bottleneck.
The iterative version — and why it scales better
An iterative implementation computes the exact same product, but using a loop and a running total instead of a chain of function calls. No call stack grows; only a couple of local variables exist at any moment, no matter how large n gets.
unsigned long long factorial(unsigned int n) { unsigned long long result = 1; for (unsigned int i = 2; i <= n; i++) { result *= i; } return result; }
This version trades a small amount of conceptual elegance for a large amount of robustness. There’s no stack depth to worry about, the memory footprint is constant regardless of n, and most compilers can optimize the simple multiply-and-loop pattern very efficiently. For any factorial implementation expected to run in production, the iterative form is almost always the right default.
A functional perspective: Haskell
Languages built around recursion as a first-class tool handle the recursive definition more gracefully. Haskell’s pattern-matching syntax lets the base case and recursive case sit side by side almost exactly as they would in a math textbook.
-- pattern matching replaces the explicit if/else entirely
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)
Two things are worth noticing here. First, the type signature declares Integer rather than a fixed-width integer type — Haskell’s Integer type grows arbitrarily large automatically, which matters enormously for factorials since the values explode in size almost immediately. Second, the factorial function as written above isn’t quite in tail position, since the multiplication happens after the recursive call returns — a useful detail to notice when learning which recursive functions get tail-call elimination for free and which don’t.
The growth problem: factorials get huge, fast
Factorials grow faster than almost any other common function in programming. 10! is 3,628,800 — already in the millions. 20! is roughly 2.43 × 10¹⁸, a number that approaches the limit of a standard 64-bit unsigned integer. 100! has 158 digits. Any factorial implementation meant for inputs larger than roughly 20 needs to make a deliberate choice about how to represent numbers that large.
| n | n! | Fits in 64-bit unsigned? |
|---|---|---|
| 10 | 3,628,800 | Yes |
| 15 | 1,307,674,368,000 | Yes |
| 20 | 2,432,902,008,176,640,000 | Yes, barely |
| 21 | 51,090,942,171,709,440,000 | No — overflows |
| 50 | 30,414,093,…,000,000 (65 digits) | No |
Stack depth, overflow, and other failure modes
- Negative input. Factorial is undefined below zero; decide whether your function raises an error, returns a sentinel, or asserts — and be consistent about it.
- Recursion depth limits. Many languages cap recursion depth defensively — Python’s default is a few thousand frames. A recursive factorial called with a large enough
nwill hit that ceiling before it hits any arithmetic problem. - Integer overflow that doesn’t crash. In C and similar languages, overflow on multiplication silently wraps around rather than raising an error, producing a confidently wrong number instead of a visible failure — arguably worse than a crash.
- Using the wrong tool for huge magnitudes. If a caller only needs to compare the relative size of two factorials, or needs the number of digits, computing the logarithm via Stirling’s approximation is far cheaper than computing the full big-integer value.
Where factorials actually get used
Beyond the classroom, factorials underpin combinatorics-heavy code: computing probabilities in card games, calculating the number of possible bracket arrangements in a tournament, or working out binomial coefficients for statistics and machine learning. The binomial coefficient formula — “n choose k” — is built directly from three factorial calculations divided against each other, and shows up constantly in probability calculations and combinatorial optimization.
Factorials also appear inside numerical methods. The Taylor series expansions used to approximate functions like sine, cosine, and the exponential function all divide each term by a growing factorial in the denominator — which is precisely why those series converge: the factorial in the denominator eventually grows faster than the numerator, shrinking each successive term toward zero.