Base Cases & Recursive Cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

# Example 1: Simple countdown
# Progress measure: the value of n itself
def countdown(n: int) -> None:
    """
    Progress measure: μ(n) = n
    - Base case: n < 0 (when μ reaches below 0)
    - Recursive call: countdown(n-1), so μ decreases by 1
    - n can't decrease infinitely below 0 → terminates
    """
    if n < 0:
        return  # Base case
    print(n)
    countdown(n - 1)  # μ decreases from n to n-1
 
 
# Example 2: Array processing
# Progress measure: the length of the remaining array
def sum_array(arr: list[int]) -> int:
    """
    Progress measure: μ(arr) = len(arr)
    - Base case: len(arr) == 0 (when μ = 0)
    - Recursive call: sum_array(arr[1:]), so μ decreases by 1
    - Length can't go negative → terminates
    """
    if len(arr) == 0:
        return 0  # Base case: μ = 0
    return arr[0] + sum_array(arr[1:])  # μ: len(arr) → len(arr)-1
 
 
# Example 3: Binary search
# Progress measure: the size of the search space (high - low + 1)
def binary_search(arr: list[int], target: int, low: int, high: int) -> int:
    """
    Progress measure: μ(low, high) = max(0, high - low + 1)
    - Base case: low > high (when μ = 0)
    - Recursive calls: either (low, mid-1) or (mid+1, high)
      Both reduce the search space by at least half
    - Search space can't go negative → terminates
    """
    if low > high:
        return -1  # Base case: μ = 0
    
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif target < arr[mid]:
        return binary_search(arr, target, low, mid - 1)  # μ decreases
    else:
        return binary_search(arr, target, mid + 1, high)  # μ decreases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

# CASE 1: Single numeric parameter
def factorial(n: int) -> int:
    """
    Progress measure: μ(n) = n
    
    Analysis:
    - μ(n) = n ≥ 0 when n ≥ 0 (assuming valid input)
    - Base case: n ≤ 1, so μ reaches 1 or 0
    - Recursive: factorial(n-1), so μ(n-1) = n-1 < n = μ(n) ✓
    """
    if n <= 1:
        return 1
    return n * factorial(n - 1)
 
 
# CASE 2: Collection parameter
def reverse_string(s: str) -> str:
    """
    Progress measure: μ(s) = len(s)
    
    Analysis:
    - μ(s) = len(s) ≥ 0 always
    - Base case: len(s) ≤ 1, so μ ≤ 1
    - Recursive: reverse_string(s[1:]), so μ(s[1:]) = len(s)-1 < len(s) = μ(s) ✓
    """
    if len(s) <= 1:
        return s
    return s[-1] + reverse_string(s[:-1])
 
 
# CASE 3: Multiple parameters - use combined measure
def power(base: float, exponent: int) -> float:
    """
    Progress measure: μ(base, exponent) = exponent
    
    Analysis:
    - μ = exponent ≥ 0 (assuming non-negative exponent)
    - Base case: exponent == 0, so μ = 0
    - Recursive: power(base, exponent-1), so μ decreases by 1 ✓
    
    Note: 'base' doesn't change, only 'exponent' matters for progress.
    """
    if exponent == 0:
        return 1
    return base * power(base, exponent - 1)
 
 
# CASE 4: Two shrinking parameters
def lcs_length(s1: str, s2: str) -> int:
    """
    Longest Common Subsequence length.
    
    Progress measure: μ(s1, s2) = len(s1) + len(s2)
    
    Analysis:
    - μ = len(s1) + len(s2) ≥ 0 always
    - Base case: either string empty, so at least one length is 0
    - Recursive calls:
      - lcs_length(s1[1:], s2[1:]) when match: μ decreases by 2
      - lcs_length(s1[1:], s2): μ decreases by 1
      - lcs_length(s1, s2[1:]): μ decreases by 1
    - All recursive calls decrease μ ✓
    """
    if len(s1) == 0 or len(s2) == 0:
        return 0
    
    if s1[0] == s2[0]:
        return 1 + lcs_length(s1[1:], s2[1:])
    else:
        return max(lcs_length(s1[1:], s2), lcs_length(s1, s2[1:]))
 
 
