Common Mistakes: Missing or… — Base Cases & Recursive… | OneNoughtOne

0/97

Data Structures & AlgorithmsBase Cases & Recursive Cases

Base Cases & Recursive Cases

LevelBeginner

Duration60 mins

TopicBase Cases & Recursive Cases

4 / 4

Common Mistakes: Missing or Wrong Base Cases

Learning from Failure

Even experienced developers make mistakes with base cases. These errors are particularly insidious because they often produce code that works for simple inputs but fails catastrophically for edge cases or at scale. This page is a field guide to the most common base case mistakes: what they look like, why they happen, how to detect them, and most importantly, how to prevent them. By studying these patterns of failure, you'll develop the defensive reflexes to catch them before they cause problems.

What You Will Learn

By the end of this page, you will recognize the most common base case errors, understand why each mistake leads to incorrect behavior, develop strategies to prevent these mistakes proactively, know how to debug base case issues when they occur, and build a mental checklist for validating recursive functions.

Mistake #1: Missing Base Case Entirely

The Error: Writing a recursive function that never stops recursing—no base case exists at all. Why It Happens: Developer focuses on the recursive logic first and forgets to add the stopping condition The base case seems 'obvious' and gets mentally skipped Copy-paste from a non-recursive version without adding termination Symptoms: Immediate stack overflow on any input Freeze/hang as the program allocates stack frames endlessly

missing_base_case.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
# ❌ 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))

Prevention: Base Case First

Make it a habit to ALWAYS write your base case before writing any recursive logic. Start every recursive function with 'if (base condition): return base_value'. Only after that should you write the recursive call.

Mistake #2: Wrong Base Case Value

The Error: The function terminates correctly but returns the wrong value for base cases, causing all results to be incorrect. Why It Happens: Misunderstanding the mathematical definition (Is 0! equal to 0 or 1?) Off-by-one in counting logic Returning a value that doesn't compose correctly with the recursive case Symptoms: No stack overflow (function terminates) Results are consistently wrong by a constant factor All answers are off by 1, or all are doubled, or all are 0

wrong_base_value.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
# ❌ 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)

Common Wrong Base Values
Problem	Wrong Value	Correct Value	Why
Factorial n!	0	1	Empty product = 1 (multiplicative identity)
Sum of elements	first element	0	Empty sum = 0 (additive identity)
Count nodes in tree	1 for null	0 for null	Nothing to count in empty tree
Is array sorted?	False for empty	True for empty	Vacuously true - nothing out of order
Count permutations	0 for empty	1 for empty	One way to arrange nothing: do nothing

Verify with Math and Composition

Always check: (1) Does this base case value match the mathematical definition? (2) When plugged into the recursive formula, does it produce correct results for small cases? Test factorial(2) = 2 * factorial(1) = 2 * 1 = 2 ✓

Mistake #3: Base Case Condition Too Narrow

The Error: The base case catches some but not all termination points, allowing recursion to 'skip over' into invalid states. Why It Happens: Only considering positive cases, forgetting n could reach 0 or negative Multi-step recursion (n-2) reaching beyond single-step base (n=0) Not thinking about edge cases in the input space Symptoms: Works for most inputs, fails for specific edge cases Stack overflow only for certain inputs

base_too_narrow.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
# ❌ 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

Use Inequalities for Robustness

Instead of 'if n == 0', prefer 'if n <= 0' unless you specifically need to distinguish negative inputs. This catches inputs that might 'overshoot' the exact boundary. It's defensive programming for recursion.

Mistake #4: Base Case Condition Too Broad

The Error: The base case triggers too early, cutting off computation before it should, or handling inputs that need further recursion. Why It Happens: Being overly defensive after previous off-by-one bugs Misunderstanding when recursion should stop Copy-paste with wrong threshold adjustment Symptoms: Function terminates but returns incomplete or approximate results Some computations are skipped entirely

base_too_broad.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
# ❌ 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!

Minimal Base Cases Are Safer

The safest base cases handle only truly indivisible inputs: empty arrays, single elements, n=0, null nodes. Trying to optimize by handling larger base cases (like n \leq 2) introduces complexity and more chances for errors.

Mistake #5: Forgetting Edge Cases in Input

The Error: Base cases work for 'normal' inputs but fail for edge cases like empty collections, null pointers, negative numbers, or single-element inputs. Why It Happens: Testing only with 'happy path' inputs Assuming inputs will always be 'reasonable' Not considering what the caller might pass Symptoms: Works for typical inputs Crashes or gives wrong answers for edge inputs Index out of bounds, null pointer exceptions

