Write a recursive function that returns n! (n factorial), the product of all
integers from 1 to n. By definition 0! = 1.
factorial(n)
Assume n >= 0.
factorial(5) // → 120 (5 × 4 × 3 × 2 × 1)
factorial(1) // → 1
factorial(0) // → 1
Factorial's own definition is already recursive: n! is n times (n-1)!, all the way down to 0! = 1. Spotting that a problem's definition refers to a smaller version of itself is often the fastest way to see that recursion is the natural tool — you're translating a definition you already have, not inventing one.
By definition, 0! is 1 (there's exactly one way to arrange zero items). So when n reaches 0, return 1 immediately. That base case alone is enough — you don't need a separate check for n == 1, since factorial(1) correctly computes 1 * factorial(0) = 1 once the recursion gets there.
For any n greater than 0, trust that factorial(n-1) correctly returns (n-1)!. Given that, n! is just n times it — you supply the one new factor and let the recursive call handle the rest. That's exactly the definition: n! = n × (n-1)!.
Calling factorial(5) calls factorial(4), then factorial(3), factorial(2), factorial(1), factorial(0). Only factorial(0) resolves immediately, returning 1 — five frames deep, the bottom of the stack. The multiplications happen on the way back up: factorial(1) returns 1 × 1 = 1. factorial(2) returns 2 × 1 = 2. factorial(3) returns 3 × 2 = 6. factorial(4) returns 4 × 6 = 24. factorial(5) returns 5 × 24 = 120. Each frame waits, holding its own n, until the base case supplies the first real value to multiply against.
A loop multiplying a running product from 1 to n does the same work in O(1) extra space instead of O(n) stack frames, and in practice is the more efficient choice here. But writing it recursively is good practice: when a problem's definition already refers to a smaller version of itself, that reference usually translates almost directly into a base case and a recursive case. That skill carries over to problems — tree recursion, backtracking — where there's no simple loop equivalent, and recursion isn't just an option, it's the cleanest approach.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.