Base Cases & Recursive Cases: Designing Correct Recursion

Every recursive function is built from two kinds of cases. A base case is an input small enough to answer directly, with no further recursion — it stops the process. A recursive case breaks the problem into a smaller instance of itself and combines the result. Get the base case wrong and recursion never stops; get the shrinking wrong and it never reaches the base case. This page is about getting both right, every time.

A reliable three-question recipe

Before writing any recursive function, answer:

1. What is the smallest input? That is your base case — return its answer directly.
2. How do I make the problem smaller? The recursive case must move toward the base case (smaller n, shorter list, closer index).
3. How do I combine the smaller answer into mine? Trust the recursive call to be correct, then build on top of it.

Here is “is this string a palindrome?” expressed with that recipe. Base case: a string of length 0 or 1 is trivially a palindrome. Recursive case: ends must match, and the inside must also be a palindrome.

bool isPalindrome(const std::string& s, int lo, int hi) {
    if (lo >= hi) return true;                 // base case: 0 or 1 char left
    if (s[lo] != s[hi]) return false;          // mismatch
    return isPalindrome(s, lo + 1, hi - 1);    // shrink inward
}

boolean isPalindrome(String s, int lo, int hi) {
    if (lo >= hi) return true;                 // base case: 0 or 1 char left
    if (s.charAt(lo) != s.charAt(hi)) return false; // mismatch
    return isPalindrome(s, lo + 1, hi - 1);    // shrink inward
}

function isPalindrome(s, lo, hi) {
  if (lo >= hi) return true;                   // base case: 0 or 1 char left
  if (s[lo] !== s[hi]) return false;           // mismatch
  return isPalindrome(s, lo + 1, hi - 1);      // shrink inward
}

def is_palindrome(s, lo, hi):
    if lo >= hi:
        return True               # base case: 0 or 1 char left
    if s[lo] != s[hi]:
        return False              # mismatch
    return is_palindrome(s, lo + 1, hi - 1)  # shrink inward

The base case must be reachable

A base case only helps if every recursive call eventually hits it. Two classic bugs:

• Wrong direction. factorial(n + 1) grows away from 0 forever.
• Skipping past it. Decreasing by 2 from an odd n toward a == 0 base case overshoots into negatives. Use <= 0 or <= 1 as a guard so you never miss it.

Tip: Make base-case conditions inclusive (n <= 1, lo >= hi) rather than exact (n == 1, lo == hi). An inclusive guard catches the off-by-one and the “already past it” inputs, killing a whole class of infinite-recursion bugs.

Multiple base cases are fine

Some problems need more than one stopping point. Fibonacci needs two, because each step looks back two steps:

int fib(int n) {
    if (n == 0) return 0;   // base case 1
    if (n == 1) return 1;   // base case 2
    return fib(n - 1) + fib(n - 2);
}

int fib(int n) {
    if (n == 0) return 0;   // base case 1
    if (n == 1) return 1;   // base case 2
    return fib(n - 1) + fib(n - 2);
}

function fib(n) {
  if (n === 0) return 0;    // base case 1
  if (n === 1) return 1;    // base case 2
  return fib(n - 1) + fib(n - 2);
}

def fib(n):
    if n == 0:
        return 0            # base case 1
    if n == 1:
        return 1            # base case 2
    return fib(n - 1) + fib(n - 2)

Going deeper: This fib is correct but O(2ⁿ) — it recomputes the same values exponentially. The fix is to remember answers (memoization). A correct base case guarantees termination; it does not guarantee efficiency.

Validate input at the boundary, not in every call

If an empty input is meaningful, fold it into the base case (if (n <= 1) return 1 already covers n == 0). If empty input is an error, check it once in a thin public wrapper, then let the recursive helper assume valid input. This keeps the hot recursive path clean and avoids re-validating on every frame.

Checklist before you run it

• There is at least one base case, and it returns without recursing.
• Every recursive call moves strictly closer to a base case.
• Base-case guards are inclusive to avoid overshooting.
• You trust the recursive call’s result instead of mentally tracing all of it.

Next: weigh recursion against loops in recursion vs iteration, or practice on the recursion exercises.