Base Cases And Recursive Cases - Learning Module

Loading content...

0/279

Multiple Base Cases

When One Base Case Isn't Enough

In the previous page, we established that every recursive function needs at least one base case to terminate. But what happens when the problem structure is more complex? When there are multiple 'ground floors'? When the recursive decomposition can end in different ways?

The answer: Multiple base cases.

Many real-world recursive functions require not one, but several distinct stopping conditions. The classic Fibonacci sequence needs two. Binary search might have two or three. Tree traversals handle different structural configurations. Getting these multiple base cases right—covering all termination scenarios without redundancy or gaps—is an essential recursive skill.

What You Will Learn

By the end of this page, you will understand why some problems require multiple base cases, how to identify when multiple base cases are needed, techniques for designing coordinated sets of base cases, common patterns that signal multi-base-case requirements, and how to verify completeness—that all termination paths are covered.

Why Multiple Base Cases?

A single base case suffices when recursion always reduces the problem the same way and terminates at a single point. But this isn't always the case.

Scenario 1: Multiple Reduction Paths

When recursion can reduce the problem in different ways (e.g., n-1 and n-2), each reduction path might reach a different 'floor.'

Scenario 2: Multiple Valid 'Smallest' Inputs

Some problems have multiple inputs that qualify as 'smallest'—like n=0 and n=1 for Fibonacci.

Scenario 3: Different Input Configurations

Tree traversals might hit null nodes, leaf nodes, or special structural patterns—each requiring different handling.

Scenario 4: Success vs. Failure Termination

Some problems can terminate successfully (found what we're looking for) or unsuccessfully (exhausted search space). Each needs its own base case.

The Consequence of Missing Base Cases:

If your recursive logic can reach a state not covered by any base case, the function will continue recursing on invalid input—causing stack overflow, incorrect results, or runtime errors.

fibonacci_single_vs_multiple.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
# ❌ 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 ✓

The 'Off-by-One' Trap

When recursion reduces by more than 1 (like Fibonacci with n-1 AND n-2), a single base case at n=0 isn't enough. The recursion might 'skip over' to n=-1. You need base cases to catch all potential landing points.

The Fibonacci Pattern: Two-Step Recursion

The Fibonacci sequence is the canonical example of a function requiring two base cases. Let's understand why structurally.

The Recurrence:

F(n) = F(n-1) + F(n-2), for n ≥ 2

The Problem:

F(n) makes two recursive calls: to F(n-1) and F(n-2)
Starting from any n ≥ 2, forward simulation shows both paths need termination
F(2) → F(1) and F(0)
F(3) → F(2) and F(1) → F(1), F(0), F(1)

Both F(0) and F(1) will be reached from any starting point n ≥ 2. Therefore, both must be defined.

The Mathematical Definition:

F(0) = 0  (1st base case)
F(1) = 1  (2nd base case)
F(n) = F(n-1) + F(n-2), for n ≥ 2

This isn't arbitrary—it's the mathematical definition of the Fibonacci sequence. The code mirrors this exactly.

fibonacci_analysis.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
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!

Alternative: Consolidating Base Cases

Some implementations combine these into a single statement:

if n <= 1:
    return n  # Returns 0 if n==0, 1 if n==1

This is elegant but works only because F(0) = 0 and F(1) = 1 happen to match the value of n. For other problems, explicit separate base cases are clearer and safer.

Generalization: k-Step Recursion

Any recursion that steps back by amounts up to k requires k base cases:

1-step (n-1 only): 1 base case at n=0
2-step (n-1 and n-2): 2 base cases at n=0 and n=1
3-step (n-1, n-2, n-3): 3 base cases at n=0, n=1, and n=2

This pattern appears in problems like "count ways to climb stairs with up to k steps."

Count Your Steps

Quick rule: If your recursive case decrements by at most k, you need k base cases. For Fibonacci, k=2, so 2 base cases. For a tribonacci-like recurrence (n-1, n-2, n-3), k=3, so 3 base cases.

Success vs. Failure Base Cases

Search and decision problems often have two fundamentally different ways to terminate:

Success: Found what we're looking for
Failure: Exhausted all possibilities without finding it

Each requires its own base case with distinct return values.

Example: Binary Search

Binary search can terminate two ways:

Success: Element found at some index
Failure: Search space exhausted (low > high)

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

The Pattern in Decision Problems

Many recursive problems have this success/failure duality:

Problem	Success Base Case	Failure Base Case
Binary Search	Element found	Search space empty
Path Finding	Reached destination	Dead end / visited
Subset Sum	Sum equals target	No more elements
String Matching	Pattern found	String exhausted

Order Matters for Success/Failure

When you have both success and failure base cases, check for success AFTER checking for the failure condition at the boundary. In binary search, we first check if low > high (failure), then check if we found the element (success). Reversing this order can lead to index-out-of-bounds errors.

Tree Traversal: Structural Base Cases

Tree recursion often requires base cases based on structural properties rather than numeric conditions. The structure of the data determines when recursion stops.

Common Tree Base Cases:

Null node (empty tree): The tree/subtree doesn't exist
Leaf node: A node with no children
Special structural configuration: One child, both children present, etc.

Different problems emphasize different base cases:

tree_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
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)

