Ensuring Progress Toward… — Base Cases & Recursive… | OneNoughtOne

0/97

Data Structures & AlgorithmsBase Cases & Recursive Cases

Base Cases & Recursive Cases

LevelBeginner

Duration60 mins

TopicBase Cases & Recursive Cases

3 / 4

Ensuring Progress Toward the Base Case

The Direction of Descent

Having a correct base case is necessary but not sufficient. Your recursion must actually reach that base case. Every recursive call must make measurable progress toward termination—otherwise, you have infinite recursion wearing a disguise. This page addresses the critical question: How do we guarantee that recursion terminates? The answer lies in understanding progress measures —properties of the problem that strictly decrease (or increase) with each recursive call until they reach the base case boundary. Think of it as fuel in a tank: if every call burns fuel but never refills, the car must eventually stop. We need to prove the tank empties.

What You Will Learn

By the end of this page, you will understand what it means for recursion to 'make progress,' how to identify and define progress measures, techniques for proving that recursion always terminates, how to detect when progress isn't being made, and patterns that ensure progress in different problem types.

The Termination Requirement

A recursive function terminates if and only if: There exists at least one base case that returns without recursing Every recursive call makes progress toward some base case Progress is bounded — the measure can't decrease infinitely The first condition we've covered. The second and third are about convergence : does the sequence of subproblems eventually hit a base case? Formal Reasoning: Well-Founded Relations In theoretical computer science, termination is proven using well-founded relations . A relation is well-founded if there are no infinite descending chains. For recursion, this means: Define a measure μ(input) \to ℕ (natural numbers: 0, 1, 2, ...) Show that for every recursive call: μ(new_input) < μ(current_input) Since natural numbers can't decrease infinitely (no negative integers), termination is guaranteed Practical Translation: Find something that: Is always non-negative (or has a lower bound) Decreases by at least 1 with each recursive call Reaches 0 (or the bound) at your base case

progress_measure_examples.py
Python
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

The Key Question

For any recursive function, ask: 'What quantity decreases with each recursive call?' If you can name it clearly and show it has a lower bound, your recursion terminates. If you can't, you may have a bug.

Defining Progress Measures

A progress measure (also called a variant or ranking function) is a function that maps your input to a non-negative integer, strictly decreasing with each recursive call. Common Progress Measures by Input Type:

Input Type	Typical Progress Measure
Integer n	The value n itself, or some function of n
Array/List	The length len(arr), or remaining elements
String	The length len(s), or remaining characters
Tree node	The height/depth, or the subtree size
Two indices [low, high]	The range size (high - low + 1)
Two strings	Sum of lengths, or combined remaining length

Properties of a Valid Progress Measure: Non-Negative : μ(input) \geq 0 for all valid inputs Strictly Decreasing : μ(recursive_input) < μ(current_input) for all recursive calls Zero at Base Case : When μ(input) = 0 (or minimum), we're at a base case Let's see this applied to increasingly complex examples:

progress_measures_defined.py
Python
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)

When Parameters Don't Change

Some parameters may stay constant across recursive calls (like 'base' in the power function). Only the parameters that affect termination need to be part of your progress measure. Focus on what's shrinking.

Proving Termination

For critical code, especially in interviews or formal settings, you may need to prove that your recursion terminates. Here's a systematic approach: The Termination Proof Template: State your progress measure : "Let μ(input) = ..." Show non-negativity : "μ(input) \geq 0 because..." Identify base case boundary : "The base case triggers when μ \leq k (typically k=0 or k=1)" Show strict decrease : "Each recursive call has μ(new) < μ(old) because..." Conclude : "Since μ is a non-negative integer that strictly decreases each call and has a lower bound, termination is guaranteed." Let's apply this to Merge Sort:

merge_sort_termination.py
Python
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 ✓

Interview Tip

In technical interviews, briefly mentioning 'the recursion terminates because the array size strictly decreases each call' demonstrates deeper understanding. Interviewers appreciate candidates who think about correctness, not just functionality.

Detecting When Progress Isn't Being Made

