Python Algorithms

Factorial Using Recursion in Python

factorial(6) calls factorial(5), which calls factorial(4)... See how recursion stacks up and unwinds to 720.

  • Intermediate
  • 2 min read
  • 1 runnable example
What you'll learn
  • Base case and recursive case
  • How calls stack up and return
  • Python's recursion limit
factorial(4)
  1. factorial(1)base casereturns 1
  2. factorial(2)returns 2 * 1 = 2
  3. factorial(3)returns 3 * 2 = 6
  4. factorial(4)returns 4 * 6 = 24
Calls pile up from the bottom; results return from the top.

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.

From a line of people to code
factorial(6)🙋 The first person: 6 × the answer they are waiting for
number * factorial(number - 1)➡️ Ask the next person the same question with a smaller number
if number <= 1: return 1🛑 The last person answers right away: 1
720⬅️ Answers travel back along the line: 720
Every call waits for a smaller call until the base case answers.
In one sentence

A 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

  1. if number <= 1: return 1 is the base case; without it the calls would never stop.
  2. return number * factorial(number - 1) calls the same function with a smaller number.
  3. factorial(6) waits for factorial(5), which waits for factorial(4), down to factorial(1).
  4. 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.factorial is 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

Run code →
main.py
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))
Get a Run button for this example

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.

  1. Try empty, single-item, and duplicate-value inputs.
  2. Print state after every step to observe the algorithm.
  3. Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Run in the Python compiler →

Common mistakes

Forgetting the base case

The function calls itself forever until Python raises RecursionError.

Problem
def factorial(number):
    return number * factorial(number - 1)
Fix
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.

All challenges