Multiple Base Cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# ❌ BROKEN: Only one base case for Fibonacci
def fib_broken(n: int) -> int:
    """This implementation is missing a base case."""
    if n == 0:
        return 0
    # Missing: if n == 1: return 1
    return fib_broken(n - 1) + fib_broken(n - 2)
 
# What happens with fib_broken(2)?
# fib_broken(2) = fib_broken(1) + fib_broken(0)
# fib_broken(0) → 0 ✓
# fib_broken(1) = fib_broken(0) + fib_broken(-1)  ← PROBLEM!
# fib_broken(-1) = fib_broken(-2) + fib_broken(-3)
# ... infinite recursion into negative numbers → Stack Overflow
 
# ✅ CORRECT: Two base cases for Fibonacci
def fib_correct(n: int) -> int:
    """Fibonacci with both necessary base cases."""
    if n == 0:
        return 0  # Base case 1
    if n == 1:
        return 1  # Base case 2
    return fib_correct(n - 1) + fib_correct(n - 2)
 
# Now fib_correct(2) = fib_correct(1) + fib_correct(0)
#                    = 1 + 0 = 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

def fibonacci(n: int) -> int:
    """
    Compute the nth Fibonacci number.
    
    Mathematical definition:
        F(0) = 0
        F(1) = 1
        F(n) = F(n-1) + F(n-2) for n ≥ 2
    
    Why two base cases?
    - Recursion decrements by 1 AND by 2
    - From n=2: we reach both n=1 and n=0
    - Both are "smallest" inputs that need direct answers
    """
    # BASE CASE 1: F(0) = 0
    if n == 0:
        return 0
    
    # BASE CASE 2: F(1) = 1
    if n == 1:
        return 1
    
    # RECURSIVE CASE: F(n) = F(n-1) + F(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2)
 
# Execution trace for fibonacci(5):
#
# fibonacci(5)
#   ├── fibonacci(4)
#   │     ├── fibonacci(3)
#   │     │     ├── fibonacci(2)
#   │     │     │     ├── fibonacci(1) → 1  [BASE CASE 2]
#   │     │     │     └── fibonacci(0) → 0  [BASE CASE 1]
#   │     │     └── fibonacci(1) → 1  [BASE CASE 2]
#   │     └── fibonacci(2)
#   │           ├── fibonacci(1) → 1  [BASE CASE 2]
#   │           └── fibonacci(0) → 0  [BASE CASE 1]
#   └── fibonacci(3)
#         ├── fibonacci(2)
#         │     ├── fibonacci(1) → 1  [BASE CASE 2]
#         │     └── fibonacci(0) → 0  [BASE CASE 1]
#         └── fibonacci(1) → 1  [BASE CASE 2]
#
# Both base cases are hit multiple times in this tree!

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

from typing import List
 
def binary_search(arr: List[int], target: int, low: int, high: int) -> int:
    """
    Search for target in sorted array arr[low..high].
    Returns index if found, -1 otherwise.
    
    TWO DISTINCT BASE CASES:
    1. Failure: Search space is empty (low > high)
    2. Success: Target found at mid
    """
    # BASE CASE 1: FAILURE
    # The search space is empty - nothing left to search
    if low > high:
        return -1  # Convention: -1 means "not found"
    
    mid = (low + high) // 2
    
    # BASE CASE 2: SUCCESS
    # We found the target
    if arr[mid] == target:
        return mid  # Return the index where found
    
    # RECURSIVE CASE: Search appropriate half
    if target < arr[mid]:
        return binary_search(arr, target, low, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, high)
 
# Example 1: Element exists
# binary_search([1, 3, 5, 7, 9], 5, 0, 4)
# mid = 2, arr[2] = 5 == target → return 2 (SUCCESS BASE CASE)
 
# Example 2: Element doesn't exist  
# binary_search([1, 3, 5, 7, 9], 4, 0, 4)
# mid = 2, arr[2] = 5 > 4 → search left [0, 1]
# mid = 0, arr[0] = 1 < 4 → search right [1, 1]
# mid = 1, arr[1] = 3 < 4 → search right [2, 1]
# low(2) > high(1) → return -1 (FAILURE BASE CASE)

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

class TreeNode:
    def __init__(self, val: int):
        self.val = val
        self.left: 'TreeNode | None' = None
        self.right: 'TreeNode | None' = None
 
# PATTERN 1: Single base case (null node only)
def count_nodes(node: TreeNode | None) -> int:
    """Count total nodes in tree."""
    # BASE CASE: Null node contributes 0
    if node is None:
        return 0
    
    # RECURSIVE CASE: This node + left subtree + right subtree
    return 1 + count_nodes(node.left) + count_nodes(node.right)
 
