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

# ❌ BROKEN: No base case at all
def infinite_factorial(n: int) -> int:
    """This function will never terminate."""
    return n * infinite_factorial(n - 1)
    # No base case! Recurses forever (or until stack overflow)
 
# Call infinite_factorial(5):
# → 5 * infinite_factorial(4)
# → 5 * (4 * infinite_factorial(3))
# → 5 * (4 * (3 * infinite_factorial(2)))
# → 5 * (4 * (3 * (2 * infinite_factorial(1))))
# → 5 * (4 * (3 * (2 * (1 * infinite_factorial(0)))))
# → 5 * (4 * (3 * (2 * (1 * (0 * infinite_factorial(-1))))))
# → ... eventually RecursionError: maximum recursion depth exceeded
 
 
# ✅ FIX: Add the base case first
def correct_factorial(n: int) -> int:
    """Always write the base case first!"""
    # BASE CASE - Write this BEFORE the recursive case
    if n <= 1:
        return 1
    
    # RECURSIVE CASE
    return n * correct_factorial(n - 1)
 
 
# PREVENTION STRATEGY: Write base case first
# Template:
def recursive_function(input):
    # 1. FIRST: Handle base case(s)
    if is_base_case(input):
        return base_result
    
    # 2. SECOND: Write recursive case
    return combine(input, recursive_function(smaller_input))

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

# ❌ BROKEN: Wrong base case value
def broken_factorial(n: int) -> int:
    """Returns 0 for everything because base case is wrong."""
    if n <= 1:
        return 0  # WRONG! 0! = 1 and 1! = 1, not 0
    return n * broken_factorial(n - 1)
 
# broken_factorial(5):
# = 5 * broken_factorial(4)
# = 5 * (4 * broken_factorial(3))
# = 5 * (4 * (3 * broken_factorial(2)))
# = 5 * (4 * (3 * (2 * broken_factorial(1))))
# = 5 * (4 * (3 * (2 * 0)))  ← Base case returns 0!
# = 5 * (4 * (3 * 0))
# = 5 * (4 * 0)
# = 5 * 0
# = 0  ← WRONG!
 
 
# ❌ BROKEN: Another common error - returning n instead of 1
def also_broken_factorial(n: int) -> int:
    if n <= 1:
        return n  # Returns 1 for n=1, but 0 for n=0!
    return n * also_broken_factorial(n - 1)
 
# also_broken_factorial(0) = 0  ← Should be 1!
 
 
# ✅ CORRECT: Math says 0! = 1! = 1
def correct_factorial(n: int) -> int:
    if n <= 1:
        return 1  # Both 0! and 1! equal 1
    return n * correct_factorial(n - 1)
 
 
# Another example: counting base case
# ❌ BROKEN: Wrong base for counting
def broken_count_nodes(node) -> int:
    """Counts nodes in a tree - but overcounts by 1."""
    if node is None:
        return 1  # WRONG! An empty tree has 0 nodes, not 1
    return 1 + broken_count_nodes(node.left) + broken_count_nodes(node.right)
 
# This returns (number_of_nodes + 2*number_of_none_pointers)
# Way too high!
 
# ✅ CORRECT
def correct_count_nodes(node) -> int:
    if node is None:
        return 0  # Empty tree/null node = 0 nodes
    return 1 + correct_count_nodes(node.left) + correct_count_nodes(node.right)

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

# ❌ BROKEN: Base case only catches n == 0
def broken_fibonacci(n: int) -> int:
    """Misses the n == 1 base case."""
    if n == 0:  # Only catches n == 0, not n == 1
        return 0
    return broken_fibonacci(n - 1) + broken_fibonacci(n - 2)
 
