Incorrect Base Cases — Debugging Algorithmic Code | OneNoughtOne

0/97

Data Structures & AlgorithmsDebugging Algorithmic Code

Debugging Algorithmic Code

LevelIntermediate

Duration75 mins

TopicDebugging Algorithmic Code

4 / 5

Incorrect Base Cases

The Foundation That Must Not Crack

In recursion and dynamic programming, the base case is everything. It's the foundation upon which all other computations build. If your recurrence relation is correct but your base case is wrong, your algorithm will systematically produce incorrect answers—sometimes subtly wrong, sometimes completely wrong. The Insidious Nature of Base Case Bugs Base case errors are particularly dangerous because: The recursive logic often looks correct The algorithm may work for "normal" inputs Failure only manifests for specific edge cases (empty, single-element, etc.) The error compounds: a wrong base case corrupts all dependent computations This makes base case bugs feel like logic errors in your recurrence, leading you to debug the wrong part of your code.

What You Will Master

This page provides a systematic approach to base case design. You'll learn to identify all necessary base cases, derive their correct values, verify consistency with your recurrence, and test comprehensively. By the end, you'll treat base case design as a critical first step, not an afterthought.

Understanding Base Cases

A base case is a condition where a recursive function returns a direct answer without making further recursive calls. Base cases serve two essential purposes: Termination: Without base cases, recursion would continue infinitely Foundation: Base cases provide the seed values that all recursive computations build upon Anatomy of Recursive Solutions Every recursive solution has two parts: function solve(problem): if is_base_case(problem): # Base case check return base_case_answer # Direct answer, no recursion else: smaller_problems = decompose(problem) sub_answers = [solve(p) for p in smaller_problems] # Recursive calls return combine(sub_answers) # Combine results The correctness of solve depends critically on: Correctly identifying ALL base cases (not just some) Returning the RIGHT value for each base case Ensuring the recurrence relation reaches base cases for all valid inputs

Properties of Correct Base Cases

•Exhaustive: All input patterns that cannot be decomposed further are covered.
•Minimal: Base cases represent the smallest meaningful problem instances.
•Correct: Each base case returns the mathematically correct answer for that specific input.
•Reachable: The recursive decomposition eventually reaches base cases for all valid inputs.
•Consistent: Base case definitions align with how the recurrence relation uses sub-results.

The Consistency Requirement

A base case isn't just 'an answer for small inputs'—it must be the CORRECT answer that makes your recurrence relation work. If your recurrence computes dp[i] = dp[i-1] + dp[i-2], then dp[0] and dp[1] must be defined such that dp[2] computed from them is correct.

Common Base Case Error Patterns

Let's examine the most frequent base case mistakes and how they manifest.

Taxonomy of Base Case Errors
Error Type	Description	Typical Symptom
Missing Base Case	A condition that should return directly but doesn't	Stack overflow or infinite recursion
Incomplete Base Cases	Some edge cases covered, others not	Correct for some inputs, wrong for edges
Wrong Base Value	Base case exists but returns wrong value	Systematic offset in all results
Inconsistent Base	Base case value doesn't match recurrence semantics	Wrong answer propagates through recursion
Off-by-One Base	Base case index is shifted (dp[0] vs dp[1])	All results shifted by one position
Premature Base Case	Returns base value too early, missing work	Missing computation for smallest cases

base_case_errors.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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
# === ERROR 1: Missing Base Case ===
 
# BUGGY: No base case for empty string
def count_substrings_buggy(s: str) -> int:
    """Count all possible substrings."""
    if len(s) == 1:  # Only one base case
        return 1
    
    # BUG: What if s is empty? This will call count_substrings("") which
    # doesn't match len(s) == 1, leads to index errors or infinite recursion
    return len(s) + count_substrings_buggy(s[1:])
 
# CORRECT: Handle all minimal cases
def count_substrings_correct(s: str) -> int:
    if len(s) == 0:  # MISSING BASE CASE added
        return 0
    if len(s) == 1:
        return 1
    return len(s) + count_substrings_correct(s[1:])
 
 
# === ERROR 2: Wrong Base Value ===
 
# BUGGY: Wrong base case for Fibonacci
def fibonacci_buggy(n: int) -> int:
    if n <= 0:
        return 0
    if n == 1:
        return 0  # BUG: fib(1) should be 1, not 0!
    return fibonacci_buggy(n - 1) + fibonacci_buggy(n - 2)
 
# Test: fib(2) = fib(1) + fib(0) = 0 + 0 = 0 (should be 1!)
# All Fibonacci numbers will be wrong.
 
# CORRECT: Proper Fibonacci base cases
def fibonacci_correct(n: int) -> int:
    if n <= 0:
        return 0  # fib(0) = 0
    if n == 1:
        return 1  # fib(1) = 1
    return fibonacci_correct(n - 1) + fibonacci_correct(n - 2)
 
 
# === ERROR 3: Inconsistent Base with Recurrence ===
 
# Recurrence: dp[i] represents min cost to reach step i from step 0
# dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
 
# BUGGY: Base case doesn't match recurrence semantics
def min_cost_climbing_buggy(cost: list) -> int:
    n = len(cost)
    dp = [0] * (n + 1)
    
    dp[0] = cost[0]  # BUG: dp[0] should be 0 (no cost to be at step 0)
    dp[1] = cost[1]  # BUG: dp[1] should consider coming from step 0
    
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    
    return dp[n]  # Wrong answer due to wrong base cases
 
# CORRECT: Base cases match recurrence semantics
def min_cost_climbing_correct(cost: list) -> int:
    n = len(cost)
    dp = [0] * (n + 1)
    
    # dp[i] = minimum cost to reach step i
    # You start on step 0 or step 1 with no prior cost
    dp[0] = 0  # Cost to be at step 0 before any move
    dp[1] = 0  # Cost to be at step 1 before any move (can start here)
    
    for i in range(2, n + 1):
        # To reach step i: come from i-1 (pay cost[i-1]) or i-2 (pay cost[i-2])
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    
    return dp[n]
 
 
# === ERROR 4: Off-by-One in Base Case Index ===
 
