Functional & recursion theory

closures.py# A closure is a function plus the enclosing variables it captures ("free vars").
def make_counter():
    count = 0                       # a free variable for the inner function
    def inc():
        nonlocal count              # rebind the enclosing name, don't shadow it
        count += 1
        return count
    return inc

c1, c2 = make_counter(), make_counter()
print(c1(), c1(), c1())             # 1 2 3   -> each closure has its OWN cell
print(c2())                         # 1       -> independent state

# Introspection: free variables live in code.co_freevars and in __closure__ cells
print("free vars:", make_counter().__code__.co_freevars)   # ('count',)
print("has closure cells:", make_counter().__closure__ is not None)

late_binding.py# The late-binding gotcha: closures capture the VARIABLE, not its value-at-creation.
funcs = [lambda: i for i in range(3)]
print("late binding:", [f() for f in funcs])   # [2, 2, 2]  (all see final i)

# Fix 1: bind the current value as a default argument (evaluated at def time)
fixed = [lambda i=i: i for i in range(3)]
print("default-arg fix:", [f() for f in fixed])# [0, 1, 2]

# Fix 2: a factory that closes over its own parameter
def make(i):
    return lambda: i
fixed2 = [make(i) for i in range(3)]
print("factory fix:", [f() for f in fixed2])   # [0, 1, 2]

pure.py# A PURE function: output depends only on inputs, and it mutates nothing external.
def pure_add_tax(price, rate):
    return round(price * (1 + rate), 2)      # no side effects, deterministic

# An IMPURE function: mutates its argument (a side effect) -> surprises callers.
def impure_append(item, bucket=[]):          # classic mutable-default bug!
    bucket.append(item)
    return bucket

print(pure_add_tax(100, 0.2))                # 120.0  (same input -> same output)
print(pure_add_tax(100, 0.2))                # 120.0
print(impure_append(1))                      # [1]
print(impure_append(2))                      # [1, 2]  <- shared default persists!

# The fix for the mutable default:
def safe_append(item, bucket=None):
    bucket = [] if bucket is None else bucket
    bucket.append(item)
    return bucket
print(safe_append(1), safe_append(2))        # [1] [2]

hof.pyfrom functools import reduce

nums = [1, 2, 3, 4, 5]

# map / filter are lazy iterators; wrap in list() to materialize.
print("map    :", list(map(lambda x: x * x, nums)))        # [1, 4, 9, 16, 25]
print("filter :", list(filter(lambda x: x % 2 == 0, nums)))# [2, 4]
print("reduce :", reduce(lambda a, b: a + b, nums, 0))     # 15

# The Pythonic equivalents are comprehensions (usually clearer & as fast):
print("comp   :", [x * x for x in nums if x % 2])          # [1, 9, 25]

# Higher-order: a function that RETURNS a function (a decorator-style adder).
def adder(n):
    def add(x): return x + n
    return add
add10 = adder(10)
print("hof    :", add10(5))                                # 15

recursion.pyimport sys

# Recursion uses the call stack: each call adds a frame. Python does NOT optimize
# tail calls, so recursion depth is bounded by the recursion limit.
print("recursion limit:", sys.getrecursionlimit())   # 1000 by default

def factorial(n):
    return 1 if n == 0 else n * factorial(n - 1)      # not tail-optimized either
print("factorial(10):", factorial(10))                # 3628800

# Even a perfectly tail-recursive function blows the stack — no TCO in CPython:
def count_down(n):
    if n == 0:
        return "done"
    return count_down(n - 1)                          # tail call, still a new frame

try:
    count_down(100_000)
except RecursionError:
    print("RecursionError: CPython has no tail-call optimization")

explicit_stack.py# Convert recursion to an EXPLICIT stack -> no depth limit, iterative control.
def sum_nested_recursive(x):
    if isinstance(x, int):
        return x
    return sum(sum_nested_recursive(c) for c in x)

def sum_nested_iterative(root):
    total, stack = 0, [root]
    while stack:                    # our own stack on the heap, not the call stack
        node = stack.pop()
        if isinstance(node, int):
            total += node
        else:
            stack.extend(node)      # push children
    return total

data = [1, [2, 3, [4, 5]], 6]
print("recursive:", sum_nested_recursive(data))   # 21
print("iterative:", sum_nested_iterative(data))   # 21

# The iterative version handles arbitrarily deep nesting without RecursionError.
deep = 1
for _ in range(50_000):
    deep = [deep]                    # 50k-deep nesting
print("deep sum:", sum_nested_iterative(deep))     # 1

memoization.pyfrom functools import lru_cache
import time

# Naive Fibonacci is exponential: O(phi^n) calls (recomputes the same subproblems).
def fib_slow(n):
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)

# Memoized: each n computed once -> O(n) time, O(n) space. Requires a PURE function.
@lru_cache(maxsize=None)
def fib_fast(n):
    return n if n < 2 else fib_fast(n - 1) + fib_fast(n - 2)

print("fib_fast(30):", fib_fast(30))      # 832040
print("cache:", fib_fast.cache_info())    # hits/misses show the reuse

# fib_slow(35) is already noticeably slow; fib_fast(100) is instant:
print("fib_fast(100):", fib_fast(100))    # 354224848179261915075

partial.pyfrom functools import partial

def power(base, exponent):
    return base ** exponent

# partial application: pre-fill some arguments to make a specialized function.
square = partial(power, exponent=2)
cube   = partial(power, exponent=3)
print("square(5):", square(5))     # 25
print("cube(2):", cube(2))         # 8

# "Currying" by hand: turn f(a, b) into f(a)(b) via nested closures.
def curry_add(a):
    return lambda b: a + b
print("curried:", curry_add(3)(4)) # 7

# partial is common for pre-configuring callbacks / API wrappers:
log_error = partial(print, "[ERROR]")
log_error("disk full")             # [ERROR] disk full