edge_case_mistakes.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
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])

Edge Cases to Always Consider

•Empty collections: [], "", empty set, empty map
•Null/None pointers: Especially in tree/linked list recursion
•Single-element inputs: [x], "a", single node
•Negative numbers: If your base case is n == 0, what about n = -5?
•Zero: Is n=0 valid input? What should it return?
•Large inputs: Will you hit recursion limit?
•Duplicates: Do duplicates affect your base case logic?

Mistake #6: Incorrect Order of Base Case Checks

The Error: Multiple base cases are checked in the wrong order, causing one to shadow another or causing errors when an earlier check should have returned. Why It Happens: Adding base cases incrementally without reorganizing Not thinking about check dependencies Optimizing for the common case at the expense of edge cases Symptoms: Code crashes on specific inputs Wrong base case is triggered Index/null errors before intended checks run

base_case_order.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
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)

The Golden Order

Check in this order: (1) Null/empty/invalid first, (2) Boundary conditions second, (3) Most specific valid cases third, (4) Less specific cases fourth, (5) Recursive case last. This prevents crashes and ensures correct case matching.

Mistake #7: Type Mismatch Between Base and Recursive Cases

The Error: The base case returns a different type than the recursive case expects, causing type errors or silent incorrect behavior. Why It Happens: Not thinking about how return values compose Using None when the recursive case expects a number Returning single values vs. collections inconsistently Symptoms: TypeError when trying to operate on return value'Cannot add NoneType to int' Results are None for some inputs, numbers for others

type_mismatch.py
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

Use Type Hints

Type annotations and static analysis tools (mypy, TypeScript) catch many type mismatches before runtime. Always annotate your recursive functions' return types and use a type checker.

Data Structures & AlgorithmsBase Cases & Recursive Cases

Base Cases & Recursive Cases

LevelBeginner

Duration60 mins

TopicBase Cases & Recursive Cases

4 / 4

Common Mistakes: Missing or Wrong Base Cases

Learning from Failure

Even experienced developers make mistakes with base cases. These errors are particularly insidious because they often produce code that works for simple inputs but fails catastrophically for edge cases or at scale. This page is a field guide to the most common base case mistakes: what they look like, why they happen, how to detect them, and most importantly, how to prevent them. By studying these patterns of failure, you'll develop the defensive reflexes to catch them before they cause problems.

What You Will Learn

By the end of this page, you will recognize the most common base case errors, understand why each mistake leads to incorrect behavior, develop strategies to prevent these mistakes proactively, know how to debug base case issues when they occur, and build a mental checklist for validating recursive functions.

Mistake #1: Missing Base Case Entirely

The Error: Writing a recursive function that never stops recursing—no base case exists at all. Why It Happens: Developer focuses on the recursive logic first and forgets to add the stopping condition The base case seems 'obvious' and gets mentally skipped Copy-paste from a non-recursive version without adding termination Symptoms: Immediate stack overflow on any input Freeze/hang as the program allocates stack frames endlessly

missing_base_case.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
# ❌ 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))

Prevention: Base Case First

Make it a habit to ALWAYS write your base case before writing any recursive logic. Start every recursive function with 'if (base condition): return base_value'. Only after that should you write the recursive call.

Mistake #2: Wrong Base Case Value

The Error: The function terminates correctly but returns the wrong value for base cases, causing all results to be incorrect. Why It Happens: Misunderstanding the mathematical definition (Is 0! equal to 0 or 1?) Off-by-one in counting logic Returning a value that doesn't compose correctly with the recursive case Symptoms: No stack overflow (function terminates) Results are consistently wrong by a constant factor All answers are off by 1, or all are doubled, or all are 0

wrong_base_value.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
# ❌ 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)

Common Wrong Base Values
Problem	Wrong Value	Correct Value	Why
Factorial n!	0	1	Empty product = 1 (multiplicative identity)
Sum of elements	first element	0	Empty sum = 0 (additive identity)
Count nodes in tree	1 for null	0 for null	Nothing to count in empty tree
Is array sorted?	False for empty	True for empty	Vacuously true - nothing out of order
Count permutations	0 for empty	1 for empty	One way to arrange nothing: do nothing

Verify with Math and Composition

Always check: (1) Does this base case value match the mathematical definition? (2) When plugged into the recursive formula, does it produce correct results for small cases? Test factorial(2) = 2 * factorial(1) = 2 * 1 = 2 ✓