# Problem: Compute number of ways to climb n stairs (1 or 2 steps at a time)
 
# BUGGY: Base case indexing mismatch
def climb_stairs_buggy(n: int) -> int:
    if n <= 0:
        return 0  # BUG: What does this mean?
    
    dp = [0] * (n + 1)
    dp[0] = 0  # BUG: There IS one way to stay at step 0 (do nothing)
    dp[1] = 1
    # dp[2] = dp[1] + dp[0] = 1 + 0 = 1 (should be 2!)
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]  # Wrong!
 
# CORRECT: Think about what dp[i] means
def climb_stairs_correct(n: int) -> int:
    if n <= 0:
        return 0 if n < 0 else 1  # 1 way to climb 0 stairs: do nothing
    
    dp = [0] * (n + 1)
    
    # dp[i] = number of ways to reach step i
    dp[0] = 1  # One way to be at step 0: start there
    dp[1] = 1  # One way to reach step 1: take one step
    # dp[2] = dp[1] + dp[0] = 1 + 1 = 2 (1+1 or 2) ✓
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

Systematic Base Case Design

Instead of guessing base cases and hoping they're right, follow a systematic design process. The Base Case Design Algorithm Define what your function/dp computes precisely — Write down in plain English what the return value represents. Identify the smallest valid inputs — What's the minimal problem size? (Empty, single element, etc.) Compute answers for smallest inputs by definition — Using your definition from step 1, what IS the answer for each minimal case? Verify consistency with recurrence — Does your recurrence correctly compute dp[2] from dp[0] and dp[1]? Trace through manually. Check all edge conditions — Are there special cases the recurrence doesn't handle naturally?

systematic_design.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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
# === EXAMPLE: Designing Base Cases for Coin Change ===
 
# PROBLEM: Find minimum number of coins to make amount.
# If impossible, return -1.
 
# STEP 1: Define precisely what we compute
# dp[amount] = minimum number of coins needed to make exactly 'amount'
# If impossible, dp[amount] = infinity (or some sentinel)
 
# STEP 2: Identify smallest valid inputs
# Smallest amount: 0
# What about negative amounts? Invalid input, handle separately.
 
# STEP 3: Compute by definition
# dp[0] = 0 (zero coins needed to make amount 0)
# This is THE key insight many miss!
 
# STEP 4: Define recurrence
# dp[i] = min(dp[i - coin] + 1) for all coins where i >= coin
# Verify: dp[5] with coins=[1,2,5]
#   = min(dp[4] + 1, dp[3] + 1, dp[0] + 1)
#   = min(dp[4] + 1, dp[3] + 1, 0 + 1)
#   = uses dp[0] = 0 correctly ✓
 
def coin_change_correct(coins: list, amount: int) -> int:
    """Minimum coins to make amount."""
    INF = float('inf')
    
    # dp[i] = minimum coins to make exactly i
    dp = [INF] * (amount + 1)
    
    # BASE CASE: 0 coins needed for amount 0
    dp[0] = 0
    
    # Fill DP table
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != INF:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != INF else -1
 
 
# === EXAMPLE: Designing Base Cases for Longest Common Subsequence ===
 
# PROBLEM: Find length of longest common subsequence of two strings.
 
# STEP 1: Define precisely
# dp[i][j] = length of LCS of text1[0:i] and text2[0:j]
# Note: 0:i means first i characters (indices 0 to i-1)
 
# STEP 2: Smallest valid inputs
# i = 0: text1[0:0] is empty string
# j = 0: text2[0:0] is empty string
 
# STEP 3: Compute by definition
# dp[0][j] = LCS of "" and text2[0:j] = 0 (nothing in common with empty)
# dp[i][0] = LCS of text1[0:i] and "" = 0 (nothing in common with empty)
 
# STEP 4: Define recurrence (for i, j > 0)
# If text1[i-1] == text2[j-1]:  (last chars match)
#     dp[i][j] = dp[i-1][j-1] + 1
# Else:
#     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 
def lcs_correct(text1: str, text2: str) -> int:
    """Length of longest common subsequence."""
    m, n = len(text1), len(text2)
    
    # dp[i][j] = LCS length of text1[0:i] and text2[0:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # BASE CASES: First row and first column are all 0
    # Already initialized by [[0] * (n+1) for ...]
    # dp[0][j] = 0 for all j (empty text1)
    # dp[i][0] = 0 for all i (empty text2)
    
    # Fill table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]
 
 
# === EXAMPLE: Designing Base Cases for Binary Search Tree Count ===
 
# PROBLEM: Count number of structurally unique BSTs with n nodes (values 1 to n)
# This is the nth Catalan number.
 
# STEP 1: Define precisely
# dp[n] = number of unique BSTs with n nodes
 
# STEP 2: Smallest valid inputs
# n = 0: No nodes
# n = 1: Single node
 
# STEP 3: Compute by definition
# dp[0] = 1 (ONE empty tree - this is the tricky one!)
#         The empty tree is a valid BST structure.
#         This is necessary for the recurrence to work.
# dp[1] = 1 (one tree with just the root)
 
# STEP 4: Recurrence
# For n nodes with root value k (1 <= k <= n):
#   Left subtree: k-1 nodes (values 1 to k-1)
#   Right subtree: n-k nodes (values k+1 to n)
#   dp[n] = sum(dp[k-1] * dp[n-k]) for k = 1 to n
 
# Verify: dp[2] = dp[0]*dp[1] + dp[1]*dp[0] = 1*1 + 1*1 = 2 ✓
# (Either root is 1 with right child 2, or root is 2 with left child 1)
 
def num_trees_correct(n: int) -> int:
    """Count unique BSTs with n nodes."""
    dp = [0] * (n + 1)
    
    # BASE CASES
    dp[0] = 1  # Empty tree (crucial for recurrence!)
    dp[1] = 1  # Single node tree
    
    for nodes in range(2, n + 1):
        for root in range(1, nodes + 1):
            left_subtrees = dp[root - 1]      # nodes in left subtree
            right_subtrees = dp[nodes - root]  # nodes in right subtree
            dp[nodes] += left_subtrees * right_subtrees
    
    return dp[n]

