Recursion and the Call Stack

def countdown(n):
    if n == 0:              # BASE CASE — answer directly, stop descending
        print("Liftoff!")
        return
    print(n)                # do this level's work
    countdown(n - 1)        # RECURSIVE CASE — strictly smaller argument

def factorial(n):
    if n <= 1:              # base case
        return 1
    return n * factorial(n - 1)   # recursive case

# Two questions to ask of any recursive function:
#   1. Is there an input it can answer WITHOUT recursing?
#   2. Does every recursive call get STRICTLY closer to that input?
# Answer B to either and it never terminates.

def trace(n, depth=0):
    """The same recursion, printing its own stack depth."""
    print("  " * depth + f"→ trace({n})")
    if n <= 1:
        print("  " * depth + f"← base case, return {n}")
        return n
    result = trace(n - 1, depth + 1) + trace(n - 2, depth + 1)
    print("  " * depth + f"← trace({n}) returns {result}")
    return result

trace(4)
# Run this in the playground. The indentation IS the stack.

# Naive — O(2ⁿ)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)


# Memoised — O(n). One decorator.
from functools import lru_cache

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


# Or by hand, so you can see what the decorator does:
def fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]           # ← the entire optimisation
    if n <= 1:
        return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

# fib(35):        about 5 seconds
# fib_fast(35):   instant
# fib_fast(500):  also instant

# Factorial: iteration is clearly better. No reason to recurse.
def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Tree traversal: recursion is clearly better. The iterative version
# needs an explicit stack and reads worse for no gain.
def tree_sum(node):
    if node is None:
        return 0
    return node.value + tree_sum(node.left) + tree_sum(node.right)

# The rule of thumb:
#   Is the DATA self-similar (a tree, a nested structure, a subdivided
#   range)? → recursion.
#   Is the data flat and the process just accumulation? → a loop.

def count_tail(n, acc=0):
    if n == 0:
        return acc
    return count_tail(n - 1, acc + n)    # a tail call...

count_tail(10000)
# ...and Python still raises RecursionError. CPython does NOT eliminate
# tail calls, deliberately: keeping every frame means tracebacks stay
# complete and debuggable.
#
# So in Python, A is not an optimisation.
# B is.

def list_sum(xs, i=0):
    if i == len(xs):
        return 0
    return xs[i] + list_sum(xs, i + 1)

# Note: xs[i] with an index, NOT xs[1:]. Slicing copies the rest of
# the list on every call, turning O(n) into O(n²).

def max_of(xs, lo, hi):
    if lo == hi:
        return xs[lo]
    mid = (lo + hi) // 2
    return max(max_of(xs, lo, mid), max_of(xs, mid + 1, hi))

def subsets(xs, i=0, current=None):
    if current is None:
        current = []
    if i == len(xs):
        return [current[:]]              # a complete choice — copy it
    without = subsets(xs, i + 1, current)          # do not take xs[i]
    current.append(xs[i])
    with_it = subsets(xs, i + 1, current)          # take xs[i]
    current.pop()                                  # UN-CHOOSE — essential
    return without + with_it

# 2ⁿ subsets, so 2ⁿ leaves. Exponential is correct here: the OUTPUT is
# exponential. That is a different situation from fib, where the output
# was one number.

def is_even(n):
    return True if n == 0 else is_odd(n - 1)

def is_odd(n):
    return False if n == 0 else is_even(n - 1)

# A silly example of a serious pattern: recursive-descent parsers are
# built this way — parse_expression calls parse_term calls parse_factor,
# which calls parse_expression again for a bracketed sub-expression.