Writing Self-Referencing Code

A recursive function calls itself. Recursion is the natural way to express algorithms that are defined in terms of smaller versions of themselves: walking a tree, traversing a nested data structure, solving a problem by reducing it to a simpler problem. Any loop can be written as recursion and vice versa; often one form is dramatically clearer than the other.

Every recursive function needs two parts: a base case that stops the recursion, and a recursive step that reduces the problem and calls itself on the smaller version. Skip the base case and you get infinite recursion; skip the reduction and you get the same thing. Python's default recursion limit (1000) turns infinite recursion into a RecursionError quickly, which at least stops the program before it hangs.

Classic textbook examples are factorial, Fibonacci, and tree traversal. Practical examples are flattening nested lists, walking a directory tree, parsing JSON or XML, evaluating expressions. The pattern repeats: handle the leaf, recurse into the children, combine.

Python does not optimize tail calls. Deep recursion is expensive — each call adds a frame to the stack. For deep structures, convert to iteration (an explicit stack or queue) or use sys.setrecursionlimit carefully. Memoization with @lru_cache can make naively exponential recursion (like a recursive Fibonacci) run in linear time without rewriting the algorithm.

Writing a correct recursion

State the base case first: “for an empty input, return X”. Then state the recursive step: “otherwise, solve a smaller version and combine the results”. Write them in that order in the code too; it reads clearly.

Check that every recursive call makes the input strictly smaller. If it doesn't, the base case will never fire and the stack will grow until RecursionError. “Strictly smaller” usually means fewer elements, shorter string, smaller number.

Recursion vs iteration, and memoization

When the recursion depth is bounded by log(n) (binary tree walks, divide-and-conquer), recursion is natural and safe. When it is bounded by n, convert to iteration or extend the limit only after measuring.

For recursive functions that repeatedly recompute the same sub-problem (naive Fibonacci), add @functools.lru_cache(maxsize=None). The cache turns exponential work into linear without changing the code.

Recursion-related tools.

Writing Self-Referencing Code code example

The script shows classic recursive helpers and how memoization rescues the naive Fibonacci.

# Lesson: Writing Self-Referencing Code
from functools import lru_cache
import sys


def factorial(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n in (0, 1):
        return 1
    return n * factorial(n - 1)


def flatten(items):
    """Flatten a nested list of arbitrary depth."""
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result


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


def count_nodes(tree: dict) -> int:
    """Count nodes in a tree represented as {'value': x, 'children': [...]}"""
    return 1 + sum(count_nodes(c) for c in tree.get("children", []))


print("factorial(6):", factorial(6))
print("flatten    :", flatten([1, [2, [3, 4], 5], [6]]))
print("fib(30)    :", fib(30))

tree = {
    "value": "root",
    "children": [
        {"value": "a", "children": [{"value": "a1"}, {"value": "a2"}]},
        {"value": "b", "children": []},
        {"value": "c", "children": [{"value": "c1"}]},
    ],
}
print("count_nodes:", count_nodes(tree))

# Guard against pathological input
print("recursion limit:", sys.getrecursionlimit())
try:
    factorial(20_000)
except RecursionError as err:
    print("too deep:", err)

Notice the shape of each recursion:

1) Base case: a concrete, tiny input that answers directly.
2) Recursive step: solve a smaller sub-problem and combine.
3) `@lru_cache` erases duplicate work in `fib` — linear instead of exponential.
4) Deep calls still hit the recursion limit; convert to iteration if needed.

Convert a recursive sum to an iterative one.

def rec_sum(xs):
    if not xs: return 0
    return xs[0] + rec_sum(xs[1:])

def iter_sum(xs):
    total = 0
    for x in xs:
        total += x
    return total

nums = list(range(1000))
assert rec_sum(nums[:100]) == iter_sum(nums[:100])
print(iter_sum(nums))

Verify the base cases and reductions.

def fact(n):
    if n in (0, 1): return 1
    return n * fact(n - 1)
assert fact(0) == 1 and fact(1) == 1 and fact(5) == 120
def fl(x):
    return [a for i in x for a in (fl(i) if isinstance(i, list) else [i])]
assert fl([1, [2, [3]]]) == [1, 2, 3]

Running prints:

factorial(6): 720
flatten    : [1, 2, 3, 4, 5, 6]
fib(30)    : 832040
count_nodes: 7
recursion limit: 1000
too deep: maximum recursion depth exceeded