The dp[0] = 1 Pattern

Many counting problems require dp[0] = 1 (not 0) because 'there is one way to do nothing' or 'the empty set is a valid selection'. This is counterintuitive but mathematically correct. If your recurrence involves products or counts of combinations, check if dp[0] = 1 is the right base case.

Base Cases Across Algorithmic Paradigms

Different algorithmic paradigms have characteristic base case patterns. Understanding these patterns accelerates correct design.

Divide and Conquer algorithms split problems into smaller subproblems, solve them recursively, and combine results. Base cases are typically: Size 0 or 1: Problems too small to divide further Direct computation: When the problem is trivially solvable

divide_conquer_base.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
# === MERGE SORT ===
def merge_sort(arr: list) -> list:
    """Sort array using divide and conquer."""
    # BASE CASE: 0 or 1 elements are already sorted
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
 
# === BINARY SEARCH (Recursive) ===
def binary_search_recursive(arr: list, target: int, left: int, right: int) -> int:
    """Find target in sorted array."""
    # BASE CASE 1: Empty search space
    if left > right:
        return -1  # Not found
    
    mid = left + (right - left) // 2
    
    # BASE CASE 2: Found the target
    if arr[mid] == target:
        return mid
    
    # Recursive cases
    if arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)
 
 
# === MAXIMUM SUBARRAY (Divide and Conquer) ===
def max_subarray_dc(arr: list, left: int, right: int) -> int:
    """Find maximum sum subarray using divide and conquer."""
    # BASE CASE: Single element
    if left == right:
        return arr[left]
    
    mid = (left + right) // 2
    
    # Maximum in left half, right half, or crossing the middle
    left_max = max_subarray_dc(arr, left, mid)
    right_max = max_subarray_dc(arr, mid + 1, right)
    cross_max = max_crossing_sum(arr, left, mid, right)
    
    return max(left_max, right_max, cross_max)

Verifying Base Case Correctness

How do you know your base cases are correct? Here are systematic verification techniques.

Base Case Verification Checklist

•Manual Computation Test: Compute dp[2] or the smallest non-base case by hand using your base cases. Does it match the expected answer?
•Definition Consistency: Re-read your dp definition. Does each base case value match what the definition says for that input?
•Edge Input Tests: Test with empty input, single element, two elements, all zeros, all identical values.
•Recurrence Trace: Trace backward from a known answer. If dp[5] should be X, does dp[5] = f(dp[4], dp[3], ...) actually compute X?
•Mathematical Identity: For problems with known formulas, verify: Fibonacci should give 0,1,1,2,3,5,8... Catalan numbers should give 1,1,2,5,14,42...

base_case_verification.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
# === VERIFICATION BY MANUAL TRACE ===
 
def verify_climb_stairs():
    """
    Verify climb stairs base cases by manual computation.
    
    dp[n] = number of ways to climb n stairs (1 or 2 steps at a time)
    Recurrence: dp[n] = dp[n-1] + dp[n-2]
    """
    
    # Our base cases:
    dp_0 = 1  # 1 way to climb 0 stairs: do nothing
    dp_1 = 1  # 1 way to climb 1 stair: take one step
    
    # Manual verification of non-base cases:
    # dp[2] = dp[1] + dp[0] = 1 + 1 = 2
    # Expected: 2 ways (1+1 or 2)
    assert dp_1 + dp_0 == 2, "dp[2] is wrong!"
    
    # dp[3] = dp[2] + dp[1] = 2 + 1 = 3
    # Expected: 3 ways (1+1+1, 1+2, 2+1)
    dp_2 = 2
    assert dp_2 + dp_1 == 3, "dp[3] is wrong!"
    
    # dp[4] = dp[3] + dp[2] = 3 + 2 = 5
    # Expected: 5 ways (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)
    dp_3 = 3
    assert dp_3 + dp_2 == 5, "dp[4] is wrong!"
    
    print("Base cases verified!")
 
 
# === VERIFICATION BY KNOWN SEQUENCES ===
 
def verify_fibonacci_base():
    """Verify Fibonacci base cases against known sequence."""
    known_fib = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
    
    def fib(n):
        if n <= 0:
            return 0
        if n == 1:
            return 1
        return fib(n - 1) + fib(n - 2)
    
    for i, expected in enumerate(known_fib):
        computed = fib(i)
        assert computed == expected, f"fib({i}) = {computed}, expected {expected}"
    
    print("Fibonacci base cases verified!")
 
 
# === VERIFICATION BY EDGE CASES ===
 
def verify_coin_change_base():
    """Verify coin change handles edge cases correctly."""
    
    def coin_change(coins, amount):
        INF = float('inf')
        dp = [INF] * (amount + 1)
        dp[0] = 0  # Base case
        
        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i and dp[i - coin] != INF:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return dp[amount] if dp[amount] != INF else -1
    
    # Edge case 1: amount = 0
    assert coin_change([1, 2, 5], 0) == 0, "0 coins for amount 0"
    
    # Edge case 2: single coin equals amount
    assert coin_change([5], 5) == 1, "one coin for exact amount"
    
    # Edge case 3: impossible amount
    assert coin_change([2], 3) == -1, "impossible with only 2s"
    
    # Edge case 4: empty coins (any positive amount impossible)
    assert coin_change([], 5) == -1, "impossible with no coins"
    assert coin_change([], 0) == 0, "0 coins for amount 0, even with no coins"
    
    print("Coin change base cases verified!")
 
 
# Run verifications
verify_climb_stairs()
verify_fibonacci_base()
verify_coin_change_base()

Base Case Patterns by Problem Type

Certain problem types have characteristic base case patterns. Recognizing these accelerates correct design.