# broken_fibonacci(2):
# = broken_fibonacci(1) + broken_fibonacci(0)
# = (broken_fibonacci(0) + broken_fibonacci(-1)) + 0
# = (0 + broken_fibonacci(-2) + broken_fibonacci(-3)) + 0
# = ... infinite recursion into negatives!
 
 
# ✅ FIX: Catch ALL termination points
def correct_fibonacci(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:  # Must catch n == 1 too!
        return 1
    return correct_fibonacci(n - 1) + correct_fibonacci(n - 2)
 
 
# ❌ BROKEN: Using == instead of <= for robustness
def fragile_factorial(n: int) -> int:
    if n == 0:  # Only catches exactly 0
        return 1
    return n * fragile_factorial(n - 1)
 
# fragile_factorial(-1):
# = -1 * fragile_factorial(-2)
# = -1 * (-2 * fragile_factorial(-3))
# = ... never hits n == 0 exactly!
 
 
# ✅ FIX: Use inequality for robustness
def robust_factorial(n: int) -> int:
    if n <= 1:  # Catches 0, 1, and any negative (defensive)
        return 1
    return n * robust_factorial(n - 1)
 
 
# ❌ BROKEN: Binary search missing low == high case
def broken_binary_search(arr, target, low, high):
    if low > high:  # Only catches empty range
        return -1
    # Missing: what if low == high? We should still check arr[low]!
    # Actually this one works, but shows the thinking...
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif target < arr[mid]:
        return broken_binary_search(arr, target, low, mid - 1)
    else:
        return broken_binary_search(arr, target, mid + 1, high)
 
# The real issue is when mid calculation or range reduction is wrong

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

# ❌ BROKEN: Base case is too aggressive
def broken_sum(arr: list[int]) -> int:
    """Stops too early - misses one element."""
    if len(arr) <= 1:  # Stops at 1 element instead of 0
        return 0  # But returns 0 instead of arr[0]!
    return arr[0] + broken_sum(arr[1:])
 
# broken_sum([5]) returns 0, should return 5!
# The base case catches single-element arrays but returns wrong value
 
 
# ❌ ANOTHER BROKEN VERSION: 
def also_broken_sum(arr: list[int]) -> int:
    """Base case at len <= 1 with return arr[0] is risky."""
    if len(arr) <= 1:
        return arr[0] if arr else 0  # Fixed, but clunky
    return arr[0] + also_broken_sum(arr[1:])
 
# Works, but the if/else in base case is a code smell
# Better to have len(arr) == 0 as the base case
 
 
# ✅ CLEANER: Let the base case be truly minimal
def clean_sum(arr: list[int]) -> int:
    """Base case is empty array, recursive case handles rest."""
    if len(arr) == 0:  # Minimal base case
        return 0
    return arr[0] + clean_sum(arr[1:])  # Works for length 1, 2, 3, ...
 
 
# ❌ BROKEN: Merge sort stopping too early
def broken_merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 2:  # Tries to handle base case for 2 elements
        return sorted(arr)  # "Why recurse when I can sort directly?"
    # ... rest of merge sort
    
# This WORKS but defeats the purpose of learning merge sort.
# The proper base case is len(arr) <= 1.
 
 
# ❌ BROKEN: Binary search with premature termination
def broken_bs(arr, target, low, high):
    if high - low <= 1:  # Stops too early
        if arr[low] == target:
            return low
        return -1  # Might miss arr[high]!
    
    mid = (low + high) // 2
    if target <= arr[mid]:
        return broken_bs(arr, target, low, mid)
    else:
        return broken_bs(arr, target, mid + 1, high)
 
# broken_bs([1, 3, 5], 5, 0, 2):
# high - low = 2 > 1, so mid = 1, arr[1] = 3 < 5, search [2, 2]
# high - low = 0 <= 1, check arr[2] = 5 == target ✓
# Actually this one works, but shows risky pattern
 
# The danger: if your base case handles 2 elements, 
# make sure the logic for those 2 elements is correct!

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

from typing import List, Optional
 
# ❌ BROKEN: Doesn't handle empty array
def broken_find_max(arr: List[int]) -> int:
    """What if arr is empty?"""
    if len(arr) == 1:
        return arr[0]  # Base case for single element
    # But what about len(arr) == 0?? This crashes!
    return max(arr[0], broken_find_max(arr[1:]))
 
# broken_find_max([]) → eventually hits arr[0] on empty list → IndexError
 
 
# ✅ FIX: Handle empty array explicitly
def correct_find_max(arr: List[int]) -> Optional[int]:
    """Returns None for empty array, max for non-empty."""
    if len(arr) == 0:
        return None  # Edge case: no maximum exists
    if len(arr) == 1:
        return arr[0]
    return max(arr[0], correct_find_max(arr[1:]))
 
 
# ❌ BROKEN: Tree function without null check
class TreeNode:
    def __init__(self, val: int):
        self.val = val
        self.left: Optional['TreeNode'] = None
        self.right: Optional['TreeNode'] = None
 
def broken_tree_sum(node: TreeNode) -> int:
    """Assumes node is never None."""
    # No null check!
    return node.val + broken_tree_sum(node.left) + broken_tree_sum(node.right)
 
# Call on a leaf node:
# broken_tree_sum(leaf)
# = leaf.val + broken_tree_sum(None) + broken_tree_sum(None)
# = leaf.val + None.val + ... → AttributeError!
 
 
# ✅ FIX: Always check for null in tree recursion
def correct_tree_sum(node: Optional[TreeNode]) -> int:
    if node is None:  # Handle null nodes
        return 0
    return node.val + correct_tree_sum(node.left) + correct_tree_sum(node.right)
 
 
# ❌ BROKEN: String recursion without empty string check
def broken_reverse(s: str) -> str:
    """What if s is empty?"""
    # Bug: s[-1] and s[:-1] work on empty string in Python (return "")
    # But this pattern might fail in other contexts
    return s[-1] + broken_reverse(s[:-1])  # What's ""[-1]? IndexError!
 
# Actually in Python, ""[-1] raises IndexError
 
 
# ✅ FIX: Handle empty string explicitly
def correct_reverse(s: str) -> str:
    if len(s) == 0:  # Handle empty string
        return ""
    return s[-1] + correct_reverse(s[:-1])

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

from typing import List
 
# ❌ BROKEN: Wrong order of checks
def broken_find_min_max(arr: List[int]) -> tuple:
    """Find min and max simultaneously."""
    # Wrong order: checks content before checking existence
    if arr[0] == arr[-1]:  # Tries to access arr[0] first
        return (arr[0], arr[0])
    if len(arr) == 0:  # This check comes too late!
        return (float('inf'), float('-inf'))
    if len(arr) == 1:
        return (arr[0], arr[0])
    # ... rest of recursive logic
 
# broken_find_min_max([]) → IndexError on arr[0]
# The len(arr) == 0 check never runs because we crashed first!
 
 
# ✅ FIX: Check bounds before accessing elements
def correct_find_min_max(arr: List[int]) -> tuple:
    """Always check existence before content."""
    # Check length FIRST
    if len(arr) == 0:
        return (float('inf'), float('-inf'))  # Or raise error, or return None
    if len(arr) == 1:
        return (arr[0], arr[0])
    # Now safe to access elements
    if arr[0] == arr[-1]:  # Now this is safe
        return (arr[0], arr[0])
    # ... rest of logic
 
 
# ❌ BROKEN: Less specific check shadows more specific
def broken_classify(n: int) -> str:
    if n <= 10:
        return "small"  # This catches everything <= 10
    if n == 0:
        return "zero"  # Never reached! 0 <= 10, caught above
    if n < 0:
        return "negative"  # Never reached for negative!
    return "large"
 
# broken_classify(0) returns "small", not "zero"
# broken_classify(-5) returns "small", not "negative"
 
 
# ✅ FIX: Order from most specific to least specific
def correct_classify(n: int) -> str:
    if n == 0:
        return "zero"  # Most specific case first
    if n < 0:
        return "negative"  # More specific than "small"
    if n <= 10:
        return "small"  # Now correctly catches 1-10
    return "large"
 
 
# GENERAL PRINCIPLE: Ordering Rules
# 1. Null/empty checks → before any content access
# 2. Most specific conditions → before less specific
# 3. Error/boundary conditions → before normal processing
# 4. Rare edge cases → can be before or after common cases
 
def well_ordered_function(data):
    # 1. Null/empty check
    if data is None:
        return None
    if len(data) == 0:
        return default_for_empty
    
    # 2. Boundary checks
    if index_out_of_bounds:
        return boundary_result
    
    # 3. Specific cases
    if specific_special_case:
        return special_result
    
    # 4. General base case
    if general_base_condition:
        return base_result
    
    # 5. Recursive case
    return recursive_call(smaller_data)

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

from typing import List
 
# ❌ BROKEN: Base case returns None, recursive case expects int
def broken_sum(arr: List[int]) -> int:
    if len(arr) == 0:
        return None  # Wrong type! Should return 0
    return arr[0] + broken_sum(arr[1:])  # Can't add int + None!
 
# broken_sum([1, 2, 3]):
# = 1 + broken_sum([2, 3])
# = 1 + (2 + broken_sum([3]))
# = 1 + (2 + (3 + broken_sum([])))
# = 1 + (2 + (3 + None))  ← TypeError!
 
 
# ❌ BROKEN: Base case returns list, recursive case expects element
def broken_find_first_positive(arr: List[int]) -> int:
    if len(arr) == 0:
        return []  # Returns list, but function says int!
    if arr[0] > 0:
        return arr[0]  # Returns int
    return broken_find_first_positive(arr[1:])  # Returns... what?
 
# Type inconsistency: sometimes list, sometimes int
 
 
# ✅ FIX: Consistent types throughout
def correct_sum(arr: List[int]) -> int:
    if len(arr) == 0:
        return 0  # Returns int, consistent with recursive case
    return arr[0] + correct_sum(arr[1:])
 
def correct_find_first_positive(arr: List[int]) -> int | None:
    """Returns first positive int, or None if none found."""
    if len(arr) == 0:
        return None  # Type hint says this is OK
    if arr[0] > 0:
        return arr[0]
    return correct_find_first_positive(arr[1:])
 
 
# ❌ BROKEN: Returning single element vs list
def broken_flatten(nested: List) -> List:
    if not nested:
        return []  # OK
    if not isinstance(nested[0], list):
        return nested[0]  # WRONG! Returns single element, not list
    return broken_flatten(nested[0]) + broken_flatten(nested[1:])
 
# broken_flatten([1, [2, 3]]):
# = broken_flatten([1]) + broken_flatten([[2, 3]])
# = 1 + ...  ← Can't concatenate int to list!
 
 
# ✅ FIX: Always return same type
def correct_flatten(nested: List) -> List:
    if not nested:
        return []
    if not isinstance(nested[0], list):
        return [nested[0]] + correct_flatten(nested[1:])  # Wrap in list
    return correct_flatten(nested[0]) + correct_flatten(nested[1:])
 
 
# TYPE CHECKING TIP: In statically typed languages, the compiler
# would catch these. In Python, use type hints and mypy:
#
# def sum_array(arr: List[int]) -> int:  # Declares return type
#     if len(arr) == 0:
#         return None  # mypy error: expected int, got None

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

def validate_recursive_function(func, test_cases):
    """
    Test harness for validating recursive functions.
    Test cases should include base case inputs!
    """
    for inputs, expected in test_cases:
        try:
            result = func(*inputs) if isinstance(inputs, tuple) else func(inputs)
            if result == expected:
                print(f"✓ {func.__name__}({inputs}) = {result}")
            else:
                print(f"✗ {func.__name__}({inputs}) = {result}, expected {expected}")
        except Exception as e:
            print(f"✗ {func.__name__}({inputs}) raised {type(e).__name__}: {e}")
 
# Example: Testing factorial
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
 
# ALWAYS test base cases and near-base cases first:
factorial_tests = [
    # Base cases
    (0, 1),           # n = 0 (base case)
    (1, 1),           # n = 1 (base case)
    
    # One step from base
    (2, 2),           # Tests base case + one recursion
    
    # Normal cases
    (5, 120),
    (10, 3628800),
    
    # Edge cases
    (-1, 1),          # Negative - should probably not crash
]
 
validate_recursive_function(factorial, factorial_tests)
 
# Output:
# ✓ factorial(0) = 1
# ✓ factorial(1) = 1
# ✓ factorial(2) = 2
# ✓ factorial(5) = 120
# ✓ factorial(10) = 3628800
# ✓ factorial(-1) = 1