# PATTERN 2: Multiple structural base cases
def is_leaf(node: TreeNode | None) -> bool:
    """Check if node is a leaf (no children)."""
    if node is None:
        return False  # Null isn't a leaf
    return node.left is None and node.right is None
 
def sum_of_leaves(node: TreeNode | None) -> int:
    """Sum values of all leaf nodes."""
    # BASE CASE 1: Null node
    if node is None:
        return 0
    
    # BASE CASE 2: Leaf node - use its value directly
    if is_leaf(node):
        return node.val
    
    # RECURSIVE CASE: Sum leaves in subtrees
    return sum_of_leaves(node.left) + sum_of_leaves(node.right)
 
# PATTERN 3: Early termination base case
def contains_value(node: TreeNode | None, target: int) -> bool:
    """Check if tree contains target value."""
    # BASE CASE 1: Empty tree can't contain anything
    if node is None:
        return False
    
    # BASE CASE 2: Found! (early termination)
    if node.val == target:
        return True
    
    # RECURSIVE CASE: Check subtrees (short-circuit with OR)
    return contains_value(node.left, target) or contains_value(node.right, target)

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

def are_identical(tree1: TreeNode | None, tree2: TreeNode | None) -> bool:
    """
    Check if two binary trees are structurally identical with same values.
    
    MULTIPLE BASE CASES for different structural configurations:
    1. Both null: Identical (empty trees are equal)
    2. One null, one not: Not identical
    3. Both non-null with same value: Check subtrees (recursive case)
    """
    # BASE CASE 1: Both trees are empty
    if tree1 is None and tree2 is None:
        return True
    
    # BASE CASE 2: Exactly one tree is empty (asymmetric)
    if tree1 is None or tree2 is None:
        return False
    
    # BASE CASE 3 (implicit): Values differ at current node
    if tree1.val != tree2.val:
        return False
    
    # RECURSIVE CASE: Both non-null with equal values
    # Must match in BOTH subtrees
    return (are_identical(tree1.left, tree2.left) and 
            are_identical(tree1.right, tree2.right))
 
def is_symmetric(root: TreeNode | None) -> bool:
    """Check if tree is a mirror of itself."""
    if root is None:
        return True
    return is_mirror(root.left, root.right)
 
def is_mirror(left: TreeNode | None, right: TreeNode | None) -> bool:
    """Check if two subtrees are mirrors of each other."""
    # BASE CASE 1: Both null - symmetric
    if left is None and right is None:
        return True
    
    # BASE CASE 2: One null, one not - asymmetric
    if left is None or right is None:
        return False
    
    # BASE CASE 3: Values differ - not mirror
    if left.val != right.val:
        return False
    
    # RECURSIVE CASE: Check crossed pairs
    return is_mirror(left.left, right.right) and is_mirror(left.right, right.left)

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

from typing import List, Optional
 
def find_target_index(
    arr: List[int], 
    target: int, 
    index: int = 0
) -> int:
    """
    Find index of target in unsorted array. Returns -1 if not found.
    
    BASE CASES (coordinated):
    1. index >= len(arr): Searched everything, not found → -1
    2. arr[index] == target: Found it → return index
    
    These are DISJOINT (can't both be true) and EXHAUSTIVE (cover all stops).
    ORDER: Check bounds FIRST, then check content (avoid index error).
    """
    # BASE CASE 1: Exhausted the array (check bounds FIRST)
    if index >= len(arr):
        return -1
    
    # BASE CASE 2: Found the target
    if arr[index] == target:
        return index
    
    # RECURSIVE CASE: Check next index
    return find_target_index(arr, target, index + 1)
 
 
def gcd(a: int, b: int) -> int:
    """
    Compute greatest common divisor using Euclidean algorithm.
    
    BASE CASE: When b is 0, the GCD is a.
    This single base case suffices because the algorithm always 
    reduces toward b=0.
    
    Note: We could add a second base case for a=0 (symmetry),
    but mathematically, gcd(0, b) = b, which the recursion handles.
    """
    # Single base case is sufficient here
    if b == 0:
        return a
    
    # Recursive case: GCD(a, b) = GCD(b, a % b)
    return gcd(b, a % b)
 
 
def min_max(arr: List[int], start: int = 0) -> tuple[int, int]:
    """
    Find minimum and maximum of array simultaneously.
    Returns (min, max) tuple.
    
    MULTIPLE BASE CASES:
    1. Single element: min = max = that element
    2. Two elements: compare and return ordered tuple
    
    Why two base cases? The recursive case compares results from
    two halves. We need at least 1 element to compute min/max,
    and handling size-2 directly avoids edge cases.
    """
    remaining = len(arr) - start
    
    # BASE CASE 1: Single element
    if remaining == 1:
        return (arr[start], arr[start])  # Both min and max
    
    # BASE CASE 2: Two elements (optional but cleaner)
    if remaining == 2:
        if arr[start] < arr[start + 1]:
            return (arr[start], arr[start + 1])
        else:
            return (arr[start + 1], arr[start])
    
    # RECURSIVE CASE: Divide and combine
    mid = start + remaining // 2
    left_min, left_max = min_max(arr, start, mid)  # Would need modified signature
    right_min, right_max = min_max(arr, mid)
    return (min(left_min, right_min), max(left_max, right_max))

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

