Python Recursion

Most functions you've written so far call other functions, like print() or len(). But a function can also call itself. That's Python recursion: solving a big problem by breaking it into a smaller copy of the same problem, again and again, until it becomes trivially easy. In this lesson, you'll learn the two parts every recursive function needs, watch the call stack grow and shrink, and see when a plain loop is the better choice.

What is recursion in Python?

A recursive function is a function that calls itself. Each call works on a smaller or simpler input than the one before, until the input is so small that the answer is obvious.

def countdown(n):
    if n == 0:
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)

countdown(3)

3
2
1
Liftoff!

countdown(3) prints 3 and calls countdown(2), which prints 2 and calls countdown(1), and so on. When n reaches 0, the function prints "Liftoff!" and stops calling itself.

Base case and recursive case

Every recursive function has two parts:

• Base case – the condition where the function stops and returns an answer directly, without calling itself. In countdown(), it's n == 0. This is the doll that doesn't open.
• Recursive case – the part where the function calls itself with a smaller input, moving one step closer to the base case. In countdown(), it's countdown(n - 1).

How to calculate a factorial with recursion

The factorial of a number (written n!) is that number multiplied by every whole number below it, down to 1. For example, 4! = 4 × 3 × 2 × 1 = 24. Notice that 4! is just 4 × 3!. That "same problem, but smaller" shape is perfect for recursion:

def factorial(n):
    if n == 1:                       # base case
        return 1
    return n * factorial(n - 1)      # recursive case

print(factorial(3))
print(factorial(5))

6
120

How does the call stack work in recursion?

Python keeps track of running functions on the call stack, a pile of "frames" where each frame remembers one function call and its local variables. A new call is placed on top. When a call returns, its frame is removed and Python goes back to the frame underneath.

Here's what happens for factorial(3):

1. factorial(3) needs 3 * factorial(2), so it waits and calls factorial(2).
2. factorial(2) needs 2 * factorial(1), so it waits and calls factorial(1).
3. factorial(1) hits the base case and returns 1. The stack stops growing.
4. factorial(2) gets the 1 back, calculates 2 * 1 = 2 and returns 2.
5. factorial(3) gets the 2 back, calculates 3 * 2 = 6 and returns 6.

You can see this order for yourself by adding print() calls:

def factorial(n):
    print(f"Calling factorial({n})")
    if n == 1:
        return 1
    result = n * factorial(n - 1)
    print(f"factorial({n}) returns {result}")
    return result

factorial(3)

Calling factorial(3)
Calling factorial(2)
Calling factorial(1)
factorial(2) returns 2
factorial(3) returns 6

All the "Calling" lines come first (the stack grows), then the "returns" lines appear in reverse order (the stack shrinks).

Summing a list with recursion

The total of a list is its first item plus the total of the rest of the list. The base case is an empty list, whose total is 0. This uses list slicing: prices[1:] is every item except the first.

def cart_total(prices):
    if not prices:                   # base case: empty list
        return 0
    return prices[0] + cart_total(prices[1:])

print(cart_total([12, 5, 8, 20]))

45

Each call works on a list that is one item shorter, so it's guaranteed to reach the empty list eventually.

Real-world example: counting files in nested folders

Recursion really shines when data is nested inside data of the same shape, like folders inside folders. Here, each folder is a dictionary with a number of files and a list of subfolders:

photos = {
    "files": 2,
    "subfolders": [
        {"files": 5, "subfolders": []},
        {"files": 1, "subfolders": [
            {"files": 3, "subfolders": []},
        ]},
    ],
}

def count_files(folder):
    total = folder["files"]
    for sub in folder["subfolders"]:
        total += count_files(sub)    # same job, smaller folder
    return total

print("Total files:", count_files(photos))

Total files: 11

The function doesn't need to know how deep the folders go. A folder with no subfolders is the base case: the loop doesn't run, so it simply returns its own file count.

What is the recursion limit in Python?

Every waiting call takes up memory on the call stack, so Python sets a limit on how deep recursion can go. By default it's 1,000 calls. You can check it with the sys module (you'll learn about imports in Python modules):

import sys
print(sys.getrecursionlimit())

1000

If a function goes deeper than that, usually because the base case is missing, Python raises a RecursionError:

def countdown(n):
    print(n)
    countdown(n - 1)     # no base case!

countdown(3)

RecursionError: maximum recursion depth exceeded

You'll see 3, 2, 1, 0, -1, -2 and hundreds more numbers printed before the error. The fix is to add a base case, not to raise the limit.

Recursion vs loop: which should you use?

Anything you can do with recursion, you can also do with a loop. Here's factorial with a for loop:

def factorial_loop(n):
    result = 1
    for number in range(2, n + 1):
        result *= number
    return result

print(factorial_loop(5))

120

Common mistakes with recursion

1. Forgetting the base case

Without a stopping condition, you get RecursionError. Always write the base case first.

2. Not moving toward the base case

If countdown(n) checks n == 0 but calls countdown(n - 2), then countdown(3) jumps from 1 to -1 and skips 0 forever. A safer base case is if n <= 0:.

3. Forgetting to return the recursive result

def factorial(n):
    if n == 1:
        return 1
    n * factorial(n - 1)     # calculated, but not returned

print(factorial(3))

TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'

Without return, factorial(2) gives back None, and 3 * None fails. Write return n * factorial(n - 1).

Practice exercise

def reverse_text(text):
    if text == "":
        return ""
    return reverse_text(text[1:]) + text[0]

print(reverse_text("stressed"))

desserts

What's next?

You've seen how functions can call themselves. To finish the chapter, explore the handy tools Python gives you for free in useful Python built-in functions like map(), filter(), zip() and enumerate().