Some recursive calls look like they're making progress but aren't. These subtle bugs cause infinite recursion that's hard to detect by inspection. Learn to spot them: Red Flag 1: Unchanged Parameter If the recursive call passes the same input unchanged, progress isn't being made.

no_progress_examples.py
Python
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 ✓

Red Flag 2: Conditional Progress If progress only happens in some branches of a conditional, infinite loops can occur when those branches aren't taken.

conditional_progress.py
Python
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 ✓

Red Flags for Non-Progress

•Same parameter value: Recursive call uses identical input as current call
•Wrong direction: Parameter goes away from base case (increasing when should decrease)
•Off-by-one in ranges: Using mid instead of mid±1 in divide-and-conquer
•Conditional progress: Some code paths don't reduce the problem
•Mutual recursion cycles: A→B→A with no net progress
•Slice/copy confusion: Thinking arr[1:] modifies arr (it creates a new smaller list)

Ensuring Progress in Different Patterns

Different recursion patterns require different progress guarantees: Pattern 1: Linear Decrease The simplest pattern: decrement a counter or shrink a collection by one element.

progress_patterns.py
Python
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 ✓

Progress Patterns Summary
Pattern	Progress Measure	Decrease Rate	Max Depth
Linear decrease	n or len(arr)	-1 per call	O(n)
Divide and conquer	Size of range/array	÷2 per call	O(log n)
Multi-branch (Fibonacci)	n	-1 (along any path)	O(n) per path
Tree traversal	Number of nodes in subtree	At least -1	O(height)
2D recursion	Sum of dimensions	-1 per call	O(m+n)
Lexicographic	Tuple (a, b, c, ...)	First differs decreases	Depends on range

Advanced: Lexicographic Progress Measures

Some recursive functions can't be analyzed with a single decreasing number. Instead, we need lexicographic ordering on tuples. Lexicographic (Dictionary) Order: Tuples (a₁, a₂, ...) are compared like words in a dictionary: Compare first elements; if different, that determines order If equal, compare second elements, and so on (3, 5) < (4, 0) because 3 < 4 (first element differs) (3, 5) < (3, 6) because 3 = 3, then 5 < 6 When to Use: Use lexicographic measures when: One parameter sometimes increases while another decreases The function has complex control flow with multiple recursive paths Simple measures don't capture the progress pattern Example: Ackermann Function Structure The Ackermann function is a classic example where lexicographic ordering proves termination:

lexicographic_progress.py
Python
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

Lexicographic Ordering in Practice

Most everyday recursion uses simple decreasing measures. Lexicographic ordering is needed for functions like Ackermann or complex mutual recursion. The key insight: if the 'outer' measure decreases, any change to 'inner' measures is fine.

Debugging Non-Terminating Recursion

When your recursive function doesn't terminate (stack overflow or hanging), use these debugging strategies: Strategy 1: Add Progress Logging Print the progress measure at each call to see if it's decreasing:

debugging_recursion.py
Python
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(...):
#     ...

Strategy 2: Trace the First Few Calls Manually Before running code, trace by hand with a simple input: f(3) \to calls f(2) \to calls f(1) \to calls f(0) \to base case ✓ vs. f(3) \to calls f(3) \to calls f(3) \to ... infinite ✗ Strategy 3: Check All Recursive Call Sites For each recursive call in your function: What parameters are passed? Is at least one parameter strictly closer to a base case? Could any path pass unchanged parameters? Strategy 4: Set Python's Recursion Limit Low Reduce sys.setrecursionlimit(50) during debugging to fail fast.

Quick Debugging Checklist

•Add print statements showing your progress measure at each call
•Trace 3-5 calls by hand on paper before running
•Check EVERY recursive call site for proper parameter changes
•Test with the smallest non-base-case input first
•Set low recursion limits during development
•Use a call counter to detect excessive recursion early

Data Structures & AlgorithmsBase Cases & Recursive Cases

Base Cases & Recursive Cases

LevelBeginner

Duration60 mins

TopicBase Cases & Recursive Cases

3 / 4

Ensuring Progress Toward the Base Case

The Direction of Descent