Choosing the Right Structural Base Cases:

Problem Type	Base Case(s)	Why
Counting/Summing all nodes	null → 0	Every node contributes; null contributes nothing
Operations on leaves only	null → 0, leaf → value	Distinguish leaves from internal nodes
Search problems	null → False, found → True	Handle not-found vs. found cases
Tree comparison	both null → True, one null → False	Compare structures symmetrically
Height calculation	null → -1 (or 0)	Define height at base level

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

Think in Structural Configurations

For tree problems, enumerate all possible structural states at a node: (null), (leaf), (left child only), (right child only), (both children). Decide which states are base cases and which require recursion. This ensures completeness.

Coordinating Multiple Base Cases

When a function has multiple base cases, they must work together coherently. Here are principles for coordination:

Principle 1: Base Cases Must Be Disjoint

No input should match more than one base case condition. Overlapping base cases create ambiguity about which return value to use.

Principle 2: Base Cases Must Be Exhaustive

Every non-recursive termination point must be covered. If recursion can reach a state that matches no base case, the function will fail.

Principle 3: Order of Checks Matters

Check more specific conditions before more general ones. Check failure/boundary conditions before success conditions.

Principle 4: Return Values Must Be Type-Consistent

All base cases (and the recursive case) must return compatible types. Mixing int and None without proper handling causes bugs.

Principle 5: Base Cases Should Handle Edge Inputs

Consider what happens with the most 'extreme' valid inputs (0, 1, empty, null). These are your base cases.

coordinated_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
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))

Coordination Checklist

•Disjoint: Can any input trigger more than one base case? (Should be NO)
•Exhaustive: Can recursion reach a state matching NO base case? (Should be NO)
•Ordered: Are bounds checked before content access? (Should be YES)
•Type-safe: Do all paths return the same type? (Should be YES)
•Meaningful: Does each base case return a semantically correct value? (Should be YES)

Real-World Example: Permutations

Let's work through a more complex example: generating all permutations of a list. This problem beautifully illustrates multiple base cases and their coordination.

Problem: Given a list of distinct elements, generate all possible orderings (permutations).

Analysis:

Permutations of [1, 2, 3]: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] (6 total = 3!)
Recursive idea: For each element, make it first, then permute the rest

Base Case Identification:

What's the smallest input? An empty list [] or a single-element list [x]
Permutations of []? Just one: [[]] (the empty permutation)
Permutations of [x]? Just one: [[x]]

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

The Empty Permutation

Returning [[]] for an empty list (not just []) is crucial. There is ONE permutation of the empty list: the empty arrangement itself. This mirrors how 0! = 1 (one way to arrange nothing). Returning [] would incorrectly say there are ZERO permutations.

Patterns That Signal Multiple Base Cases

Certain problem characteristics reliably indicate the need for multiple base cases. Learn to recognize these signals:

Patterns Requiring Multiple Base Cases
Pattern	Signal	Typical Base Cases	Example
Multi-step recursion	f(n-1), f(n-2), ..., f(n-k)	k base cases: f(0), f(1), ..., f(k-1)	Fibonacci, climb stairs
Search with success/fail	Looking for something	Found case + not-found case	Binary search, contains
Two-input functions	Two parameters shrink	Each param's minimum, combinations	GCD, string matching
Comparison functions	Comparing two structures	Both empty, one empty, both present	Tree equality, merge sorted
Accumulation over pairs	Processing elements pairwise	0 elements, 1 element cases	Run-length encoding
Backtracking	Try options, rollback on failure	Goal reached, no options left	N-queens, sudoku

two_input_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
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)

Two Inputs → Consider Four Cases

For functions with two inputs that both shrink, systematically consider four scenarios: (1) both at base, (2) first at base only, (3) second at base only, (4) neither at base. Cases 1-3 are typically base cases; case 4 is recursive.

Summary: Mastering Multiple Base Cases

Many real-world recursive functions require more than one base case. Mastering the design of multiple base cases is essential for writing correct, robust recursive code.

Key Takeaways

•Multi-step recursion needs multiple base cases — If f(n) calls f(n-1) AND f(n-2), you need bases at both n=0 and n=1.
•Success vs. Failure are distinct terminations — Search problems need base cases for both 'found' and 'not found' outcomes.
•Structure dictates base cases — Tree problems may need different handling for null, leaf, and internal nodes.
•Base cases must be disjoint and exhaustive — No overlap, no gaps. Every termination path must be covered.
•Order of checks matters — Check bounds before accessing elements; check failure before success to avoid errors.
•Two-input functions may need combinatorial base cases — Consider all combinations of inputs at their minimum values.
•The empty case often has a meaningful answer — Permutations of [] is [[]], not []. Empty product is 1, not 0.

What's Next:

Having a correct base case isn't enough—your recursive calls must actually reach it. The next page covers ensuring progress toward the base case: guaranteeing that each recursive call moves closer to termination, and detecting when it doesn't.

Page Complete

You now understand when and why multiple base cases are needed, and how to coordinate them correctly. This skill is essential for handling complex recursive problems like Fibonacci variants, tree comparisons, and multi-dimensional search. Next, we'll ensure your recursion actually converges to these base cases.