Recursion — A Function That Calls Itself

What is it? #

Recursion is solving a problem by solving a smaller version of the same problem, until the version is small enough to answer directly.

Every recursive function needs two things: a base case that stops the process, and a recursive step that moves closer to it. Miss either and you get infinite recursion.

Each call gets its own set of local variables, stacked on top of the previous call. When a call returns, its frame is discarded and the one below continues.

Recursion is not magic and it is not always better. For anything naturally shaped like a tree or a nested structure, it is far clearer than a loop. For simple counting, a loop is simpler.

Think of it like this #

You are in a cinema and want to know your row number. You cannot see the front, so you ask the person in front: "what row are you in?" They do not know either, so they ask the person in front of them. Eventually someone in row 1 says "row 1" — the base case. That answer travels back: 2, 3, 4, until it reaches you.

Each person only has to know one rule: my row is one more than the row in front.

Simple example #

Adding up numbers in a nested list of unknown depth. A loop struggles because you do not know how deep the nesting goes. Recursion handles it naturally: for each item, either add it or recurse into it.

Code #

# The shape of every recursive function
def countdown(n):
    if n <= 0:              # base case — stop here
        print("liftoff")
        return
    print(n)
    countdown(n - 1)        # recursive step — moves towards the base case


# Nested structures are where recursion shines
def deep_sum(items):
    total = 0
    for item in items:
        if isinstance(item, list):
            total += deep_sum(item)      # same problem, smaller input
        else:
            total += item
    return total

print(deep_sum([1, [2, 3, [4, [5]]], 6]))     # 21


# Walking a nested dictionary — a very common real task
def find_key(data, target):
    if isinstance(data, dict):
        for key, value in data.items():
            if key == target:
                return value
            found = find_key(value, target)
            if found is not None:
                return found
    elif isinstance(data, list):
        for item in data:
            found = find_key(item, target)
            if found is not None:
                return found
    return None

config = {"server": {"db": {"host": "localhost", "port": 5432}}}
print(find_key(config, "port"))               # 5432


# Recursion without memoisation can explode
def fib_slow(n):
    if n < 2:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)   # recalculates the same values

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_fast(n):
    if n < 2:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

print(fib_fast(50))        # instant; fib_slow(50) would take years

countdown(3) on the call stack

countdown(3)  prints 3
  countdown(2)  prints 2
    countdown(1)  prints 1
      countdown(0)  prints liftoff, returns
    returns
  returns
returns

How it works #

countdown checks the base case first. That order matters: check whether you are done before doing more work, otherwise the stop condition is never reached.

Each call to countdown(n - 1) pushes a new frame onto the call stack with its own n. The diagram shows four frames existing at once at the deepest point.

deep_sum is the natural fit. Each nested list is the same problem with a smaller input, so the function calls itself and adds the result. Writing this with loops means managing your own stack of positions.

find_key shows the same shape applied to nested dictionaries — searching parsed JSON or configuration is one of the most common real uses of recursion.

The Fibonacci pair shows the classic failure. fib_slow(50) recomputes the same values exponentially many times. @lru_cache remembers each result, turning an exponential algorithm into a linear one. That idea — remember what you already computed — is exactly what dynamic programming formalises later in this track.

Python caps recursion depth at around 1,000 by default. That limit is a safety net against runaway recursion, and it is also why deeply recursive algorithms on large inputs often get rewritten with an explicit stack.

Real-world use #

Recursion appears wherever data nests: JSON documents, directory trees, DOM trees, category hierarchies, organisation charts, expression parsing, and every tree and graph algorithm in this track.

Walking a folder tree to find every file matching a pattern is naturally recursive, because a folder contains folders.

Where recursion is risky is unbounded depth. Parsing an untrusted deeply nested JSON payload can blow the stack — a real denial-of-service vector, which is why parsers impose depth limits.

The practical guideline: use recursion when the data is tree-shaped, use a loop when it is list-shaped, and add memoisation when the same subproblem repeats.

Common mistakes #

• Missing or unreachable base case, causing RecursionError.
• Recursing without making the input smaller, so the base case is never reached.
• Recomputing the same subproblem repeatedly instead of caching results.
• Using recursion on a flat list of a million items and hitting the depth limit.
• Slicing inside recursion (items[1:]), which copies and quietly adds a factor of n.

Practice #

Write a recursive function that flattens an arbitrarily nested list into a flat one. Then write a recursive function that counts how many files are in a nested dictionary representing a folder tree. Finally, add @lru_cache to a recursive grid-path counter and compare the timing with and without it.