# CASE 5: Tree structure
class TreeNode:
    def __init__(self, val: int):
        self.val = val
        self.left: 'TreeNode | None' = None
        self.right: 'TreeNode | None' = None
 
def tree_size(node: TreeNode | None) -> int:
    """
    Progress measure: μ(node) = number of nodes in subtree rooted at node
    
    Analysis:
    - μ(None) = 0, μ(leaf) = 1, μ(tree) = number of nodes ≥ 0
    - Base case: node is None, μ = 0
    - Recursive: tree_size(node.left) and tree_size(node.right)
      Both have strictly fewer nodes than the original tree ✓
    
    Alternative measure: height of subtree (also works)
    """
    if node is None:
        return 0
    return 1 + tree_size(node.left) + tree_size(node.right)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

from typing import List
 
def merge_sort(arr: List[int]) -> List[int]:
    """
    Sort array using merge sort algorithm.
    
    === TERMINATION PROOF ===
    
    1. Progress Measure:
       μ(arr) = len(arr)
    
    2. Non-Negativity:
       len(arr) ≥ 0 for any array (length is never negative)
    
    3. Base Case Boundary:
       Base case triggers when len(arr) ≤ 1
       This means μ ≤ 1 triggers termination
    
    4. Strict Decrease:
       Each recursive call passes arr[:mid] or arr[mid:]
       where mid = len(arr) // 2
       
       For len(arr) ≥ 2:
       - len(arr[:mid]) = mid < len(arr)        ✓
       - len(arr[mid:]) = len(arr) - mid < len(arr)  ✓
       
       Both halves are strictly smaller than the original.
    
    5. Conclusion:
       Since μ is a non-negative integer that:
       - Starts at len(arr) for any input
       - Decreases strictly with each recursive call
       - Triggers base case at μ ≤ 1
       
       Merge sort must terminate.
       
       Maximum recursion depth: ⌈log₂(n)⌉ where n = initial length
    """
    # Base case: arrays of length 0 or 1 are already sorted
    if len(arr) <= 1:
        return arr.copy()  # Return copy to avoid mutation
    
    # Split
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # μ decreases: mid < len(arr)
    right = merge_sort(arr[mid:])   # μ decreases: len(arr)-mid < len(arr)
    
    # Merge
    return merge(left, right)
 
 
def merge(left: List[int], right: List[int]) -> List[int]:
    """Merge two sorted arrays into one sorted array."""
    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
    
    # Append remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
 
# Visual: merge_sort([38, 27, 43, 3, 9, 82, 10])
#
# μ=7: [38, 27, 43, 3, 9, 82, 10]
#       ↙              ↘
# μ=3: [38, 27, 43]    μ=4: [3, 9, 82, 10]
#       ↙    ↘             ↙       ↘
# μ=1: [38]  μ=2: [27,43]  μ=2: [3,9]  μ=2: [82,10]
#            ↙    ↘       ↙   ↘      ↙    ↘
#       μ=1:[27] μ=1:[43] μ=1:[3] μ=1:[9] μ=1:[82] μ=1:[10]
#
# All paths reach μ=1 base case ✓

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# ❌ BROKEN: Parameter doesn't change
def broken_sum(arr: list[int], total: int = 0) -> int:
    if len(arr) == 0:
        return total
    # Bug: passing arr instead of arr[1:]
    return broken_sum(arr, total + arr[0])  # arr never shrinks!
 
# This will recurse forever on any non-empty array
 
 
# ❌ BROKEN: Wrong direction
def broken_countdown(n: int) -> None:
    if n == 0:
        return
    print(n)
    broken_countdown(n + 1)  # n increases! Never reaches 0
 
# countdown(5) → countdown(6) → countdown(7) → ... forever
 
 
# ❌ BROKEN: Subtle index error 
def broken_binary_search(arr: list[int], target: int, low: int, high: int) -> int:
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    if target < arr[mid]:
        return broken_binary_search(arr, target, low, mid)  # Bug: should be mid-1
    else:
        return broken_binary_search(arr, target, mid, high)  # Bug: should be mid+1
 
