After this lesson you can read and write a function that solves a problem by calling itself, and you can recognise the two parts that keep such a function safe.
The idea
Recursion sounds mysterious, but the idea is simple. To solve a big problem, solve a slightly smaller version of the same problem and combine the answer. A function that does this calls itself.
Think of counting the people in a queue. You cannot see the whole line, so you ask the person ahead of you "how many are in front of you?", add one, and answer the person behind. The person at the very front knows without asking: nobody is ahead. That person is the stopping point.
Two required parts
Every working recursive function has:
- A base case: an input so small that the answer is known directly. No further call is made.
- A recursive case: the function calls itself with a smaller input, getting closer to the base case.
Here is a countdown with both parts:
def countdown(n):
if n == 0:
print("liftoff")
return
print(n)
countdown(n - 1)
countdown(3)3
2
1
liftoffWhen n is 0 the base case prints and returns. Otherwise the function prints and calls itself with n - 1. Each call is closer to zero.
A function that returns a value
The classic example is the factorial. factorial(4) means 4 * 3 * 2 * 1. Notice that factorial(4) is 4 * factorial(3).
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(0))
print(factorial(4))
print(factorial(10))1
24
3628800Trace factorial(3) by hand. It waits for factorial(2), which waits for factorial(1), which waits for factorial(0). That one returns 1. Then the waiting calls finish in reverse order: 1 * 1, then 2 * 1, then 3 * 2. This waiting list of unfinished calls is called the call stack.
You can see the order by printing on the way in and out:
def trace(n):
print("enter", n)
if n > 0:
trace(n - 1)
print("leave", n)
trace(2)enter 2
enter 1
enter 0
leave 0
leave 1
leave 2Another example: adding a list
You can sum a list recursively by taking the first item and adding the sum of the rest:
def total(numbers):
if not numbers:
return 0
return numbers[0] + total(numbers[1:])
print(total([5, 10, 15]))30The base case is the empty list, whose total is 0. This is for learning. In real code you would write sum(numbers), which is simpler and faster.
Where recursion shines: nested data
Loops are better for flat data. Recursion pays off when a structure contains smaller copies of itself, such as a menu with sub-menus.
menu = {
"name": "Food",
"children": [
{"name": "Drinks", "children": [
{"name": "Tea", "children": []},
{"name": "Juice", "children": []},
]},
{"name": "Snacks", "children": []},
],
}
def show(node, depth=0):
print(" " * depth + node["name"])
for child in node["children"]:
show(child, depth + 1)
show(menu)Food
Drinks
Tea
Juice
SnacksNo loop could be written without knowing in advance how deep the nesting goes. The recursive version does not care. Each node, however deep, is handled by the same code.
Forgetting the base case
If the recursion never reaches a base case, the calls pile up. Python protects you by stopping after a limit, which by default is about a thousand calls.
def forever(n):
return forever(n + 1)
forever(0)RecursionError: maximum recursion depth exceededThis limit is why recursion is a poor choice for walking a list of a million items. A loop has no such limit.
import sys
print(sys.getrecursionlimit())1000Recursion versus loops
The factorial can also be written with a loop:
def factorial_loop(n):
result = 1
for number in range(2, n + 1):
result *= number
return result
print(factorial_loop(10))3628800Both give the same answer. For simple counting, prefer the loop. For trees, nested folders and similar shapes, prefer recursion.
Counting the steps
It helps to measure how deep a recursion goes. The next function counts how many digits a whole number has by cutting off the last digit each time:
def count_digits(n):
if n < 10:
return 1
return 1 + count_digits(n // 10)
print(count_digits(7))
print(count_digits(48213))1
5The base case is a single digit. Each recursive call works with a number that is ten times smaller, so it must eventually reach the base case. Whenever you write a recursive function, ask yourself two questions: "what is the smallest input, and what do I return for it?" and "how does every other input get smaller?" If you can answer both, the function will work.
Common mistakes
- No base case. The most common mistake, ending in a RecursionError.
- A recursive step that does not get smaller. Calling
countdown(n)instead ofcountdown(n - 1)never ends. - Forgetting to return the recursive result. Writing
factorial(n - 1)withoutreturngivesNone. - Using recursion for long flat data. A loop is simpler and has no depth limit.
- Skipping the hand trace. If a recursive function confuses you, write out the first three calls on paper.
Exercise
Write a recursive function power(base, exponent) that returns base raised to a non-negative whole exponent, without using **. The base case is exponent 0, which gives 1. Test it with power(2, 5).
Show one possible answer
def power(base, exponent):
if exponent == 0:
return 1
return base * power(base, exponent - 1)
print(power(2, 5))
print(power(5, 0))32
1Key points
- A recursive function calls itself on a smaller version of the problem.
- Every recursive function needs a base case that stops the calls, and a recursive case that moves toward it.
- Without a base case Python stops the program with a RecursionError once the call stack gets too deep.
- Anything done with recursion can be done with a loop. Choose recursion when the data is naturally nested, such as folders inside folders.
- Python allows about a thousand nested calls by default, so recursion is not a good fit for very long sequences.