Recursive factorial

Write a recursive factorial function.

Iterative solution

Factorial can also be computed with a loop: multiply numbers from 1 to n. This uses less memory than recursion.

The iterative solution requires O(n) time and O(1) memory. The recursive solution requires O(n) time and O(n) memory (stack).

Recursive vs iterative

Recursive factorial is more readable but each call uses stack space. The iterative solution is more efficient but less elegant.

For small n, both methods are fast. For large n, iterative is preferred because there is no stack overflow risk.

Exercise Iterative factorial

Write factorial_iter(n). Multiply from 1 to n with a loop. Print 120 with print(factorial_iter(5)).

Show example solution

def factorial_iter(n):
    # Factorial with loop
    result = 1
    for i in range(1, n + 1):
        result = result * i
    return result
print(factorial_iter(5))

Test yourself

Iterative product

To accumulate the result, start with ____ = 1.

Show answer

To accumulate the result, start with result = 1.

Recursive factorial: match the terms

Recursive

Uses stack
Iterative

O(1) memory
0! = 1

Base
n! = n*(n-1)!

Recursive
How much memory does iterative factorial use?
- O(1)
- O(n^2)
- O(n)
- O(2^n)
Show answer

O(1) — Iterative factorial uses O(1) memory.

Next lesson: Choosing the base case

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies