11. Recursion

What Is Recursion?

Recursion is a function that calls itself with a smaller version of the same problem, until it reaches a simple base case it can answer directly.

Analogy: Russian nesting dolls (Matryoshka). To open the full set, you open the outer doll, then the next, until you reach the smallest one inside — that's your base case.

The two requirements:

1. Base case — a condition where the function returns without recursing (stops the chain)
2. Recursive case — the function calls itself with a smaller input, moving toward the base case

---

11.1 Recursion Fundamentals

# --- Factorial ---
# factorial(5) = 5 × 4 × 3 × 2 × 1 = 120
def factorial(n: int) -> int:
    if n == 0:              # base case
        return 1
    return n * factorial(n - 1)   # recursive case

# What happens in memory:
# factorial(3)
#   → 3 * factorial(2)
#         → 2 * factorial(1)
#               → 1 * factorial(0)
#                     → 1          ← base case
#               → 1 * 1 = 1
#         → 2 * 1 = 2
#   → 3 * 2 = 6

# --- Fibonacci (naive — exponential, used for illustration) ---
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)   # two recursive calls

# --- Power (divide & conquer) ---
def power(base: float, exp: int) -> float:
    if exp == 0: return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half      # reuse result — O(log n) instead of O(n)
    return base * power(base, exp - 1)

---

11.2 Recursion on Trees and Lists

# --- Sum all values in a nested list ---
# e.g. [1, [2, [3, 4]], 5] → 15
def nested_sum(lst) -> int:
    total = 0
    for item in lst:
        if isinstance(item, list):
            total += nested_sum(item)   # recurse into sub-list
        else:
            total += item
    return total

print(nested_sum([1, [2, [3, 4]], 5]))  # 15

# --- Flatten a nested list ---
def flatten(lst: list) -> list:
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, [4]], 5]]))  # [1, 2, 3, 4, 5]

# --- Directory size (real-world recursion) ---
import os

def directory_size(path: str) -> int:
    """Recursively calculate total size of all files in a directory."""
    total = 0
    for entry in os.scandir(path):
        if entry.is_file():
            total += entry.stat().st_size
        elif entry.is_dir():
            total += directory_size(entry.path)   # recurse into subdirectory
    return total

---

11.3 The Call Stack & Recursion Limit

Each recursive call adds a stack frame to the call stack. Python's default recursion limit is 1000.

import sys

# Check / change limit
print(sys.getrecursionlimit())   # 1000

# For deep recursion (e.g. large trees), increase it:
sys.setrecursionlimit(10_000)

# Better: convert to iterative with an explicit stack when depth is large
def factorial_iterative(n: int) -> int:
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

---

11.4 Divide & Conquer

A powerful recursive strategy: split the problem in half, solve each half, combine results.

# --- Binary search (divide & conquer version) ---
def binary_search_rec(arr: list[int], target: int, lo: int, hi: int) -> int:
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    else:
        return binary_search_rec(arr, target, lo, mid - 1)

# --- Maximum subarray sum (divide & conquer) ---
def max_crossing_sum(arr, lo, mid, hi):
    left_sum  = float("-inf")
    right_sum = float("-inf")
    total = 0
    for i in range(mid, lo - 1, -1):
        total += arr[i]
        left_sum = max(left_sum, total)
    total = 0
    for i in range(mid + 1, hi + 1):
        total += arr[i]
        right_sum = max(right_sum, total)
    return left_sum + right_sum

def max_subarray_dc(arr, lo, hi):
    if lo == hi:
        return arr[lo]
    mid = (lo + hi) // 2
    return max(
        max_subarray_dc(arr, lo, mid),
        max_subarray_dc(arr, mid + 1, hi),
        max_crossing_sum(arr, lo, mid, hi)
    )

---