Python · Course navigation

Python recursion and factorial

Separate a base case from a smaller recursive problem.

On this page

Before you start

Functions, return values, and conditions.

Separate a base case from a smaller recursive problem.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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) == 1

Output

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1def factorial(n):

2 if n < 0:

3 raise ValueError("n must be nonnegative")

4 if n == 0:

5 return 1

6 return n * factorial(n - 1)

8print(factorial(4))

9assert factorial(0) == 1

10assert factorial(1) == 1

Follow 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

Prepared trace of the published program. Some rows group repeated iterations.
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: 11, 21, 32, then 46.	`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

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

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.