Python recursion and factorial
Separate a base case from a smaller recursive problem.
Python
def factorial(n):
if n < 0:
raise ValueError("n must be nonnegative")
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
assert factorial(0) == 1
assert factorial(1) == 1Output
24
Explanation
A recursive function calls itself with a smaller problem. The base case stops recursion; without it, calls continue until the runtime recursion limit is reached.
For a nonnegative integer n, factorial(n) is n times factorial(n-1), with factorial(0) = 1. Each call waits for its child before multiplying.
Explore the dry run
Guided walkthroughReady
1
def factorial(n):2
if n < 0:3
raise ValueError("n must be nonnegative")4
if n == 0:5
return 16
return n * factorial(n - 1)7
8
print(factorial(4))9
assert factorial(0) == 110
assert factorial(1) == 1Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Call factorial(4). | stack: f(4) | — | |
| Calls descend with n = 3, 2, 1, then 0. | stack: f(4), f(3), f(2), f(1), f(0) | — | |
| The base case returns 1. | f(0) = 1 | — | |
| Unwind: 1*1, 2*1, 3*2, then 4*6. | f(1)=1, f(2)=2, f(3)=6, f(4)=24 | — | |
| Print the final result. | f(1)=1, f(2)=2, f(3)=6, f(4)=24 | 24 | |
| Check zero and one separately. | f(1)=1, f(2)=2, f(3)=6, f(4)=24 | 24 |
Cost and common mistakes
O(n) calls and O(n) stack frames; multiplication costs increase as the integer grows.
- The input contract is a nonnegative integer.
- Large n can exceed recursion depth; an iterative approach avoids recursive stack growth.
Try it yourself
Draw the call stack for factorial(3).
Reveal answer and reasoning
Calls descend 3 -> 2 -> 1 -> 0, then return 1 -> 1 -> 2 -> 6.