DSA Tutorial
🔍
Base Case & Recursive Case
The Two-Part Contract
Every recursive function is a contract with two clauses:
CONTRACT:
1. BASE CASE: "I know the answer directly for these simple inputs."
2. RECURSIVE CASE: "For all other inputs, I can reduce the problem
to a simpler version of itself — and I trust that
the simpler version will return the correct answer."
If both clauses are honoured for all valid inputs,
the function is correct for ALL inputs.
The formal name for this guarantee is MATHEMATICAL INDUCTION:
- Base case = Base step (n=0 or n=1 is true)
- Recursive case = Inductive step (if true for n-1, prove true for n)
Designing a Base Case
A correct base case must satisfy two properties:
PROPERTY 1: Solvable without recursion The answer for this input is known directly — no sub-problem needed. It is the "atomic" version of the problem. PROPERTY 2: Reachable from any valid input For EVERY valid input, repeated application of the recursive case must eventually produce a base case input. An unreachable base case is a bug. TEST: for each base case, ask: "Is every valid input guaranteed to reach this base case?" If not — either the base case is missing some inputs, or the recursive case does not make progress.
Common Base Case Patterns
NUMERIC: if n == 0: → zero is trivial (factorial, sum, power) if n <= 1: → covers both 0 and 1 (Fibonacci, binary search) if n < 0: → invalid input guard if lo > hi: → empty range in divide-and-conquer (binary search) STRUCTURAL (list/string/tree): if not arr: → empty list is the base if len(arr) == 1: → single element cannot be divided further if not node: → null/None node in tree traversal if lo == hi: → single-element subarray in merge sort LOGICAL: if found: → target already located, no need to recurse if target == node.val: → found in tree search
Designing the Recursive Case
The recursive case must:
REQUIREMENT 1: Call itself with a SMALLER argument "Smaller" means strictly closer to the base case. For numbers: n-1 is smaller than n (if base is n==0) For arrays: arr[1:] is smaller than arr (if base is empty arr) For trees: node.left is smaller than the tree rooted at node REQUIREMENT 2: Use the result of the recursive call The recursive case must actually use what the sub-call returns. Just calling the function without using its result is usually wrong. (Exception: recursive procedures that have side effects, not return values) REQUIREMENT 3: Combine sub-results correctly The current level's answer must be correctly computed from the sub-problem's answer. factorial: n × factorial(n-1) ← multiply this level's n reverse: reverse(tail) + [head] ← append head to reversed tail sum: head + sum(tail) ← add head to sum of rest
Building Correct Recursive Functions
Step-by-Step Design Process
1. IDENTIFY the base case(s) What is the simplest version of this problem? What input has a known answer without any recursion? 2. VERIFY the base case is reachable From any valid input, does the recursive case always produce an argument closer to the base case? 3. WRITE the recursive case Assume the function works correctly for input (n-1) or (smaller). Express the answer for input n using the answer for (n-1). 4. TRUST AND VERIFY Mentally execute for the smallest non-trivial input (n=2 or n=1). Does it produce the correct answer using the base case?
Examples: Designing Base Cases and Recursive Cases
Example 1: Sum of Digits
Java
1public class SumOfDigits {
2
3 // Sum of digits of n e.g. sumDigits(123) = 1+2+3 = 6
4 public static int sumDigits(int n) {
5 // BASE CASE: single digit — value IS the sum
6 if (n < 10) return n;
7
8 // RECURSIVE CASE: last digit + sum of remaining digits
9 // Progress: n/10 < n for all n >= 10 (strips last digit each time)
10 return (n % 10) + sumDigits(n / 10);
11 }
12
13 public static void main(String[] args) {
14 System.out.println(sumDigits(0)); // 0
15 System.out.println(sumDigits(9)); // 9
16 System.out.println(sumDigits(123)); // 6 (1+2+3)
17 System.out.println(sumDigits(9999)); // 36 (9+9+9+9)
18 System.out.println(sumDigits(12345)); // 15 (1+2+3+4+5)
19 }
20}Output:
0
9
6
36
15
Trace: sumDigits(123)
sumDigits(123):
n=123 ≥ 10 → recursive case
(123 % 10) + sumDigits(123 / 10)
= 3 + sumDigits(12)
sumDigits(12):
n=12 ≥ 10 → recursive case
(12 % 10) + sumDigits(12 / 10)
= 2 + sumDigits(1)
sumDigits(1):
n=1 < 10 → BASE CASE → return 1
returns: 2 + 1 = 3
returns: 3 + 3 = 6 ✓
Progress check: 123 → 12 → 1 → base case ✓ (each call strips one digit)
Example 2: Check Palindrome
Java
1public class Palindrome {
2
3 // A string is a palindrome if it reads the same forward and backward
4 public static boolean isPalindrome(String s) {
5 // BASE CASE 1: empty string — trivially a palindrome
6 if (s.length() == 0) return true;
7
8 // BASE CASE 2: single character — trivially a palindrome
9 if (s.length() == 1) return true;
10
11 // RECURSIVE CASE:
12 // First and last characters must match AND
13 // the inner substring must also be a palindrome
14 if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
15 return isPalindrome(s.substring(1, s.length() - 1));
16 }
17
18 public static void main(String[] args) {
19 System.out.println(isPalindrome("")); // true
20 System.out.println(isPalindrome("a")); // true
21 System.out.println(isPalindrome("aa")); // true
22 System.out.println(isPalindrome("racecar")); // true
23 System.out.println(isPalindrome("hello")); // false
24 System.out.println(isPalindrome("abcba")); // true
25 }
26}Output:
true
true
true
false
true
Trace: isPalindrome("racecar")
isPalindrome("racecar"):
length=7 → not base case
s[0]='r', s[-1]='r' → match
recurse: isPalindrome("aceca")
isPalindrome("aceca"):
length=5 → not base case
s[0]='a', s[-1]='a' → match
recurse: isPalindrome("cec")
isPalindrome("cec"):
length=3 → not base case
s[0]='c', s[-1]='c' → match
recurse: isPalindrome("e")
isPalindrome("e"):
length=1 → BASE CASE → return True
returns: True
returns: True
returns: True ✓
Progress: "racecar"(7) → "aceca"(5) → "cec"(3) → "e"(1) → base
Length shrinks by 2 each call — guaranteed to reach length ≤ 1 ✓
Example 3: Flatten a Nested List
A structural base case — the "atom" of the structure.
Java
1import java.util.*;
2
3public class FlattenList {
4
5 public static List<Integer> flatten(Object input) {
6 List<Integer> result = new ArrayList<>();
7
8 if (input instanceof Integer) {
9 // BASE CASE: single integer — "atom", not a list
10 result.add((Integer) input);
11 } else if (input instanceof List) {
12 // RECURSIVE CASE: for each element in the list,
13 // flatten it and add all results
14 for (Object element : (List<?>) input) {
15 result.addAll(flatten(element));
16 }
17 }
18
19 return result;
20 }
21
22 public static void main(String[] args) {
23 // Nested structure: [1, [2, [3, 4], 5], [6, 7]]
24 List<Object> nested = new ArrayList<>();
25 nested.add(1);
26 List<Object> inner1 = new ArrayList<>();
27 inner1.add(2);
28 List<Object> inner2 = new ArrayList<>();
29 inner2.add(3); inner2.add(4);
30 inner1.add(inner2);
31 inner1.add(5);
32 nested.add(inner1);
33 List<Object> inner3 = new ArrayList<>();
34 inner3.add(6); inner3.add(7);
35 nested.add(inner3);
36
37 System.out.println(flatten(nested)); // [1, 2, 3, 4, 5, 6, 7]
38 }
39}Output:
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
Multiple Base Cases
Some problems genuinely require more than one base case. The most common patterns:
Pattern 1: Two boundary values
Fibonacci: fib(0) = 0, fib(1) = 1 Both are needed because the recursive case uses both fib(n-1) AND fib(n-2). If only fib(0) were defined, fib(2) = fib(1) + fib(0) would try fib(1) which would try fib(0) + fib(-1) — going negative forever. Binary search: base case for lo > hi (not found) AND lo == hi (found or not) lo > hi: empty range — target absent, return -1 lo == hi: single element — check arr[lo] == target
Pattern 2: Different structural boundaries
isPalindrome: len(s) == 0: empty string is a palindrome (even-length strings reduce to this) len(s) == 1: single char is a palindrome (odd-length strings reduce to this) Both needed: "aa" reduces to "" (even); "aba" reduces to "b" (odd). Tree problems: node is None: empty tree — e.g. height = 0 node.left is None AND node.right is None: leaf node — e.g. height = 1 (Some problems only need the null check; some need both)
Java
1public class MultipleBaseCases {
2
3 // Fibonacci — two base cases, both essential
4 public static int fib(int n) {
5 if (n == 0) return 0; // Base case 1: fib(0) = 0
6 if (n == 1) return 1; // Base case 2: fib(1) = 1
7 return fib(n - 1) + fib(n - 2);
8 }
9
10 // Binary search — two base cases with different meanings
11 public static int binarySearch(int[] arr, int target, int lo, int hi) {
12 if (lo > hi) return -1; // Base case 1: empty range — not found
13 int mid = lo + (hi - lo) / 2;
14 if (arr[mid] == target) return mid; // Base case 2: found
15
16 if (arr[mid] < target) return binarySearch(arr, target, mid + 1, hi);
17 else return binarySearch(arr, target, lo, mid - 1);
18 }
19
20 // Tree height — null check AND leaf check
21 static class TreeNode {
22 int val; TreeNode left, right;
23 TreeNode(int v) { val = v; }
24 }
25
26 public static int height(TreeNode node) {
27 if (node == null) return 0; // Base case 1: null node — height 0
28 // Base case 2 implicit: leaf nodes recurse into null children → 1 + max(0,0) = 1
29 return 1 + Math.max(height(node.left), height(node.right));
30 }
31
32 public static void main(String[] args) {
33 System.out.println(fib(0)); // 0
34 System.out.println(fib(1)); // 1
35 System.out.println(fib(6)); // 8
36
37 int[] arr = {1, 3, 5, 7, 9};
38 System.out.println(binarySearch(arr, 7, 0, 4)); // 3
39 System.out.println(binarySearch(arr, 4, 0, 4)); // -1
40 }
41}Output:
0 1 8
3
-1
Common Base Case Mistakes
Mistake 1: Off-by-one base case
WRONG:
def factorial(n):
if n == 1: return 1 ← base case only handles n=1
return n * factorial(n-1)
factorial(0): n=0 ≠ 1 → 0 * factorial(-1)
→ factorial(-2) → ... → forever!
CORRECT:
def factorial(n):
if n <= 0: return 1 ← handles n=0 AND negative
return n * factorial(n-1)
Or better: guard invalid input first:
def factorial(n):
if n < 0: raise ValueError
if n == 0: return 1
return n * factorial(n-1)
Mistake 2: Missing base case for a branch
WRONG — binary search missing the "not found" case:
def search(arr, target, lo, hi):
mid = (lo + hi) // 2
if arr[mid] == target: return mid ← only "found" base case
# Missing: lo > hi → not found
if arr[mid] < target: return search(arr, target, mid+1, hi)
else: return search(arr, target, lo, mid-1)
↑ when lo > hi, this divides by producing wrong mid, infinite recursion
CORRECT:
def search(arr, target, lo, hi):
if lo > hi: return -1 ← "not found" base case
mid = lo + (hi - lo) // 2
if arr[mid] == target: return mid ← "found" base case
...
Mistake 3: Recursive case does not reduce the problem
WRONG:
def count_down(n):
if n == 0: return
count_down(n) ← n is unchanged! Infinite recursion.
CORRECT:
def count_down(n):
if n == 0: return
count_down(n - 1) ← n-1 is strictly smaller
ANOTHER WRONG:
def sum_list(lst):
if not lst: return 0
return sum_list(lst) ← passes same list! Off by one error.
CORRECT:
def sum_list(lst):
if not lst: return 0
return lst[0] + sum_list(lst[1:]) ← lst[1:] is strictly shorter
The Trust-and-Verify Method
Formal correctness check for any recursive function:
METHOD:
Step 1: VERIFY the base case(s) directly.
Check: does the function return the correct answer for each base case input?
For factorial: factorial(0) = 1. Is 1 the correct value of 0!? Yes ✓
Step 2: ASSUME the recursive call is correct for (n-1).
Do not trace — just assume: factorial(n-1) returns (n-1)!
Step 3: VERIFY the recursive case uses that assumption correctly.
factorial(n) = n * factorial(n-1) = n * (n-1)! = n! ✓
Step 4: CHECK PROGRESS.
Is n-1 strictly closer to the base case (n==0) than n?
Yes — n-1 < n, and n is a non-negative integer → progress ✓
If ALL four steps pass: the function is correct for ALL n ≥ 0.
This is exactly mathematical induction, applied to code.
Java
1// Trust-and-verify applied to: count occurrences of x in array
2public class CountOccurrences {
3
4 public static int count(int[] arr, int x, int index) {
5 // Step 1: Verify base cases
6 if (index == arr.length) return 0; // Empty remaining → 0 occurrences ✓
7
8 // Step 2-3: Assume count(arr, x, index+1) correctly counts
9 // occurrences in arr[index+1..end].
10 // If arr[index] == x, add 1 to that count. ✓
11 int rest = count(arr, x, index + 1);
12 return (arr[index] == x ? 1 : 0) + rest;
13 }
14
15 // Step 4: Progress — index+1 > index → index moves toward arr.length ✓
16
17 public static void main(String[] args) {
18 int[] arr = {1, 3, 2, 3, 4, 3};
19 System.out.println(count(arr, 3, 0)); // 3
20 System.out.println(count(arr, 5, 0)); // 0
21 System.out.println(count(arr, 1, 0)); // 1
22 }
23}Output:
3
0
1
Checklist: Is Your Recursive Function Correct?
BASE CASE CHECKLIST: □ Does every valid input eventually reach a base case? □ Does the base case return the CORRECT answer for its input? □ Have you handled all boundary inputs (0, empty, null, negative)? □ For two-branch recursion (like Fibonacci): are ALL branches covered? RECURSIVE CASE CHECKLIST: □ Is the argument to the recursive call strictly closer to the base case? □ Does the recursive case USE the returned value from the recursive call? □ Is the combination logic correct? (multiply, add, append, etc.) □ Does the recursive case handle all non-base-case inputs? OVERALL: □ Does trust-and-verify pass? (base correct + inductive step correct) □ For small n (n=2 or n=1), does manual tracing give the right answer? □ For negative or empty input, does the function handle it gracefully?
Interview Questions
Q: What makes a base case "correct"?
A base case is correct if it satisfies two conditions: (1) it returns the right answer for that input without needing any recursive call — the answer is computed directly; and (2) every valid input can eventually reach it through repeated application of the recursive case. An unreachable base case is effectively no base case — the recursion will run infinitely for inputs that never reach it.
Q: How do you verify that the recursive case makes progress?
Identify a "measure" that strictly decreases with each call — an integer that gets closer to the base case value, or a data structure that gets smaller. For factorial(n): the measure is n, which decreases by 1 each call and has base case n==0. For flatten(lst): the measure is the total nesting depth, which decreases by 1 each time an atom is reached. If no such measure exists, the recursion does not terminate.
Q: Why does Fibonacci need two base cases?
The recursive case for Fibonacci is fib(n) = fib(n-1) + fib(n-2). For fib(2), the recursive calls are fib(1) and fib(0) — both must be defined. If only fib(0) were a base case, fib(1) would attempt fib(0) + fib(-1), and fib(-1) would trigger fib(-2) + fib(-3) — negative values forever. Both boundaries must be explicitly handled.
Summary
Every recursive function is a two-part contract: the base case (direct answer for trivial input) and the recursive case (reduces to a simpler sub-problem).
Designing a correct base case:
- ›Identifies the simplest version of the problem where the answer is immediate
- ›Must be reachable from every valid input through the recursive case
- ›Common patterns:
n == 0,len == 0,node is None,lo > hi
Designing a correct recursive case:
- ›Calls the function with a strictly smaller argument (closer to the base case)
- ›Uses the returned value to build the current level's answer
- ›Correctly combines the sub-problem's result with the current level's data
Multiple base cases: needed when the recursive case generates multiple branches, each potentially hitting a different boundary (Fibonacci: fib(0) and fib(1); palindrome: length 0 and length 1).
Trust-and-verify method (mathematical induction):
- ›Verify base case(s) return the correct answer directly
- ›Assume the recursive call returns the correct answer for smaller input
- ›Verify the current level uses that assumed result correctly
- ›Confirm the recursive call's argument strictly approaches the base case
If all four pass — the function is provably correct for all valid inputs.
In the next topic, you will explore Recursion Tree — the visual representation of how recursive calls branch, how to read a recursion tree, and how to use it to analyse time and space complexity.
Suggested Quiz
A base case must satisfy two conditions. Which pair is correct?
1/6