Base Case Patterns by Problem Category
Problem Category	Typical Base Case	Common Mistake
Counting Ways	dp[0] = 1 (one way to do nothing)	dp[0] = 0
Finding Minimum	dp[0] = 0 or dp[target] = 0	dp[0] = 1 or forgetting infinity for impossible
Finding Maximum	dp[0] = 0 or -∞ for 'must include'	Forgetting negative infinity for 'must include'
String Matching (2D)	dp[i][0] and dp[0][j] for empty strings	Only initializing dp[0][0]
Tree Recursion	if node is None: return identity	Forgetting null check, causing NoneType error
Graph DFS/BFS	visited[start] = True before recursion	Marking visited after processing, causing cycles
Binary Search	left > right means empty range	left >= right (loses the single-element case)

pattern_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
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
95
96
97
98
99
100
101
102
103
104
105
# === COUNTING WAYS: dp[0] = 1 ===
 
def unique_paths(m: int, n: int) -> int:
    """Count paths in m×n grid from top-left to bottom-right."""
    dp = [[1] * n for _ in range(m)]  # First row and column: 1 way each
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]
 
 
def count_subsets_with_sum(nums: list, target: int) -> int:
    """Count subsets that sum to target."""
    dp = [0] * (target + 1)
    dp[0] = 1  # ONE way to make sum 0: empty subset
    
    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] += dp[s - num]
    
    return dp[target]
 
 
# === FINDING MINIMUM: dp[0] = 0, others = infinity ===
 
def min_jumps_to_end(nums: list) -> int:
    """Minimum jumps to reach end of array."""
    n = len(nums)
    INF = float('inf')
    
    dp = [INF] * n
    dp[0] = 0  # 0 jumps to reach position 0
    
    for i in range(n):
        if dp[i] == INF:
            continue
        for j in range(1, nums[i] + 1):
            if i + j < n:
                dp[i + j] = min(dp[i + j], dp[i] + 1)
    
    return dp[n-1] if dp[n-1] != INF else -1
 
 
# === STRING DP: Initialize entire row/column ===
 
def is_interleaving(s1: str, s2: str, s3: str) -> bool:
    """Check if s3 is interleaving of s1 and s2."""
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    
    # dp[i][j] = True if s3[0:i+j] is interleaving of s1[0:i] and s2[0:j]
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # BASE CASE: dp[0][0] = True (empty matches empty)
    dp[0][0] = True
    
    # BASE CASE: First column (using only s1)
    for i in range(1, m + 1):
        dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
    
    # BASE CASE: First row (using only s2)
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
    
    # Fill rest
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or \
                       (dp[i][j-1] and s2[j-1] == s3[i+j-1])
    
    return dp[m][n]
 
 
# === TREE RECURSION: Handle None ===
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def max_path_sum(root: TreeNode) -> int:
    """Maximum path sum in binary tree."""
    result = [float('-inf')]  # Track global maximum
    
    def max_gain(node: TreeNode) -> int:
        # BASE CASE: empty node contributes nothing
        if node is None:
            return 0
        
        # Recursive: max gain from left and right subtrees
        left_gain = max(max_gain(node.left), 0)  # Ignore negative paths
        right_gain = max(max_gain(node.right), 0)
        
        # Update global max: path through current node
        result[0] = max(result[0], node.val + left_gain + right_gain)
        
        # Return max gain if we continue upward (can only use one branch)
        return node.val + max(left_gain, right_gain)
    
    max_gain(root)
    return result[0]

Debugging Base Case Issues

When you suspect a base case issue, here's a systematic debugging approach.

Base Case Debugging Process

•Test the smallest inputs: Call your function with input sizes 0, 1, and 2. Are the results correct?
•Print your base case values: Add print(dp[0]), print(dp[1]), etc. to see actual initialized values.
•Manually trace dp[2]: Compute dp[2] using your recurrence and base case values. Does it match expected?
•Check the definition alignment: Does your base case value match what your dp definition says for that input?
•Look for missing base cases: Are there inputs where your recurrence doesn't apply but you try to apply it?
•Verify boundary access: Do your recurrence calls ever access dp[-1] or beyond array bounds?

debugging_base_cases.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
def debug_dp_with_base_case_check(func, *args):
    """
    Wrapper to debug DP functions by printing state.
    """
    import functools
    
    # Store all computed values
    computed = {}
    
    @functools.wraps(func)
    def wrapper(*inner_args):
        result = func(*inner_args)
        computed[inner_args] = result
        return result
    
    # Run the function
    final_result = wrapper(*args)
    
    # Print analysis
    print("=== Base Case Analysis ===")
    print(f"All computed states: {len(computed)}")
    
    # Find minimal keys (potential base cases)
    sorted_keys = sorted(computed.keys(), key=lambda x: sum(x) if isinstance(x, tuple) else x)
    print(f"Smallest states (likely base cases):")
    for key in sorted_keys[:5]:
        print(f"  {key} -> {computed[key]}")
    
    return final_result
 
 
# Example debugging session
 
def coin_change_debug(coins: list, amount: int) -> int:
    """Version with debugging output."""
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    
    print(f"Initial state: dp[0:5] = {dp[:min(5, amount+1)]}")
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != INF:
                old_val = dp[i]
                dp[i] = min(dp[i], dp[i - coin] + 1)
                if old_val != dp[i]:
                    print(f"  dp[{i}] updated: {old_val} -> {dp[i]} (used coin {coin})")
    
    print(f"Final state: dp = {dp}")
    return dp[amount] if dp[amount] != INF else -1
 
 