# When target < arr[mid] and low == mid, we call with same (low, mid)
# Infinite loop! Consider arr = [1, 2], target = 0, low = 0, high = 1
# mid = 0, 0 < arr[0]=1, search (0, 0) → mid = 0, search (0, 0) → ...
 
 
# ✅ CORRECT versions:
def correct_sum(arr: list[int]) -> int:
    if len(arr) == 0:
        return 0
    return arr[0] + correct_sum(arr[1:])  # arr shrinks by 1 each call ✓
 
def correct_binary_search(arr: list[int], target: int, low: int, high: int) -> int:
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    if target < arr[mid]:
        return correct_binary_search(arr, target, low, mid - 1)  # Exclude mid ✓
    else:
        return correct_binary_search(arr, target, mid + 1, high)  # Exclude mid ✓

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# ❌ BROKEN: Progress only in some branches
def broken_process(n: int, flag: bool) -> int:
    if n == 0:
        return 0
    
    if flag:
        return n + broken_process(n - 1, flag)  # Progress here ✓
    else:
        return n + broken_process(n, not flag)  # No progress! n unchanged
    
# If called with flag=False:
# broken_process(5, False) → broken_process(5, True) → broken_process(4, True) → ...
# This one eventually works because flag toggles, but consider:
 
def definitely_broken(n: int, flag: bool) -> int:
    if n == 0:
        return 0
    
    if flag:
        return n + definitely_broken(n - 1, flag)  # Progress
    else:
        return n + definitely_broken(n, flag)  # No progress AND flag doesn't change!
 
# definitely_broken(5, False) loops forever
 
 
# ✅ FIX: Ensure all branches make progress
def correct_process(n: int, flag: bool) -> int:
    if n == 0:
        return 0
    
    if flag:
        return n + correct_process(n - 1, flag)
    else:
        return n + correct_process(n - 1, not flag)  # Changed n to n-1 ✓

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

# PATTERN 1: Linear Decrease
# Progress: μ decreases by exactly 1 each call
def count_down(n: int) -> None:
    if n < 0:
        return
    print(n)
    count_down(n - 1)  # μ: n → n-1, decrease = 1
 