from typing import List
 
def permutations(elements: List[int]) -> List[List[int]]:
    """
    Generate all permutations of the given list.
    
    BASE CASES:
    1. Empty list → [[]]  (one permutation: the empty arrangement)
    2. Single element → [[element]]  (one permutation: just that element)
    
    Actually, base case 1 is sufficient! Here's why:
    - permutations([x]) would recursively compute permutations([])
    - For each perm in [[]], prepend x → [[x]]
    - Works correctly!
    
    But many implementations use len <= 1 for clarity and slight efficiency.
    """
    # BASE CASE: Empty or single-element list
    if len(elements) <= 1:
        return [elements.copy()]  # One permutation (copy to avoid mutation)
    
    # RECURSIVE CASE:
    # For each element, make it first, permute the rest, prepend it
    result = []
    for i, elem in enumerate(elements):
        # Remove current element
        rest = elements[:i] + elements[i+1:]
        
        # Get all permutations of the remaining elements
        for perm in permutations(rest):
            # Add current element to the front
            result.append([elem] + perm)
    
    return result
 
 
# Let's trace permutations([1, 2, 3]):
#
# permutations([1, 2, 3])
#   i=0, elem=1:
#     rest = [2, 3]
#     permutations([2, 3])
#       i=0, elem=2: rest=[3], permutations([3]) → [[3]] → [[2, 3]]
#       i=1, elem=3: rest=[2], permutations([2]) → [[2]] → [[3, 2]]
#     → [[2,3], [3,2]]
#     prepend 1: [[1,2,3], [1,3,2]]
#   
#   i=1, elem=2:
#     rest = [1, 3]
#     permutations([1, 3]) → [[1,3], [3,1]]
#     prepend 2: [[2,1,3], [2,3,1]]
#   
#   i=2, elem=3:
#     rest = [1, 2]
#     permutations([1, 2]) → [[1,2], [2,1]]
#     prepend 3: [[3,1,2], [3,2,1]]
#
# Result: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] ✓
 
print(permutations([1, 2, 3]))

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

def longest_common_subsequence(s1: str, s2: str) -> int:
    """
    Find length of longest common subsequence between two strings.
    
    TWO-INPUT FUNCTION: Both strings shrink during recursion.
    
    BASE CASES:
    - Either string empty → LCS length is 0 (nothing to match)
    
    This is a "combined" base case covering:
    - s1 empty, s2 anything → 0
    - s2 empty, s1 anything → 0
    """
    # BASE CASE: Either string is empty
    if len(s1) == 0 or len(s2) == 0:
        return 0
    
    # RECURSIVE CASE:
    if s1[0] == s2[0]:
        # First characters match: include in LCS, continue with rest
        return 1 + longest_common_subsequence(s1[1:], s2[1:])
    else:
        # First characters don't match: try skipping from each
        skip_s1 = longest_common_subsequence(s1[1:], s2)
        skip_s2 = longest_common_subsequence(s1, s2[1:])
        return max(skip_s1, skip_s2)
 
 
def edit_distance(s1: str, s2: str) -> int:
    """
    Minimum operations (insert, delete, replace) to convert s1 to s2.
    
    BASE CASES:
    - s1 empty: Need len(s2) insertions
    - s2 empty: Need len(s1) deletions
    
    Note: These are DIFFERENT base case values, not just "0".
    """
    # BASE CASE 1: s1 exhausted - insert all remaining s2 chars
    if len(s1) == 0:
        return len(s2)
    
    # BASE CASE 2: s2 exhausted - delete all remaining s1 chars
    if len(s2) == 0:
        return len(s1)
    
    # RECURSIVE CASE:
    if s1[0] == s2[0]:
        # Characters match, no operation needed
        return edit_distance(s1[1:], s2[1:])
    else:
        # Try all three operations, take minimum
        insert = 1 + edit_distance(s1, s2[1:])     # Insert s2[0] into s1
        delete = 1 + edit_distance(s1[1:], s2)     # Delete s1[0]
        replace = 1 + edit_distance(s1[1:], s2[1:]) # Replace s1[0] with s2[0]
        return min(insert, delete, replace)
 
# edit_distance("cat", "car") = 1 (replace 't' with 'r')
# edit_distance("", "abc") = 3 (insert 3 chars)