Course contentsShow
← Computer Science
Lesson 221 of 2,8725. Functions and ModularityFree lesson

Computing Factorials Recursively

Write a recursive factorial function and trace its execution through multiple stack frames.

Computing Factorials Recursively

You'll learn how to write a recursive factorial function and follow its execution through the call stack.

The Core Idea

A factorial (written as n!) is the product of all positive integers from 1 to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120. We can express this recursively: n! = n × (n-1)!, with the base case 1! = 1.

Think of it like a Russian nesting doll: to find 5!, you need 4!. To find 4!, you need 3!, and so on, until you reach 1!, which you know is just 1. Then you work backward, multiplying as you go.

The Recursive Function

def factorial(n):
    if n == 1:           # Base case
        return 1
    else:                # Recursive case
        return n * factorial(n - 1)

Tracing the Execution

Let's trace factorial(4) through the stack:

  1. Call factorial(4) → needs 4 × factorial(3)
  2. Call factorial(3) → needs 3 × factorial(2)
  3. Call factorial(2) → needs 2 × factorial(1)
  4. Call factorial(1) → base case! returns 1
  5. Return to factorial(2) → computes 2 × 1 = 2, returns 2
  6. Return to factorial(3) → computes 3 × 2 = 6, returns 6
  7. Return to factorial(4) → computes 4 × 6 = 24, returns 24

Each function call waits in memory (on the stack) until the deeper call finishes. They unwind in reverse order, each multiplying its result.

Key Takeaway: A recursive factorial breaks the problem into smaller subproblems until hitting the base case, then combines results as the stack unwinds—illustrating how recursion naturally handles problems defined in terms of themselves.