# Maximum depth: n+1 calls
 
 
# PATTERN 2: Logarithmic Decrease (Divide and Conquer)
# Progress: μ decreases by a factor each call
def binary_search_count(n: int) -> int:
    """Count how many times we can halve n before reaching 0."""
    if n <= 0:
        return 0
    return 1 + binary_search_count(n // 2)  # μ: n → n/2, halves
 
# Maximum depth: ⌈log₂(n)⌉ calls
 
 
# PATTERN 3: Multi-branch with consistent progress
# All branches must decrease μ
def fibonacci(n: int) -> int:
    if n <= 1:
        return n
    # Both branches decrease n:
    return fibonacci(n - 1) + fibonacci(n - 2)
    # μ: n → max(n-1, n-2) = n-1, still strictly less
 
# Note: Many CALLS (exponential), but each CALL makes progress
 
 
# PATTERN 4: Tree traversal (structural decrease)
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
def tree_sum(node: TreeNode | None) -> int:
    if node is None:
        return 0
    # Progress: subtrees are strictly smaller than the tree
    return node.val + tree_sum(node.left) + tree_sum(node.right)
 
# Progress measure: number of nodes in subtree
# μ(None) = 0, μ(node) = 1 + μ(left) + μ(right)
 
 
# PATTERN 5: Two-dimensional progress
def grid_paths(m: int, n: int) -> int:
    """Count paths in m×n grid from top-left to bottom-right."""
    # Base cases
    if m == 0 or n == 0:
        return 0
    if m == 1 and n == 1:
        return 1
    
    # Progress: at least one dimension decreases
    return grid_paths(m - 1, n) + grid_paths(m, n - 1)
 
# Progress measure: μ(m, n) = m + n
# Both recursive calls decrease μ by 1 ✓

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

def ackermann(m: int, n: int) -> int:
    """
    Ackermann function - grows extremely fast.
    
    Termination is non-obvious but provable with lexicographic ordering.
    
    Progress Measure: μ(m, n) = (m, n) with lexicographic comparison
    
    Case 1: m == 0
        Returns n + 1 (base case, no recursion)
    
    Case 2: m > 0 and n == 0
        Calls ackermann(m - 1, 1)
        μ goes from (m, 0) to (m-1, 1)
        Since m-1 < m, (m-1, 1) < (m, 0) lexicographically ✓
    
    Case 3: m > 0 and n > 0
        Calls ackermann(m, n - 1) to get some value k
            μ: (m, n) → (m, n-1)
            Since n-1 < n and m unchanged, (m, n-1) < (m, n) ✓
        Then calls ackermann(m - 1, k)
            μ: (m, n) → (m-1, k)
            Since m-1 < m, (m-1, k) < (m, n) regardless of k ✓
    
    All recursive calls decrease the lexicographic measure → terminates
    (But very slowly for large inputs - don't try ackermann(4, 2)!)
    """
    if m == 0:
        return n + 1
    elif n == 0:
        return ackermann(m - 1, 1)
    else:
        return ackermann(m - 1, ackermann(m, n - 1))
 
 
# A more practical example: GCD with subtraction
def gcd_subtract(a: int, b: int) -> int:
    """
    GCD using repeated subtraction (Euclidean algorithm variant).
    
    Progress Measure: μ(a, b) = max(a, b)
    
    Analysis:
    - Base case: a == b, return a
    - If a > b: gcd(a - b, b), new max = max(a-b, b) < a = old max
    - If b > a: gcd(a, b - a), new max = max(a, b-a) < b = old max
    
    The larger value always decreases → terminates
    """
    if a == b:
        return a
    elif a > b:
        return gcd_subtract(a - b, b)
    else:
        return gcd_subtract(a, b - a)
 
 
# Tuple progress example: sorting two numbers
def sort_pair_recursive(a: int, b: int, swaps: int = 0) -> tuple[int, int, int]:
    """
    Sort two numbers, counting swaps. Silly recursive version.
    
    Progress Measure: μ(a, b, swaps) = (out_of_order_count, swaps_remaining)
    where out_of_order_count = 1 if a > b else 0
    
    This is overkill for sorting two numbers, but illustrates the idea.
    """
    if a <= b:  # Already sorted
        return (a, b, swaps)
    else:  # Need to swap
        return sort_pair_recursive(b, a, swaps + 1)
    
# Only one swap ever needed, but shows lexicographic concept

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import sys
 
def mystery_recursive(arr: list[int], i: int = 0) -> int:
    """Function that might not terminate - let's debug it."""
    # DEBUG: Print progress measure
    print(f"  Call: i={i}, len(arr)={len(arr)}, progress={len(arr) - i}")
    
    if i >= len(arr):
        return 0
    
    if arr[i] % 2 == 0:
        return arr[i] + mystery_recursive(arr, i + 1)  # Progress ✓
    else:
        return mystery_recursive(arr, i)  # BUG: No progress when odd!
 
# Test with small input
# mystery_recursive([2, 3, 4])
# Output:
#   Call: i=0, len(arr)=3, progress=3
#   Call: i=1, len(arr)=3, progress=2
#   Call: i=1, len(arr)=3, progress=2  ← Same! i didn't increase
#   Call: i=1, len(arr)=3, progress=2
#   ... stack overflow
 
# The bug is clear: when arr[i] is odd, i doesn't increment
 
 
def add_depth_limit(func, max_depth=100):
    """Wrapper to detect infinite recursion."""
    call_count = [0]
    
    def wrapper(*args, **kwargs):
        call_count[0] += 1
        if call_count[0] > max_depth:
            raise RecursionError(f"Exceeded {max_depth} calls - likely infinite")
        return func(*args, **kwargs)
    
    return wrapper
 
# Usage:
# @add_depth_limit
# def my_recursive_func(...):
#     ...