# Test with debugging
print("
=== Debug Run ===")
result = coin_change_debug([1, 2, 5], 6)
print(f"Result: {result}")
 
# Expected output shows:
# - dp[0] = 0 (base case)
# - Each transition building on base case
# - Final answer traceable back to dp[0]

The 'Work Backward' Technique

If your answer is wrong, work backward: If dp[n] should be X, what should dp[n-1] be? What should dp[n-2] be? Trace back until you reach base cases. If the answer should be 5 and you're getting 6, somewhere in that chain, a value is off by 1—often the base case.

Data Structures & AlgorithmsDebugging Algorithmic Code

Debugging Algorithmic Code

LevelIntermediate

Duration75 mins

TopicDebugging Algorithmic Code

4 / 5

Incorrect Base Cases

The Foundation That Must Not Crack

In recursion and dynamic programming, the base case is everything. It's the foundation upon which all other computations build. If your recurrence relation is correct but your base case is wrong, your algorithm will systematically produce incorrect answers—sometimes subtly wrong, sometimes completely wrong. The Insidious Nature of Base Case Bugs Base case errors are particularly dangerous because: The recursive logic often looks correct The algorithm may work for "normal" inputs Failure only manifests for specific edge cases (empty, single-element, etc.) The error compounds: a wrong base case corrupts all dependent computations This makes base case bugs feel like logic errors in your recurrence, leading you to debug the wrong part of your code.

What You Will Master

This page provides a systematic approach to base case design. You'll learn to identify all necessary base cases, derive their correct values, verify consistency with your recurrence, and test comprehensively. By the end, you'll treat base case design as a critical first step, not an afterthought.

Understanding Base Cases

A base case is a condition where a recursive function returns a direct answer without making further recursive calls. Base cases serve two essential purposes: Termination: Without base cases, recursion would continue infinitely Foundation: Base cases provide the seed values that all recursive computations build upon Anatomy of Recursive Solutions Every recursive solution has two parts: function solve(problem): if is_base_case(problem): # Base case check return base_case_answer # Direct answer, no recursion else: smaller_problems = decompose(problem) sub_answers = [solve(p) for p in smaller_problems] # Recursive calls return combine(sub_answers) # Combine results The correctness of solve depends critically on: Correctly identifying ALL base cases (not just some) Returning the RIGHT value for each base case Ensuring the recurrence relation reaches base cases for all valid inputs

Properties of Correct Base Cases

•Exhaustive: All input patterns that cannot be decomposed further are covered.
•Minimal: Base cases represent the smallest meaningful problem instances.
•Correct: Each base case returns the mathematically correct answer for that specific input.
•Reachable: The recursive decomposition eventually reaches base cases for all valid inputs.
•Consistent: Base case definitions align with how the recurrence relation uses sub-results.

The Consistency Requirement

A base case isn't just 'an answer for small inputs'—it must be the CORRECT answer that makes your recurrence relation work. If your recurrence computes dp[i] = dp[i-1] + dp[i-2], then dp[0] and dp[1] must be defined such that dp[2] computed from them is correct.

Common Base Case Error Patterns

Let's examine the most frequent base case mistakes and how they manifest.

Taxonomy of Base Case Errors
Error Type	Description	Typical Symptom
Missing Base Case	A condition that should return directly but doesn't	Stack overflow or infinite recursion
Incomplete Base Cases	Some edge cases covered, others not	Correct for some inputs, wrong for edges
Wrong Base Value	Base case exists but returns wrong value	Systematic offset in all results
Inconsistent Base	Base case value doesn't match recurrence semantics	Wrong answer propagates through recursion
Off-by-One Base	Base case index is shifted (dp[0] vs dp[1])	All results shifted by one position
Premature Base Case	Returns base value too early, missing work	Missing computation for smallest cases

base_case_errors.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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
# === ERROR 1: Missing Base Case ===
 
# BUGGY: No base case for empty string
def count_substrings_buggy(s: str) -> int:
    """Count all possible substrings."""
    if len(s) == 1:  # Only one base case
        return 1
    
    # BUG: What if s is empty? This will call count_substrings("") which
    # doesn't match len(s) == 1, leads to index errors or infinite recursion
    return len(s) + count_substrings_buggy(s[1:])
 
# CORRECT: Handle all minimal cases
def count_substrings_correct(s: str) -> int:
    if len(s) == 0:  # MISSING BASE CASE added
        return 0
    if len(s) == 1:
        return 1
    return len(s) + count_substrings_correct(s[1:])
 
 
# === ERROR 2: Wrong Base Value ===
 
# BUGGY: Wrong base case for Fibonacci
def fibonacci_buggy(n: int) -> int:
    if n <= 0:
        return 0
    if n == 1:
        return 0  # BUG: fib(1) should be 1, not 0!
    return fibonacci_buggy(n - 1) + fibonacci_buggy(n - 2)
 
# Test: fib(2) = fib(1) + fib(0) = 0 + 0 = 0 (should be 1!)
# All Fibonacci numbers will be wrong.
 
# CORRECT: Proper Fibonacci base cases
def fibonacci_correct(n: int) -> int:
    if n <= 0:
        return 0  # fib(0) = 0
    if n == 1:
        return 1  # fib(1) = 1
    return fibonacci_correct(n - 1) + fibonacci_correct(n - 2)
 
 
# === ERROR 3: Inconsistent Base with Recurrence ===
 
# Recurrence: dp[i] represents min cost to reach step i from step 0
# dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
 
# BUGGY: Base case doesn't match recurrence semantics
def min_cost_climbing_buggy(cost: list) -> int:
    n = len(cost)
    dp = [0] * (n + 1)
    
    dp[0] = cost[0]  # BUG: dp[0] should be 0 (no cost to be at step 0)
    dp[1] = cost[1]  # BUG: dp[1] should consider coming from step 0
    
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    
    return dp[n]  # Wrong answer due to wrong base cases
 
# CORRECT: Base cases match recurrence semantics
def min_cost_climbing_correct(cost: list) -> int:
    n = len(cost)
    dp = [0] * (n + 1)
    
    # dp[i] = minimum cost to reach step i
    # You start on step 0 or step 1 with no prior cost
    dp[0] = 0  # Cost to be at step 0 before any move
    dp[1] = 0  # Cost to be at step 1 before any move (can start here)
    
    for i in range(2, n + 1):
        # To reach step i: come from i-1 (pay cost[i-1]) or i-2 (pay cost[i-2])
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    
    return dp[n]
 
 
# === ERROR 4: Off-by-One in Base Case Index ===
 
# Problem: Compute number of ways to climb n stairs (1 or 2 steps at a time)
 
# BUGGY: Base case indexing mismatch
def climb_stairs_buggy(n: int) -> int:
    if n <= 0:
        return 0  # BUG: What does this mean?
    
    dp = [0] * (n + 1)
    dp[0] = 0  # BUG: There IS one way to stay at step 0 (do nothing)
    dp[1] = 1
    # dp[2] = dp[1] + dp[0] = 1 + 0 = 1 (should be 2!)
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]  # Wrong!
 