Mistake #3: Base Case Condition Too Narrow

The Error: The base case catches some but not all termination points, allowing recursion to 'skip over' into invalid states. Why It Happens: Only considering positive cases, forgetting n could reach 0 or negative Multi-step recursion (n-2) reaching beyond single-step base (n=0) Not thinking about edge cases in the input space Symptoms: Works for most inputs, fails for specific edge cases Stack overflow only for certain inputs

base_too_narrow.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
# ❌ 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

Use Inequalities for Robustness

Instead of 'if n == 0', prefer 'if n <= 0' unless you specifically need to distinguish negative inputs. This catches inputs that might 'overshoot' the exact boundary. It's defensive programming for recursion.

Mistake #4: Base Case Condition Too Broad

The Error: The base case triggers too early, cutting off computation before it should, or handling inputs that need further recursion. Why It Happens: Being overly defensive after previous off-by-one bugs Misunderstanding when recursion should stop Copy-paste with wrong threshold adjustment Symptoms: Function terminates but returns incomplete or approximate results Some computations are skipped entirely

base_too_broad.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
# ❌ 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!

Minimal Base Cases Are Safer

The safest base cases handle only truly indivisible inputs: empty arrays, single elements, n=0, null nodes. Trying to optimize by handling larger base cases (like n \leq 2) introduces complexity and more chances for errors.

Mistake #5: Forgetting Edge Cases in Input

The Error: Base cases work for 'normal' inputs but fail for edge cases like empty collections, null pointers, negative numbers, or single-element inputs. Why It Happens: Testing only with 'happy path' inputs Assuming inputs will always be 'reasonable' Not considering what the caller might pass Symptoms: Works for typical inputs Crashes or gives wrong answers for edge inputs Index out of bounds, null pointer exceptions

edge_case_mistakes.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
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])

Edge Cases to Always Consider

•Empty collections: [], "", empty set, empty map
•Null/None pointers: Especially in tree/linked list recursion
•Single-element inputs: [x], "a", single node
•Negative numbers: If your base case is n == 0, what about n = -5?
•Zero: Is n=0 valid input? What should it return?
•Large inputs: Will you hit recursion limit?
•Duplicates: Do duplicates affect your base case logic?

Mistake #6: Incorrect Order of Base Case Checks

The Error: Multiple base cases are checked in the wrong order, causing one to shadow another or causing errors when an earlier check should have returned. Why It Happens: Adding base cases incrementally without reorganizing Not thinking about check dependencies Optimizing for the common case at the expense of edge cases Symptoms: Code crashes on specific inputs Wrong base case is triggered Index/null errors before intended checks run

base_case_order.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
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)

The Golden Order

Check in this order: (1) Null/empty/invalid first, (2) Boundary conditions second, (3) Most specific valid cases third, (4) Less specific cases fourth, (5) Recursive case last. This prevents crashes and ensures correct case matching.

Mistake #7: Type Mismatch Between Base and Recursive Cases

The Error: The base case returns a different type than the recursive case expects, causing type errors or silent incorrect behavior. Why It Happens: Not thinking about how return values compose Using None when the recursive case expects a number Returning single values vs. collections inconsistently Symptoms: TypeError when trying to operate on return value'Cannot add NoneType to int' Results are None for some inputs, numbers for others

type_mismatch.py
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

Use Type Hints

Type annotations and static analysis tools (mypy, TypeScript) catch many type mismatches before runtime. Always annotate your recursive functions' return types and use a type checker.

Common Mistakes: Missing or Wrong Base Cases

Learning from Failure

Mistake #1: Missing Base Case Entirely

Mistake #2: Wrong Base Case Value

Mistake #3: Base Case Condition Too Narrow

Mistake #4: Base Case Condition Too Broad

Mistake #5: Forgetting Edge Cases in Input

Mistake #6: Incorrect Order of Base Case Checks

Mistake #7: Type Mismatch Between Base and Recursive Cases

There’s more to understand.

Common Mistakes: Missing or Wrong Base Cases

Learning from Failure

Mistake #1: Missing Base Case Entirely

Mistake #2: Wrong Base Case Value

Mistake #3: Base Case Condition Too Narrow

Mistake #4: Base Case Condition Too Broad

Mistake #5: Forgetting Edge Cases in Input

Mistake #6: Incorrect Order of Base Case Checks

Mistake #7: Type Mismatch Between Base and Recursive Cases

There’s more to understand.