Introduction to recursion

Concept	Key point
Base case	Always required — stops infinite recursion
Recursive case	Reduce to a smaller problem
Call stack	Each call waits for the deeper one to finish
`sys.setrecursionlimit`	Set to 200000–300000 in CP
Memoization	Cache results with `@lru_cache` to avoid recomputation
Backtracking	Recurse → explore → undo
Fast exponentiation	$O(\log n)$ via squaring — know the idea, use `pow(a, n, mod)` in practice

factorial(4)
  → 4 * factorial(3)
       → 3 * factorial(2)
            → 2 * factorial(1)
                 → 1 * factorial(0)
                      → 1          ← base case
                 ← 1 * 1 = 1
            ← 2 * 1 = 2
       ← 3 * 2 = 6
  ← 4 * 6 = 24

from functools import lru_cache

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

print(fib(100))   # 354224848179261915075 — instant

def power(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        half = power(a, n // 2)
        return half * half        # compute once, reuse!
    return a * power(a, n - 1)

print(power(2, 10))    # 1024
print(power(3, 20))    # 3486784401

def binary_search(a, target, lo, hi):
    if lo > hi:
        return -1                          # base case: not found
    mid = (lo + hi) // 2
    if a[mid] == target:
        return mid
    if a[mid] < target:
        return binary_search(a, target, mid + 1, hi)
    return binary_search(a, target, lo, mid - 1)

a = [1, 3, 5, 7, 9, 11, 15]
print(binary_search(a, 7, 0, len(a) - 1))    # 3
print(binary_search(a, 6, 0, len(a) - 1))    # -1

def hanoi(n, source, auxiliary, target):
    if n == 0:
        return
    hanoi(n - 1, source, target, auxiliary)   # move n-1 to auxiliary
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, source, target)   # move n-1 from auxiliary to target

hanoi(3, "A", "B", "C")

def subsets(a, index, current):
    if index == len(a):
        print(current)
        return
    # exclude a[index]
    subsets(a, index + 1, current)
    # include a[index]
    subsets(a, index + 1, current + [a[index]])

subsets([1, 2, 3], 0, [])
# []
# [3]
# [2]
# [2, 3]
# [1]
# [1, 3]
# [1, 2]
# [1, 2, 3]

def permutations(a, current, used):
    if len(current) == len(a):
        print(current)
        return
    for i in range(len(a)):
        if not used[i]:
            used[i] = True
            permutations(a, current + [a[i]], used)
            used[i] = False

a = [1, 2, 3]
permutations(a, [], [False] * len(a))
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]

Introduction to Recursion

Factorial

Sum from 1 to N

Fibonacci Numbers

Fast Exponentiation

Recursion Depth and `sys.setrecursionlimit`

Thinking Recursively

Binary Search Recursively

Tower of Hanoi

Generating All Subsets

Generating All Permutations

Summary

Introduction to recursion

Introduction to Recursion

Factorial

Sum from 1 to N

Fibonacci Numbers

Fast Exponentiation

Recursion Depth and sys.setrecursionlimit

Thinking Recursively

Binary Search Recursively

Tower of Hanoi

Generating All Subsets

Generating All Permutations

Summary

Recursion Depth and `sys.setrecursionlimit`