# CORRECT: Think about what dp[i] means
def climb_stairs_correct(n: int) -> int:
    if n <= 0:
        return 0 if n < 0 else 1  # 1 way to climb 0 stairs: do nothing
    
    dp = [0] * (n + 1)
    
    # dp[i] = number of ways to reach step i
    dp[0] = 1  # One way to be at step 0: start there
    dp[1] = 1  # One way to reach step 1: take one step
    # dp[2] = dp[1] + dp[0] = 1 + 1 = 2 (1+1 or 2) ✓
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

Systematic Base Case Design

Instead of guessing base cases and hoping they're right, follow a systematic design process. The Base Case Design Algorithm Define what your function/dp computes precisely — Write down in plain English what the return value represents. Identify the smallest valid inputs — What's the minimal problem size? (Empty, single element, etc.) Compute answers for smallest inputs by definition — Using your definition from step 1, what IS the answer for each minimal case? Verify consistency with recurrence — Does your recurrence correctly compute dp[2] from dp[0] and dp[1]? Trace through manually. Check all edge conditions — Are there special cases the recurrence doesn't handle naturally?

systematic_design.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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
# === EXAMPLE: Designing Base Cases for Coin Change ===
 
# PROBLEM: Find minimum number of coins to make amount.
# If impossible, return -1.
 
# STEP 1: Define precisely what we compute
# dp[amount] = minimum number of coins needed to make exactly 'amount'
# If impossible, dp[amount] = infinity (or some sentinel)
 
# STEP 2: Identify smallest valid inputs
# Smallest amount: 0
# What about negative amounts? Invalid input, handle separately.
 
# STEP 3: Compute by definition
# dp[0] = 0 (zero coins needed to make amount 0)
# This is THE key insight many miss!
 
# STEP 4: Define recurrence
# dp[i] = min(dp[i - coin] + 1) for all coins where i >= coin
# Verify: dp[5] with coins=[1,2,5]
#   = min(dp[4] + 1, dp[3] + 1, dp[0] + 1)
#   = min(dp[4] + 1, dp[3] + 1, 0 + 1)
#   = uses dp[0] = 0 correctly ✓
 
def coin_change_correct(coins: list, amount: int) -> int:
    """Minimum coins to make amount."""
    INF = float('inf')
    
    # dp[i] = minimum coins to make exactly i
    dp = [INF] * (amount + 1)
    
    # BASE CASE: 0 coins needed for amount 0
    dp[0] = 0
    
    # Fill DP table
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != INF:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != INF else -1
 
 
# === EXAMPLE: Designing Base Cases for Longest Common Subsequence ===
 
# PROBLEM: Find length of longest common subsequence of two strings.
 
# STEP 1: Define precisely
# dp[i][j] = length of LCS of text1[0:i] and text2[0:j]
# Note: 0:i means first i characters (indices 0 to i-1)
 
# STEP 2: Smallest valid inputs
# i = 0: text1[0:0] is empty string
# j = 0: text2[0:0] is empty string
 
# STEP 3: Compute by definition
# dp[0][j] = LCS of "" and text2[0:j] = 0 (nothing in common with empty)
# dp[i][0] = LCS of text1[0:i] and "" = 0 (nothing in common with empty)
 
# STEP 4: Define recurrence (for i, j > 0)
# If text1[i-1] == text2[j-1]:  (last chars match)
#     dp[i][j] = dp[i-1][j-1] + 1
# Else:
#     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 
def lcs_correct(text1: str, text2: str) -> int:
    """Length of longest common subsequence."""
    m, n = len(text1), len(text2)
    
    # dp[i][j] = LCS length of text1[0:i] and text2[0:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # BASE CASES: First row and first column are all 0
    # Already initialized by [[0] * (n+1) for ...]
    # dp[0][j] = 0 for all j (empty text1)
    # dp[i][0] = 0 for all i (empty text2)
    
    # Fill table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]
 
 
# === EXAMPLE: Designing Base Cases for Binary Search Tree Count ===
 
# PROBLEM: Count number of structurally unique BSTs with n nodes (values 1 to n)
# This is the nth Catalan number.
 
# STEP 1: Define precisely
# dp[n] = number of unique BSTs with n nodes
 
# STEP 2: Smallest valid inputs
# n = 0: No nodes
# n = 1: Single node
 
# STEP 3: Compute by definition
# dp[0] = 1 (ONE empty tree - this is the tricky one!)
#         The empty tree is a valid BST structure.
#         This is necessary for the recurrence to work.
# dp[1] = 1 (one tree with just the root)
 
# STEP 4: Recurrence
# For n nodes with root value k (1 <= k <= n):
#   Left subtree: k-1 nodes (values 1 to k-1)
#   Right subtree: n-k nodes (values k+1 to n)
#   dp[n] = sum(dp[k-1] * dp[n-k]) for k = 1 to n
 
# Verify: dp[2] = dp[0]*dp[1] + dp[1]*dp[0] = 1*1 + 1*1 = 2 ✓
# (Either root is 1 with right child 2, or root is 2 with left child 1)
 
def num_trees_correct(n: int) -> int:
    """Count unique BSTs with n nodes."""
    dp = [0] * (n + 1)
    
    # BASE CASES
    dp[0] = 1  # Empty tree (crucial for recurrence!)
    dp[1] = 1  # Single node tree
    
    for nodes in range(2, n + 1):
        for root in range(1, nodes + 1):
            left_subtrees = dp[root - 1]      # nodes in left subtree
            right_subtrees = dp[nodes - root]  # nodes in right subtree
            dp[nodes] += left_subtrees * right_subtrees
    
    return dp[n]

The dp[0] = 1 Pattern

Many counting problems require dp[0] = 1 (not 0) because 'there is one way to do nothing' or 'the empty set is a valid selection'. This is counterintuitive but mathematically correct. If your recurrence involves products or counts of combinations, check if dp[0] = 1 is the right base case.