Having a correct base case is necessary but not sufficient. Your recursion must actually reach that base case. Every recursive call must make measurable progress toward termination—otherwise, you have infinite recursion wearing a disguise. This page addresses the critical question: How do we guarantee that recursion terminates? The answer lies in understanding progress measures —properties of the problem that strictly decrease (or increase) with each recursive call until they reach the base case boundary. Think of it as fuel in a tank: if every call burns fuel but never refills, the car must eventually stop. We need to prove the tank empties.

What You Will Learn

By the end of this page, you will understand what it means for recursion to 'make progress,' how to identify and define progress measures, techniques for proving that recursion always terminates, how to detect when progress isn't being made, and patterns that ensure progress in different problem types.

The Termination Requirement

A recursive function terminates if and only if: There exists at least one base case that returns without recursing Every recursive call makes progress toward some base case Progress is bounded — the measure can't decrease infinitely The first condition we've covered. The second and third are about convergence : does the sequence of subproblems eventually hit a base case? Formal Reasoning: Well-Founded Relations In theoretical computer science, termination is proven using well-founded relations . A relation is well-founded if there are no infinite descending chains. For recursion, this means: Define a measure μ(input) \to ℕ (natural numbers: 0, 1, 2, ...) Show that for every recursive call: μ(new_input) < μ(current_input) Since natural numbers can't decrease infinitely (no negative integers), termination is guaranteed Practical Translation: Find something that: Is always non-negative (or has a lower bound) Decreases by at least 1 with each recursive call Reaches 0 (or the bound) at your base case

progress_measure_examples.py
Python
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

The Key Question

For any recursive function, ask: 'What quantity decreases with each recursive call?' If you can name it clearly and show it has a lower bound, your recursion terminates. If you can't, you may have a bug.

Defining Progress Measures

A progress measure (also called a variant or ranking function) is a function that maps your input to a non-negative integer, strictly decreasing with each recursive call. Common Progress Measures by Input Type:

Input Type	Typical Progress Measure
Integer n	The value n itself, or some function of n
Array/List	The length len(arr), or remaining elements
String	The length len(s), or remaining characters
Tree node	The height/depth, or the subtree size
Two indices [low, high]	The range size (high - low + 1)
Two strings	Sum of lengths, or combined remaining length

Properties of a Valid Progress Measure: Non-Negative : μ(input) \geq 0 for all valid inputs Strictly Decreasing : μ(recursive_input) < μ(current_input) for all recursive calls Zero at Base Case : When μ(input) = 0 (or minimum), we're at a base case Let's see this applied to increasingly complex examples:

progress_measures_defined.py
Python
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)

When Parameters Don't Change

Some parameters may stay constant across recursive calls (like 'base' in the power function). Only the parameters that affect termination need to be part of your progress measure. Focus on what's shrinking.

Proving Termination

For critical code, especially in interviews or formal settings, you may need to prove that your recursion terminates. Here's a systematic approach: The Termination Proof Template: State your progress measure : "Let μ(input) = ..." Show non-negativity : "μ(input) \geq 0 because..." Identify base case boundary : "The base case triggers when μ \leq k (typically k=0 or k=1)" Show strict decrease : "Each recursive call has μ(new) < μ(old) because..." Conclude : "Since μ is a non-negative integer that strictly decreases each call and has a lower bound, termination is guaranteed." Let's apply this to Merge Sort:

merge_sort_termination.py
Python
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 ✓

Interview Tip

In technical interviews, briefly mentioning 'the recursion terminates because the array size strictly decreases each call' demonstrates deeper understanding. Interviewers appreciate candidates who think about correctness, not just functionality.

Detecting When Progress Isn't Being Made

Some recursive calls look like they're making progress but aren't. These subtle bugs cause infinite recursion that's hard to detect by inspection. Learn to spot them: Red Flag 1: Unchanged Parameter If the recursive call passes the same input unchanged, progress isn't being made.

no_progress_examples.py
Python
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 ✓

Red Flag 2: Conditional Progress If progress only happens in some branches of a conditional, infinite loops can occur when those branches aren't taken.

