S027 · Recursion — Call Stack, Base Case, Worked Examples

"""recursion.py — the interview canon for recursion + memoisation.
 
Run:  python recursion.py
"""
from __future__ import annotations
from functools import lru_cache
import time
import sys
 
 
# ------------------------------------------------------------------
# 1) Factorial — the ‘hello world’ of recursion
# ------------------------------------------------------------------
def factorial(n: int) -> int:
    if n <= 1:                       # base case
        return 1
    return n * factorial(n - 1)      # recursive case, shrinks by 1
 
 
# ------------------------------------------------------------------
# 2) Fibonacci — naive vs memoised
# ------------------------------------------------------------------
def fib_naive(n: int) -> int:
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)      # exponential — see it below
 
 
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)         # linear — because each n computed once
 
 
# ------------------------------------------------------------------
# 3) List sum — recursive is fine but iteration is clearer
# ------------------------------------------------------------------
def sum_list(a: list[int]) -> int:
    if not a:
        return 0
    return a[0] + sum_list(a[1:])                     # careful — a[1:] copies! O(n^2) memory
 
 
def sum_list_iter(a: list[int]) -> int:
    total = 0
    for x in a:
        total += x
    return total
 
 
# ------------------------------------------------------------------
# 4) Mergesort — the classic divide-and-conquer
# ------------------------------------------------------------------
def merge_sort(a: list[int]) -> list[int]:
    if len(a) <= 1:                                  # base case
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])                       # recursive on smaller
    right = merge_sort(a[mid:])
    return _merge(left, right)
 
 
def _merge(left: list[int], right: list[int]) -> list[int]:
    out: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out
 
 
# ------------------------------------------------------------------
# 5) Binary tree — the recursive definition matches the code exactly
# ------------------------------------------------------------------
class TreeNode:
    __slots__ = ("val", "left", "right")
 
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def tree_depth(root: TreeNode | None) -> int:
    if root is None:                                 # base case
        return 0
    return 1 + max(tree_depth(root.left), tree_depth(root.right))
 
 
def inorder(root: TreeNode | None) -> list:
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)
 
 
# ------------------------------------------------------------------
# 6) Iterative DFS on a tree — recursion with your own explicit stack
# ------------------------------------------------------------------
def inorder_iter(root: TreeNode | None) -> list:
    """Same output as inorder() but uses an explicit stack — no recursion, no depth limit."""
    out, stack, node = [], [], root
    while node or stack:
        while node:                                  # descend the left spine
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out
 
 
# ------------------------------------------------------------------
# 7) The perf demo — see exponential vs linear
# ------------------------------------------------------------------
def perf_demo() -> None:
    n = 30
    t = time.perf_counter(); fib_naive(n); dt_naive = time.perf_counter() - t
    fib_memo.cache_clear()
    t = time.perf_counter(); fib_memo(n); dt_memo = time.perf_counter() - t
    print(f"fib({n}) naive : {dt_naive*1000:.1f} ms   {'(' + str(2**n) + ' calls)' if False else ''}")
    print(f"fib({n}) memo  : {dt_memo*1000:.4f} ms  <- {dt_naive/dt_memo:.0f}x faster")
 
 
if __name__ == "__main__":
    print("factorial(5) :", factorial(5))
    print("sum_list([1..10]) :", sum_list(list(range(1, 11))))
    print("merge_sort([3,1,4,1,5,9,2,6]) :", merge_sort([3, 1, 4, 1, 5, 9, 2, 6]))
 
    # Build a small tree:   1
    #                      / \
    #                     2   3
    #                    / \
    #                   4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print("tree_depth :", tree_depth(root))
    print("inorder recursive :", inorder(root))
    print("inorder iterative :", inorder_iter(root))
 
    perf_demo()
 
    # Recursion limit — comment out unless you're brave
    # sys.setrecursionlimit(2000)
    # print("factorial(1500) last 5 digits :", str(factorial(1500))[-5:])