Leveling up · step 21 of 22

Recursion

11 minSolve a problem by solving a smaller version of it.

A function that calls itself

Recursion means solving a problem by calling the same function on something smaller. Every recursive function needs a base case — the version it can answer immediately — or it calls itself forever.

def countdown(n):
    if n <= 0:            # base case: stop here
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)      # the same problem, one smaller

Factorial: the classic

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))    # 120

Read it as: 5! is 5 × 4!, and 4! is 4 × 3!, down to 1! which is 1. Each call waits for the answer from the smaller one.

When to reach for it

Recursion is not always the fastest option, but for anything defined in terms of itself — folders inside folders, family trees, a maze — it is usually the clearest. If a problem feels like "the same thing, but smaller", it is a recursion problem.

Remember this

A recursive function calls itself on a smaller input
The base case is what stops the recursion
Each call waits for the answer from the smaller one

Quick quiz

Three questions. 3 correct answers and you have the idea — you can retry as often as you like.

1. What stops a recursive function?
2. With `n * factorial(n - 1)`, what is factorial(3)?
3. What happens to a recursive function with no base case?

Answer all three to check them.

Now write it yourself

0/2 passed

Practice 1

Write a recursive function `countdown(n)` that prints the numbers from n down to 1, one per line.

practice_1.py

Practice 2

Write a recursive function `factorial(n)` that returns n! — factorial(0) and factorial(1) are both 1.

practice_2.py

Finish with two of three quiz answers correct and every exercise passing, and this lesson is marked complete.