• 0 <= n <= 12
• n is an integer
• 12! = 479001600 still fits in a 32-bit signed integer; beyond that it overflows

Factorial asks for a simple product: 5! means 5 × 4 × 3 × 2 × 1 = 120. You could stop reading and write a loop. But this problem is the doorway to recursion, a way of solving a problem by having it solve a smaller version of itself, so we will use it to build the whole mental model from scratch — the pieces here reappear in trees, sorting, backtracking, and dynamic programming.

The obvious way is to walk from 1 to n and keep multiplying:

result = 1
for i in range(2, n + 1):
    result *= i
return result

Nothing is wrong with this. It is O(n) time and uses no extra memory. Keep it in mind as the honest baseline — recursion will not make factorial faster. What recursion gives us is a different way of thinking that pays off on problems a loop cannot express cleanly.

Look at the definition again and notice the self-similarity hiding in it:

5! = 5 × (4 × 3 × 2 × 1) = 5 × 4!

The parenthesized part is 4!. In general, n! = n × (n − 1)!. The problem contains a smaller copy of itself. That is the signal for recursion: whenever the answer for n can be built from the answer for something smaller than n, you can write a function that calls itself.

Two things must be true for this to actually terminate, and they are the two halves of every recursive function:

def factorial(n):
    if n <= 1:            # base case: smallest answerable input
        return 1
    return n * factorial(n - 1)   # recursive case: shrink toward the base

The hardest part for a beginner is the line return n factorial(n - 1). It seems to use the answer before we have computed it. The trick is to trust the smaller call: assume* factorial(n − 1) already returns the correct value, and your only job is to use it correctly for n. You do not trace the whole thing in your head — you check two things and stop: (1) does the base case return the right answer, and (2) if the smaller call is correct, is my combination correct? If both hold, the function is correct for every n by induction, the same domino logic as mathematical proof: the base case knocks over the first domino, and the recursive case guarantees each domino knocks over the next.

"Faith" is really bookkeeping, and the bookkeeper is the call stack. Every time a function is called, the computer pushes a frame onto the stack holding that call's own local variables and its unfinished work — for factorial, the frame remembers "I still owe a multiplication by n once the smaller call comes back." The frame waits, frozen, until the call it is waiting on returns. Frames pile up on the way down and unwind on the way back up:

The stack is why recursion costs O(n) space here even though the loop cost none: at the deepest point, n frames are stacked at once. Push n too high and you get a stack overflow — the stack runs out of room. That is the price of the cleaner formulation, and the reason deep recursions are sometimes rewritten as loops.

Every recursive solution you will ever write fills the same three slots:

Solving a new recursive problem is nothing more than deciding those three things. Recognition signals for reaching for recursion: the problem is defined in terms of itself (n! uses (n−1)!), or it branches into sub-problems (explore left and right, try each choice), or it lives on a naturally recursive structure (a tree, a nested list). The two ways it breaks — and the two bugs to check first — are a missing or wrong base case (infinite recursion → stack overflow) and a recursive call that does not strictly shrink the input (so the base case is never reached). Train the reflex: before writing the recursive line, write the base case, and make sure every call moves toward it. Everything after this — linear recursion on a single call (Sum of Digits), binary recursion that branches (Fibonacci), and divide-and-conquer that halves (Power) — is this same skeleton with different slots filled.