Base Cases Across Algorithmic Paradigms

Different algorithmic paradigms have characteristic base case patterns. Understanding these patterns accelerates correct design.

Divide and Conquer algorithms split problems into smaller subproblems, solve them recursively, and combine results. Base cases are typically: Size 0 or 1: Problems too small to divide further Direct computation: When the problem is trivially solvable

divide_conquer_base.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
# === MERGE SORT ===
def merge_sort(arr: list) -> list:
    """Sort array using divide and conquer."""
    # BASE CASE: 0 or 1 elements are already sorted
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
 
# === BINARY SEARCH (Recursive) ===
def binary_search_recursive(arr: list, target: int, left: int, right: int) -> int:
    """Find target in sorted array."""
    # BASE CASE 1: Empty search space
    if left > right:
        return -1  # Not found
    
    mid = left + (right - left) // 2
    
    # BASE CASE 2: Found the target
    if arr[mid] == target:
        return mid
    
    # Recursive cases
    if arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)
 
 
# === MAXIMUM SUBARRAY (Divide and Conquer) ===
def max_subarray_dc(arr: list, left: int, right: int) -> int:
    """Find maximum sum subarray using divide and conquer."""
    # BASE CASE: Single element
    if left == right:
        return arr[left]
    
    mid = (left + right) // 2
    
    # Maximum in left half, right half, or crossing the middle
    left_max = max_subarray_dc(arr, left, mid)
    right_max = max_subarray_dc(arr, mid + 1, right)
    cross_max = max_crossing_sum(arr, left, mid, right)
    
    return max(left_max, right_max, cross_max)

Verifying Base Case Correctness

How do you know your base cases are correct? Here are systematic verification techniques.

Base Case Verification Checklist

•Manual Computation Test: Compute dp[2] or the smallest non-base case by hand using your base cases. Does it match the expected answer?
•Definition Consistency: Re-read your dp definition. Does each base case value match what the definition says for that input?
•Edge Input Tests: Test with empty input, single element, two elements, all zeros, all identical values.
•Recurrence Trace: Trace backward from a known answer. If dp[5] should be X, does dp[5] = f(dp[4], dp[3], ...) actually compute X?
•Mathematical Identity: For problems with known formulas, verify: Fibonacci should give 0,1,1,2,3,5,8... Catalan numbers should give 1,1,2,5,14,42...

base_case_verification.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
# === VERIFICATION BY MANUAL TRACE ===
 
def verify_climb_stairs():
    """
    Verify climb stairs base cases by manual computation.
    
    dp[n] = number of ways to climb n stairs (1 or 2 steps at a time)
    Recurrence: dp[n] = dp[n-1] + dp[n-2]
    """
    
    # Our base cases:
    dp_0 = 1  # 1 way to climb 0 stairs: do nothing
    dp_1 = 1  # 1 way to climb 1 stair: take one step
    
    # Manual verification of non-base cases:
    # dp[2] = dp[1] + dp[0] = 1 + 1 = 2
    # Expected: 2 ways (1+1 or 2)
    assert dp_1 + dp_0 == 2, "dp[2] is wrong!"
    
    # dp[3] = dp[2] + dp[1] = 2 + 1 = 3
    # Expected: 3 ways (1+1+1, 1+2, 2+1)
    dp_2 = 2
    assert dp_2 + dp_1 == 3, "dp[3] is wrong!"
    
    # dp[4] = dp[3] + dp[2] = 3 + 2 = 5
    # Expected: 5 ways (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)
    dp_3 = 3
    assert dp_3 + dp_2 == 5, "dp[4] is wrong!"
    
    print("Base cases verified!")
 
 
# === VERIFICATION BY KNOWN SEQUENCES ===
 
def verify_fibonacci_base():
    """Verify Fibonacci base cases against known sequence."""
    known_fib = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
    
    def fib(n):
        if n <= 0:
            return 0
        if n == 1:
            return 1
        return fib(n - 1) + fib(n - 2)
    
    for i, expected in enumerate(known_fib):
        computed = fib(i)
        assert computed == expected, f"fib({i}) = {computed}, expected {expected}"
    
    print("Fibonacci base cases verified!")
 
 
# === VERIFICATION BY EDGE CASES ===
 
def verify_coin_change_base():
    """Verify coin change handles edge cases correctly."""
    
    def coin_change(coins, amount):
        INF = float('inf')
        dp = [INF] * (amount + 1)
        dp[0] = 0  # Base case
        
        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i and dp[i - coin] != INF:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return dp[amount] if dp[amount] != INF else -1
    
    # Edge case 1: amount = 0
    assert coin_change([1, 2, 5], 0) == 0, "0 coins for amount 0"
    
    # Edge case 2: single coin equals amount
    assert coin_change([5], 5) == 1, "one coin for exact amount"
    
    # Edge case 3: impossible amount
    assert coin_change([2], 3) == -1, "impossible with only 2s"
    
    # Edge case 4: empty coins (any positive amount impossible)
    assert coin_change([], 5) == -1, "impossible with no coins"
    assert coin_change([], 0) == 0, "0 coins for amount 0, even with no coins"
    
    print("Coin change base cases verified!")
 
 
# Run verifications
verify_climb_stairs()
verify_fibonacci_base()
verify_coin_change_base()

Base Case Patterns by Problem Type

Certain problem types have characteristic base case patterns. Recognizing these accelerates correct design.

Base Case Patterns by Problem Category
Problem Category	Typical Base Case	Common Mistake
Counting Ways	dp[0] = 1 (one way to do nothing)	dp[0] = 0
Finding Minimum	dp[0] = 0 or dp[target] = 0	dp[0] = 1 or forgetting infinity for impossible
Finding Maximum	dp[0] = 0 or -∞ for 'must include'	Forgetting negative infinity for 'must include'
String Matching (2D)	dp[i][0] and dp[0][j] for empty strings	Only initializing dp[0][0]
Tree Recursion	if node is None: return identity	Forgetting null check, causing NoneType error
Graph DFS/BFS	visited[start] = True before recursion	Marking visited after processing, causing cycles
Binary Search	left > right means empty range	left >= right (loses the single-element case)

