Factorial Using Recursion in Python
factorial(6) calls factorial(5), which calls factorial(4)... See how recursion stacks up and unwinds to 720.
- Base case and recursive case
- How calls stack up and return
- Python's recursion limit
factorial(1)base casereturns 1factorial(2)returns 2 * 1 = 2factorial(3)returns 3 * 2 = 6factorial(4)returns 4 * 6 = 24
Each call waits for a smaller one
The problem
Some problems are naturally described in terms of a smaller version of themselves: a folder contains folders, a family tree contains smaller family trees, n! is n times (n - 1)!. Recursion lets you write code that follows such definitions directly.
Think of it like this
Recursion is like a line of people passing a question along. To answer 6!, the first person asks the next one for 5! and waits. That person asks for 4!, and so on, until someone is asked for 1! and can answer right away. Then each answer travels back along the line, and each person multiplies in their own number.
factorial(6)🙋 The first person: 6 × the answer they are waiting fornumber * factorial(number - 1)➡️ Ask the next person the same question with a smaller numberif number <= 1: return 1🛑 The last person answers right away: 1720⬅️ Answers travel back along the line: 720A recursive function calls itself with a smaller input until it reaches a base case it can answer directly; here factorial(n) = n × factorial(n - 1) and factorial(1) = 1.
Key points
if number <= 1: return 1is the base case; without it the calls would never stop.return number * factorial(number - 1)calls the same function with a smaller number.factorial(6)waits forfactorial(5), which waits forfactorial(4), down tofactorial(1).raise ValueError(...)rejects negative numbers, which would otherwise never reach the base case.
When should you use it?
- Problems defined in terms of smaller versions: trees, folders, nested data.
- Divide-and-conquer algorithms such as merge sort.
- Learning how the call stack works.
When not to use it
- Simple repetition such as factorial in real code: a loop or
math.factorialis faster and has no depth limit. - Very deep inputs: Python stops at about 1,000 nested calls with RecursionError.
See how it works
Press Step to follow each call. New calls go onto the call stack, and each one returns its value to the call that made it.
Example code
def factorial(number):
if number < 0:
raise ValueError("Factorial is undefined for negative numbers")
if number <= 1:
return 1
return number * factorial(number - 1)
print(factorial(6))
Result of running the code
720
Code explanation
The base case returns 1 for zero or one. Every other call multiplies n by the factorial of n minus one. The recursion depth is O(n).
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Common mistakes
Forgetting the base case
The function calls itself forever until Python raises RecursionError.
def factorial(number):
return number * factorial(number - 1)
def factorial(number):
if number <= 1:
return 1
return number * factorial(number - 1)
Finished this lesson?
Mark it as learned to track your progress.
Practice with a challenge
Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.
- Factorial Multiply all positive integers up to n. Easy
- Recursive Power Compute a power recursively by halving the exponent. Medium