Functions and Procedures — Specification¶

def modify(lst, num):
    lst.append(4)     # Modifies original list (by sharing)
    num = num + 10    # Does NOT modify original int (integers are immutable)

my_list = [1, 2, 3]
my_num = 5
modify(my_list, my_num)
print(my_list)  # [1, 2, 3, 4]  — list was mutated
print(my_num)   # 5             — int was not changed

# Functions as first-class objects in Python
def apply_twice(f, x):
    """Higher-order: takes function f as argument."""
    return f(f(x))

double = lambda x: x * 2
print(apply_twice(double, 3))   # double(double(3)) = double(6) = 12

# Map: applies f to each element
result = list(map(lambda x: x**2, [1, 2, 3, 4]))  # [1, 4, 9, 16]

# Filter: keeps elements where f is True
evens = list(filter(lambda x: x % 2 == 0, range(10)))  # [0, 2, 4, 6, 8]

# Reduce: fold over sequence
from functools import reduce
product = reduce(lambda a, b: a * b, [1, 2, 3, 4, 5])  # 120

# NOT tail-recursive: multiplication after recursive call
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)   # multiply happens AFTER return from recursion

# TAIL-RECURSIVE: accumulator carries the result
def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, n * acc)   # recursive call IS the last operation

# Naive Fibonacci — exponential time T(n) = T(n-1) + T(n-2) + O(1) → O(2ⁿ)
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# Memoized Fibonacci — O(n) time, O(n) space
def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]           # O(1) lookup
    if n <= 1:
        return n
    result = fib_memo(n-1, cache) + fib_memo(n-2, cache)
    cache[n] = result             # Store result
    return result

# Python standard library: functools.lru_cache
from functools import lru_cache

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

# WRONG: default list is created ONCE, shared across all calls
def append_to(element, lst=[]):
    lst.append(element)
    return lst

print(append_to(1))  # [1]
print(append_to(2))  # [1, 2] — unexpected! lst persists between calls

# CORRECT: use None as sentinel, create new list each call
def append_to(element, lst=None):
    if lst is None:
        lst = []
    lst.append(element)
    return lst

import sys
print(sys.getrecursionlimit())  # Default: 1000 in CPython

# For deep recursion, increase limit (risky — may crash Python):
sys.setrecursionlimit(10000)

# Better: convert recursive to iterative using explicit stack
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Every path must reach a base case:
def bad_recursion(n):
    if n == 0:
        return 0
    return bad_recursion(n + 1)  # n grows away from base case!
    # RecursionError for any n > 0

# Correct: ensure n approaches base case
def good_recursion(n):
    if n == 0:
        return 0
    return good_recursion(n - 1)  # n decreases toward 0

# Requires both functions to be defined before either is called
def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)

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

# is_even(4) → is_odd(3) → is_even(2) → is_odd(1) → is_even(0) → True
# Recursion depth: O(n) — could use O(1) with n % 2 == 0

def make_adder(n):
    """Returns a function that adds n to its argument."""
    def adder(x):
        return x + n    # 'n' is captured from enclosing scope
    return adder

add5 = make_adder(5)
print(add5(3))   # 8 — closure retains reference to n=5

# Gotcha: late binding in loops
funcs = [lambda x: x + i for i in range(3)]
print([f(0) for f in funcs])  # [2, 2, 2] — all capture same 'i' (= 2 at end of loop)

# Fix: use default argument to bind at creation time
funcs = [lambda x, i=i: x + i for i in range(3)]
print([f(0) for f in funcs])  # [0, 1, 2]

# Recursive DFS
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

# Iterative DFS — equivalent, using explicit stack
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()          # LIFO — mimics call stack
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

# T(n) = T(n-1) + O(1) → O(n)  [linear recursion]
def sum_recursive(A, n):
    if n == 0:
        return 0
    return A[n-1] + sum_recursive(A, n-1)

# T(n) = 2T(n/2) + O(n) → O(n log n)  [divide and conquer]
def merge_sort(A):
    if len(A) <= 1:
        return A
    mid = len(A) // 2
    left = merge_sort(A[:mid])
    right = merge_sort(A[mid:])
    return merge(left, right)

# T(n) = 2T(n-1) + O(1) → O(2ⁿ)  [exponential — avoid!]
def bad_fib(n):
    if n <= 1:
        return n
    return bad_fib(n-1) + bad_fib(n-2)   # 2 recursive calls, depth n

# Default parameters
def greet(name, greeting="Hello"):
    return f"{greeting}, {name}!"

# *args — variable positional arguments
def sum_all(*args):
    return sum(args)

# **kwargs — variable keyword arguments
def print_info(**kwargs):
    for key, value in kwargs.items():
        print(f"{key}: {value}")

# Type annotations (PEP 484)
def factorial(n: int) -> int:
    if n == 0:
        return 1
    return n * factorial(n - 1)

# Generator function (lazy evaluation)
def fibonacci_gen():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

# Lambda (anonymous function)
square = lambda x: x ** 2
print(square(5))  # 25

def factorial(n: int) -> int:
    """
    Computes n! recursively.
    Time:  O(n) — n recursive calls
    Space: O(n) — n stack frames
    """
    if n == 0:           # Base case
        return 1
    return n * factorial(n - 1)  # Recursive case

def binary_search(A: list, x) -> int:
    """
    Recursive binary search.
    Precondition:  A is sorted in non-decreasing order
    Postcondition: Returns index i where A[i] == x, or -1
    Time:  O(log n) — T(n) = T(n/2) + O(1)
    Space: O(log n) — recursion depth
    """
    def search(low, high):
        if low > high:
            return -1
        mid = (low + high) // 2
        if A[mid] == x:
            return mid
        elif A[mid] < x:
            return search(mid + 1, high)
        else:
            return search(low, mid - 1)

    return search(0, len(A) - 1)

def merge_sort(A: list) -> list:
    """
    Divide-and-conquer sort.
    Precondition:  A is a list of comparable elements
    Postcondition: Returns a new list with elements in non-decreasing order
    Time:  T(n) = 2T(n/2) + Θ(n) = Θ(n log n)  [Master Theorem, Case 2]
    Space: O(n)   — auxiliary arrays for merge
    """
    if len(A) <= 1:
        return A                    # Base case

    mid = len(A) // 2               # Divide
    left = merge_sort(A[:mid])      # Conquer left
    right = merge_sort(A[mid:])     # Conquer right
    return merge(left, right)       # Combine

def merge(left: list, right: list) -> list:
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def hanoi(n: int, source: str, auxiliary: str, destination: str) -> None:
    """
    Tower of Hanoi with n disks.
    Time: O(2ⁿ) — minimum 2ⁿ-1 moves required
    """
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return
    hanoi(n - 1, source, destination, auxiliary)
    print(f"Move disk {n} from {source} to {destination}")
    hanoi(n - 1, auxiliary, source, destination)