Recursion Examples

Recursion Examples#

GCD — Euclidean Algorithm#

The greatest common divisor of two integers has an elegant recursive definition:

gcd(a, 0) = a                  (base case)
gcd(a, b) = gcd(b, a % b)     (recursive case)

Run it below and try a few pairs of your own:

>>> def gcd(a: int, b: int) -> int:
...     if b == 0:
...         return a
...     return gcd(b, a % b)
...
>>> gcd(48, 18)
6
>>> gcd(100, 75)
25

Each call reduces b toward 0 because a % b < b for any b > 0. Python’s standard library provides math.gcd which uses the same algorithm.

Flattening a Nested List#

Some problems only make sense recursively. Flattening an arbitrarily nested list has no clean iterative equivalent. For each element, the function checks whether it is itself a list. If it is, it recurses into it; if not, it appends the value directly. Any depth of nesting is handled naturally because the recursion keeps going until it reaches a non-list item. Run it and try a more deeply nested list of your own:

>>> def flatten(lst: list) -> list:
...     result = []
...     for item in lst:
...         if isinstance(item, list):
...             result.extend(flatten(item))
...         else:
...             result.append(item)
...     return result
...
>>> nested = [1, [2, 3], [4, [5, 6]], 7]
>>> flatten(nested)
[1, 2, 3, 4, 5, 6, 7]

Directory Tree Traversal#

File systems are trees — a natural fit for recursion:

from pathlib import Path

def print_tree(path, indent: int = 0) -> None:
    print("  " * indent + path.name)
    if path.is_dir():
        for child in sorted(path.iterdir()):
            print_tree(child, indent + 1)

Each call prints the current entry’s name, indented by its depth, then recurses into each child if the entry is a directory. Files are leaf nodes — they print their name and return immediately. Calling it on the current directory walks the entire tree:

print_tree(Path("."))

The function calls itself for each subdirectory, unwinding naturally when a directory has no more children.

Memoisation with lru_cache#

The naive recursive Fibonacci is exponential because it recomputes the same values repeatedly. functools.lru_cache stores results automatically. The @lru_cache decorator wraps fib so that the first time any value is computed it is stored; subsequent calls with the same argument return the cached result instantly. The recursive structure of the code is unchanged — only its performance profile improves. Run it and try fib(200), which would be hopeless without the cache:

>>> from functools import lru_cache
>>> @lru_cache(maxsize=None)
... def fib(n: int) -> int:
...     if n <= 1:
...         return n
...     return fib(n - 1) + fib(n - 2)
...
>>> fib(50)
12586269025

With caching, each value of fib(n) is computed exactly once, reducing the total work to O(N).

Generators for Sequences with a Ceiling#

For sequences defined by a recurrence — like factorials and Fibonacci numbers — Python generators offer a third style that is neither recursive nor a plain loop. A generator function uses yield to produce one value at a time, suspending execution between calls. This makes it natural to express “generate values indefinitely, and let the caller decide when to stop.”

Infinite Factorial Generator#

def factorials():
    """Yield 0!, 1!, 2!, 3!, ... without bound."""
    result = 1
    n = 0
    while True:
        yield result
        n += 1
        result *= n

The generator runs forever by design. To collect only the values up to a ceiling, use itertools.takewhile:

from itertools import takewhile

for f in takewhile(lambda x: x <= 1_000_000, factorials()):
    print(f)

Output:

1
1
2
6
24
120
720
5040
40320
362880

You can also write a self-contained generator that accepts the ceiling directly — useful when you want a single, reusable function:

def factorials_up_to(ceiling: int):
    """Yield each factorial that does not exceed ceiling."""
    if ceiling < 1:
        raise ValueError(f"ceiling must be >= 1, got {ceiling}")
    result, n = 1, 0
    while result <= ceiling:
        yield result
        n += 1
        result *= n

print(list(factorials_up_to(1_000_000)))

Output:

[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

Infinite Fibonacci Generator#

def fibonacci():
    """Yield F(0), F(1), F(2), ... without bound."""
    prev, curr = 0, 1
    while True:
        yield prev
        prev, curr = curr, prev + curr

from itertools import takewhile

fibs = list(takewhile(lambda x: x <= 1000, fibonacci()))
print(fibs)

Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]

Again, a ceiling-aware version keeps the intent local to the function:

def fibonacci_up_to(ceiling: int):
    """Yield each Fibonacci number that does not exceed ceiling."""
    if ceiling < 0:
        raise ValueError(f"ceiling must be >= 0, got {ceiling}")
    prev, curr = 0, 1
    while prev <= ceiling:
        yield prev
        prev, curr = curr, prev + curr

print(list(fibonacci_up_to(1000)))

Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]

Why Generators?#

Property

Generators

Memory

O(1) — only the current value is in memory at any time

Stack depth

O(1) — no recursive frames; no RecursionError

Early termination

Natural with takewhile, break, or next()

Composability

Pipe generators through itertools functions freely

Generators are the idiomatic Python choice for producing a potentially large (or infinite) sequence of values one at a time. They combine the clarity of recursive definitions with the efficiency of iterative loops.