pattern_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
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
95
96
97
98
99
100
101
102
103
104
105
# === COUNTING WAYS: dp[0] = 1 ===
 
def unique_paths(m: int, n: int) -> int:
    """Count paths in m×n grid from top-left to bottom-right."""
    dp = [[1] * n for _ in range(m)]  # First row and column: 1 way each
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]
 
 
def count_subsets_with_sum(nums: list, target: int) -> int:
    """Count subsets that sum to target."""
    dp = [0] * (target + 1)
    dp[0] = 1  # ONE way to make sum 0: empty subset
    
    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] += dp[s - num]
    
    return dp[target]
 
 
# === FINDING MINIMUM: dp[0] = 0, others = infinity ===
 
def min_jumps_to_end(nums: list) -> int:
    """Minimum jumps to reach end of array."""
    n = len(nums)
    INF = float('inf')
    
    dp = [INF] * n
    dp[0] = 0  # 0 jumps to reach position 0
    
    for i in range(n):
        if dp[i] == INF:
            continue
        for j in range(1, nums[i] + 1):
            if i + j < n:
                dp[i + j] = min(dp[i + j], dp[i] + 1)
    
    return dp[n-1] if dp[n-1] != INF else -1
 
 
# === STRING DP: Initialize entire row/column ===
 
def is_interleaving(s1: str, s2: str, s3: str) -> bool:
    """Check if s3 is interleaving of s1 and s2."""
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    
    # dp[i][j] = True if s3[0:i+j] is interleaving of s1[0:i] and s2[0:j]
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # BASE CASE: dp[0][0] = True (empty matches empty)
    dp[0][0] = True
    
    # BASE CASE: First column (using only s1)
    for i in range(1, m + 1):
        dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
    
    # BASE CASE: First row (using only s2)
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
    
    # Fill rest
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or \
                       (dp[i][j-1] and s2[j-1] == s3[i+j-1])
    
    return dp[m][n]
 
 
# === TREE RECURSION: Handle None ===
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def max_path_sum(root: TreeNode) -> int:
    """Maximum path sum in binary tree."""
    result = [float('-inf')]  # Track global maximum
    
    def max_gain(node: TreeNode) -> int:
        # BASE CASE: empty node contributes nothing
        if node is None:
            return 0
        
        # Recursive: max gain from left and right subtrees
        left_gain = max(max_gain(node.left), 0)  # Ignore negative paths
        right_gain = max(max_gain(node.right), 0)
        
        # Update global max: path through current node
        result[0] = max(result[0], node.val + left_gain + right_gain)
        
        # Return max gain if we continue upward (can only use one branch)
        return node.val + max(left_gain, right_gain)
    
    max_gain(root)
    return result[0]

Debugging Base Case Issues

When you suspect a base case issue, here's a systematic debugging approach.

Base Case Debugging Process

•Test the smallest inputs: Call your function with input sizes 0, 1, and 2. Are the results correct?
•Print your base case values: Add print(dp[0]), print(dp[1]), etc. to see actual initialized values.
•Manually trace dp[2]: Compute dp[2] using your recurrence and base case values. Does it match expected?
•Check the definition alignment: Does your base case value match what your dp definition says for that input?
•Look for missing base cases: Are there inputs where your recurrence doesn't apply but you try to apply it?
•Verify boundary access: Do your recurrence calls ever access dp[-1] or beyond array bounds?

debugging_base_cases.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
def debug_dp_with_base_case_check(func, *args):
    """
    Wrapper to debug DP functions by printing state.
    """
    import functools
    
    # Store all computed values
    computed = {}
    
    @functools.wraps(func)
    def wrapper(*inner_args):
        result = func(*inner_args)
        computed[inner_args] = result
        return result
    
    # Run the function
    final_result = wrapper(*args)
    
    # Print analysis
    print("=== Base Case Analysis ===")
    print(f"All computed states: {len(computed)}")
    
    # Find minimal keys (potential base cases)
    sorted_keys = sorted(computed.keys(), key=lambda x: sum(x) if isinstance(x, tuple) else x)
    print(f"Smallest states (likely base cases):")
    for key in sorted_keys[:5]:
        print(f"  {key} -> {computed[key]}")
    
    return final_result
 
 
# Example debugging session
 
def coin_change_debug(coins: list, amount: int) -> int:
    """Version with debugging output."""
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    
    print(f"Initial state: dp[0:5] = {dp[:min(5, amount+1)]}")
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != INF:
                old_val = dp[i]
                dp[i] = min(dp[i], dp[i - coin] + 1)
                if old_val != dp[i]:
                    print(f"  dp[{i}] updated: {old_val} -> {dp[i]} (used coin {coin})")
    
    print(f"Final state: dp = {dp}")
    return dp[amount] if dp[amount] != INF else -1
 
 
# Test with debugging
print("
=== Debug Run ===")
result = coin_change_debug([1, 2, 5], 6)
print(f"Result: {result}")
 
# Expected output shows:
# - dp[0] = 0 (base case)
# - Each transition building on base case
# - Final answer traceable back to dp[0]

The 'Work Backward' Technique

If your answer is wrong, work backward: If dp[n] should be X, what should dp[n-1] be? What should dp[n-2] be? Trace back until you reach base cases. If the answer should be 5 and you're getting 6, somewhere in that chain, a value is off by 1—often the base case.

Incorrect Base Cases

The Foundation That Must Not Crack

Understanding Base Cases

Common Base Case Error Patterns

Systematic Base Case Design

Base Cases Across Algorithmic Paradigms

Verifying Base Case Correctness

Base Case Patterns by Problem Type

Debugging Base Case Issues

There’s more to understand.

Incorrect Base Cases

The Foundation That Must Not Crack

Understanding Base Cases

Common Base Case Error Patterns

Systematic Base Case Design

Base Cases Across Algorithmic Paradigms

Verifying Base Case Correctness

Base Case Patterns by Problem Type

Debugging Base Case Issues

There’s more to understand.