DSData Structures & Algorithms · Lesson 5 of 9

Recursion

A recursive function calls itself on a smaller piece of the problem until the piece is trivially small. It's the natural language for trees, divide-and-conquer sorting, and any nested structure — master it here before the next two lessons lean on it.

Every recursive function has two parts: a base case — the input so small the answer is immediate — and a recursive case that shrinks the problem and calls itself. Miss the base case, or fail to shrink, and calls nest forever until the call stack overflows. The mental model: trust the recursive call. Assume it correctly solves the smaller problem, and only ask 'how do I combine that answer into mine?'

Python


def factorial(n):
    if n <= 1:                    # base case: answer is immediate
        return 1
    return n * factorial(n - 1)   # shrink, recurse, combine

factorial(5)     # 5 * 4 * 3 * 2 * 1 = 120

# What the call stack does:
# factorial(5)
#   factorial(4)
#     factorial(3)
#       factorial(2)
#         factorial(1) -> 1      base case hit, stack unwinds
#       -> 2 * 1 = 2
#     -> 3 * 2 = 6
#   -> 4 * 6 = 24
# -> 5 * 24 = 120

Recursion shines on nested data, where loops get awkward: a folder contains files and folders, which contain files and folders. The structure is recursive, so the cleanest code is too. Anything a loop does, recursion can do and vice versa — but for self-similar structures, recursion mirrors the shape of the data.

Python


import os

def total_size(path):
    if os.path.isfile(path):                  # base case: a file
        return os.path.getsize(path)
    total = 0
    for name in os.listdir(path):             # recursive case: a folder
        total += total_size(os.path.join(path, name))
    return total

⚠ Warning
Recursion with overlapping subproblems can explode. Naive fibonacci(n) calls itself twice per step — O(2ⁿ), and fibonacci(50) takes minutes. The fix is memoization: cache results so each subproblem is solved once. In Python, one decorator: @functools.lru_cache turns O(2ⁿ) into O(n). This idea — recursion plus a cache — is the heart of dynamic programming.

Python


from functools import lru_cache

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

fib(50)    # instant — each fib(k) computed once, then cached