conditional_progress.py
Python
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 ✓

Red Flags for Non-Progress

•Same parameter value: Recursive call uses identical input as current call
•Wrong direction: Parameter goes away from base case (increasing when should decrease)
•Off-by-one in ranges: Using mid instead of mid±1 in divide-and-conquer
•Conditional progress: Some code paths don't reduce the problem
•Mutual recursion cycles: A→B→A with no net progress
•Slice/copy confusion: Thinking arr[1:] modifies arr (it creates a new smaller list)

Ensuring Progress in Different Patterns

Different recursion patterns require different progress guarantees: Pattern 1: Linear Decrease The simplest pattern: decrement a counter or shrink a collection by one element.

progress_patterns.py
Python
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 ✓

Progress Patterns Summary
Pattern	Progress Measure	Decrease Rate	Max Depth
Linear decrease	n or len(arr)	-1 per call	O(n)
Divide and conquer	Size of range/array	÷2 per call	O(log n)
Multi-branch (Fibonacci)	n	-1 (along any path)	O(n) per path
Tree traversal	Number of nodes in subtree	At least -1	O(height)
2D recursion	Sum of dimensions	-1 per call	O(m+n)
Lexicographic	Tuple (a, b, c, ...)	First differs decreases	Depends on range

Advanced: Lexicographic Progress Measures

Some recursive functions can't be analyzed with a single decreasing number. Instead, we need lexicographic ordering on tuples. Lexicographic (Dictionary) Order: Tuples (a₁, a₂, ...) are compared like words in a dictionary: Compare first elements; if different, that determines order If equal, compare second elements, and so on (3, 5) < (4, 0) because 3 < 4 (first element differs) (3, 5) < (3, 6) because 3 = 3, then 5 < 6 When to Use: Use lexicographic measures when: One parameter sometimes increases while another decreases The function has complex control flow with multiple recursive paths Simple measures don't capture the progress pattern Example: Ackermann Function Structure The Ackermann function is a classic example where lexicographic ordering proves termination:

lexicographic_progress.py
Python
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

Lexicographic Ordering in Practice

Most everyday recursion uses simple decreasing measures. Lexicographic ordering is needed for functions like Ackermann or complex mutual recursion. The key insight: if the 'outer' measure decreases, any change to 'inner' measures is fine.

Debugging Non-Terminating Recursion

When your recursive function doesn't terminate (stack overflow or hanging), use these debugging strategies: Strategy 1: Add Progress Logging Print the progress measure at each call to see if it's decreasing:

debugging_recursion.py
Python
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(...):
#     ...

Strategy 2: Trace the First Few Calls Manually Before running code, trace by hand with a simple input: f(3) \to calls f(2) \to calls f(1) \to calls f(0) \to base case ✓ vs. f(3) \to calls f(3) \to calls f(3) \to ... infinite ✗ Strategy 3: Check All Recursive Call Sites For each recursive call in your function: What parameters are passed? Is at least one parameter strictly closer to a base case? Could any path pass unchanged parameters? Strategy 4: Set Python's Recursion Limit Low Reduce sys.setrecursionlimit(50) during debugging to fail fast.

Quick Debugging Checklist

•Add print statements showing your progress measure at each call
•Trace 3-5 calls by hand on paper before running
•Check EVERY recursive call site for proper parameter changes
•Test with the smallest non-base-case input first
•Set low recursion limits during development
•Use a call counter to detect excessive recursion early

Ensuring Progress Toward the Base Case

The Direction of Descent

The Termination Requirement

Defining Progress Measures

Proving Termination

Detecting When Progress Isn't Being Made

Ensuring Progress in Different Patterns

Advanced: Lexicographic Progress Measures

Debugging Non-Terminating Recursion

There’s more to understand.

Ensuring Progress Toward the Base Case

The Direction of Descent

The Termination Requirement

Defining Progress Measures

Proving Termination

Detecting When Progress Isn't Being Made

Ensuring Progress in Different Patterns

Advanced: Lexicographic Progress Measures

Debugging Non-Terminating Recursion

There’s more to understand.