Recursion

A function that calls itself is called recursive. It sounds like a trick, but it is a natural way to solve problems that contain smaller copies of themselves: a folder holds folders, a family tree holds smaller family trees, and a sum of ten numbers is the first number plus the sum of the other nine.

In this lesson you will write recursive functions, see what happens inside the computer when they run, learn the limits Python puts on recursion, and use caching to make slow recursive code fast.

A function that calls itself

Every recursive function has two parts:

• A base case: a simple input the function can answer directly, without calling itself. This is what stops the recursion.
• A recursive case: the function calls itself with a smaller input that moves closer to the base case.

def countdown(n):
    if n == 0:                 # base case
        print("Train departs!")
        return
    print(n)
    countdown(n - 1)           # recursive case: a smaller problem

countdown(3)

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

print(factorial(5))

3
2
1
Train departs!
120

factorial(5) means 5 x 4 x 3 x 2 x 1. The function says: "the factorial of 5 is 5 times the factorial of 4", and trusts the same function to work out the rest. Eventually it reaches factorial(1), which answers 1 straight away.

What happens on the call stack

Each time a function is called, Python creates a frame: a small block of memory holding that call's local variables. Frames are kept on the call stack, a pile where the newest call sits on top. A call cannot finish until every call it started has finished, so recursive calls pile up and then unwind in reverse order. Adding a depth parameter makes this visible:

def factorial(n, depth=0):
    pad = "    " * depth
    print(f"{pad}factorial({n}) called")
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(f"{pad}factorial({n}) returns {result}")
    return result

factorial(4)

factorial(4) called
    factorial(3) called
        factorial(2) called
            factorial(1) called
            factorial(1) returns 1
        factorial(2) returns 2
    factorial(3) returns 6
factorial(4) returns 24

Four frames were on the stack at the deepest point. Each one waited, holding its own n, until the call above it returned a value. This is why every call has its own separate variables: n is 4 in one frame and 1 in another at the same moment.

The recursion limit and RecursionError

The stack cannot grow for ever. If a function forgets its base case, or the input never gets smaller, it would call itself endlessly. Python protects you with a recursion limit, which is 1,000 frames by default. Going past it raises RecursionError.

import sys

def broken(n):
    return broken(n - 1)       # no base case!

print(sys.getrecursionlimit())
try:
    broken(5)
except RecursionError as error:
    print("RecursionError:", error)

1000
RecursionError: maximum recursion depth exceeded

When you see this error, check two things: does a base case exist, and does every recursive call really move towards it? A common bug is writing countdown(n) instead of countdown(n - 1).

You can raise the limit with sys.setrecursionlimit(5000), but treat that as a last resort. Deep recursion uses a lot of memory, and some languages convert certain recursive calls into loops automatically (called tail call optimisation), but Python deliberately does not. If your data can be thousands of levels deep, write a loop instead.

Recursion on nested data

Recursion really shines when the data itself is nested and you do not know how deep it goes. A folder can hold files and more folders, which can hold more folders. A loop alone struggles here; a recursive function handles any depth naturally.

project = {
    "name": "college-fest",
    "files": {"poster.png": 850, "budget.xlsx": 40},
    "folders": [
        {"name": "photos", "files": {"day1.jpg": 3200, "day2.jpg": 2900}, "folders": []},
        {"name": "music", "files": {}, "folders": [
            {"name": "dj-night", "files": {"mix.mp3": 9000}, "folders": []},
        ]},
    ],
}

def folder_size(folder):
    total = sum(folder["files"].values())        # files directly inside
    for sub in folder["folders"]:
        total += folder_size(sub)                # the same question, smaller
    return total

def show_tree(folder, depth=0):
    print("  " * depth + folder["name"] + "/", folder_size(folder), "KB")
    for sub in folder["folders"]:
        show_tree(sub, depth + 1)

show_tree(project)

college-fest/ 15990 KB
  photos/ 6100 KB
  music/ 9000 KB
    dj-night/ 9000 KB

Notice the base case here is hidden: a folder with no sub-folders does not enter the loop, so it simply returns the size of its own files. The same pattern works for nested lists, JSON from a web API, comment threads with replies, and menus with sub-menus.

Memoisation with functools.cache

Some recursive functions solve the same smaller problem many times. Take this question: how many different ways can a shopkeeper in Rohtak give ₹100 using coins of ₹1, ₹2, ₹5 and ₹10? The function below tries "use the first coin" and "skip the first coin", which is correct but repeats a lot of work. Memoisation means remembering the answer for each input so each question is solved only once. @functools.cache does this for you.

import functools

calls = 0

@functools.cache
def ways(amount, coins):
    global calls
    calls += 1
    if amount == 0:
        return 1                              # exact change made
    if amount < 0 or not coins:
        return 0                              # overshot, or no coins left
    use_first = ways(amount - coins[0], coins)
    skip_first = ways(amount, coins[1:])
    return use_first + skip_first

print(ways(100, (1, 2, 5, 10)), "ways")
print("Function body ran", calls, "times")

2156 ways
Function body ran 518 times

Without the @functools.cache line the answer is the same, but the body runs 157,071 times. Two rules apply. The arguments must be hashable (usable as dictionary keys), which is why the coins are a tuple and not a list. And the function must always give the same result for the same arguments. The Decorators lesson shows how cache and lru_cache work as decorators.

Common mistakes

• No base case, or one that is never reached. The function recurses until RecursionError. Make sure every call moves closer to the base case.
• Forgetting to return the recursive call. factorial(n - 1) on its own computes a value and throws it away; write return n * factorial(n - 1).
• Using recursion for simple loops. Adding 1 to 10,000 recursively hits the limit; sum(range(1, 10_001)) does not.
• Caching a function that takes a list. @cache raises TypeError: unhashable type: 'list'; pass a tuple instead.

Key points

• A recursive function calls itself on a smaller input and needs a base case to stop.
• Each call gets its own frame on the call stack; frames unwind in reverse order.
• Python's default recursion limit is 1,000; going past it raises RecursionError.
• Python does not do tail call optimisation, so prefer loops for very deep problems.
• Recursion suits nested data such as folders, trees and JSON.
• @functools.cache memoises results so repeated sub-problems are solved only once.

def total_marks(data):
    total = 0
    for item in data:
        if isinstance(item, list):
            total += total_marks(item)
        else:
            total += item
    return total

def deepest(data):
    inner = [deepest(item) for item in data if isinstance(item, list)]
    return 1 + max(inner, default=0)

marks = [45, [78, 91, [66, 54]], [], 88]
print(total_marks(marks))
print(deepest(marks))

422
3