Lesson 14: Recursion — Base Cases and Recursive ThinkingAP

Unit 10 is recursion: a method that calls itself on a *smaller* version of the problem, until the problem is small enough to answer directly. Recursion is the unit where tracing skill matters most per line of code — a five-line recursive method can unfold into dozens of calls — and where the exam's questions are the most mechanical once you learn to draw the call stack instead of guessing.

The two ingredients

Every correct recursive method has:

• A base case: an input so small the answer is returned immediately, with no further recursion.
• A recursive case: a reduction of the problem (smaller number, shorter string, narrower range) plus a call to the same method on the reduced problem, combined appropriately.

public static int factorial(int n)
{
    if (n == 0)
    {
        return 1;                       // base case
    }
    return n * factorial(n - 1);        // recursive case: n shrinks toward 0
}

Trace factorial(4) as a stack of waiting calls — note that nothing is *computed* until the base case returns, and then the multiplications resolve on the way back up:

Each call is a separate frame with its own copy of the parameter — factorial(4)'s n and factorial(3)'s n are different variables that happen to share a name (Unit 5's scope rules, applied vertically). If the base case is missing or unreachable — say factorial(-1) with the code above, or a reduction that never shrinks — the calls pile up until the JVM runs out of stack space: StackOverflowError.

Recursion on strings and ranges

The reduction need not be numeric. Strings shrink by substring: to process a string recursively, handle the first character and recurse on the rest. Searching shrinks by range: recursive binary search passes smaller low/high bounds into the next call (the algorithm from Lesson 12, re-expressed). A classic trace:

public static String reverse(String s)
{
    if (s.length() <= 1)
    {
        return s;
    }
    return reverse(s.substring(1)) + s.substring(0, 1);
}

reverse("abc") = reverse("bc") + "a" = (reverse("c") + "b") + "a" = "c" + "b" + "a" = "cba". The first character waits at the end of each concatenation — draw the unfolding, don't try to feel it.

Recursion versus iteration

Anything written recursively can be written with loops, and vice versa. Iteration is usually clearer for simple repetition (accumulating a sum); recursion wins when the problem is *self-similar* — searching a sorted range by halves, processing a branching structure, merge sort's split-sort-merge. The exam's recursion questions are tracing questions and short method-writing questions; nobody is graded on choosing recursion for elegance, only on correctness. A pragmatic professional rule survives both worlds: the reduction must make strict progress toward the base case on every path — test the smallest inputs (0, 1, empty string, single element) first, because that is where recursive code dies.

Merge sort is the unit's flagship: split the array in half, recursively sort each half, then merge the two sorted halves into one. The merge step is a loop; the genius is that the recursion guarantees the halves arrive sorted. Runtime O(n log n) — the divide step contributes the log, the per-level merging the n.

Real-world design: recursion matches problem shape

File systems are trees; a "delete this folder" operation is recursive because folders contain folders (base case: an empty folder or a plain file). Web pages, org charts, family trees, and the expression parser inside every compiler share the shape. Professionals also learn recursion's limit: deep recursion on huge linear data can overflow the stack, which is why a loop is preferred for a million-element scan even when the recursive version reads beautifully.

Common mistakes (from examiner reports)

• Missing or unreachable base case. The single cause of essentially every StackOverflowError question.
• A reduction that doesn't shrink. Calling f(n) from f(n), or shrinking a string by 0 characters.
• Forgetting to return the recursive result. factorial(n - 1); as a statement computes and discards — the method then returns garbage or fails to compile.
• Combining in the wrong order. In string recursion, s.substring(0,1) + reverse(...) and reverse(...) + s.substring(0,1) produce reverses of each other; the exam tests precisely this.
• Assuming parameters are shared between calls. Each frame has its own copy; one frame's changes never leak into another.
• Testing only large inputs. Recursive bugs live at the boundary: always hand-check the base case and the smallest recursive case (n = 1 or a 2-character string).

AP Exam Experience

Question 1. Consider the following recursive method.

public static int mystery(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    return n + mystery(n - 2);
}

What is the value of mystery(6)?

• (A) 7
• (B) 12
• (C) 13
• (D) 21
• (E) The call never terminates.

Answer: (C). Unfold: mystery(6) = 6 + mystery(4) = 6 + 4 + mystery(2) = 6 + 4 + 2 + mystery(0) = 6 + 4 + 2 + 1 = 13. (B) drops the base case's 1; (D) adds the odd numbers too.

Question 2. Consider the following recursive method.

public static String shrink(String s)
{
    if (s.length() <= 1)
    {
        return s;
    }
    return shrink(s.substring(1)) + s.substring(0, 1);
}

What is returned by shrink("code")?

• (A) "code"
• (B) "edoc"
• (C) "cdeo"
• (D) "odec"
• (E) The call never terminates.

Answer: (B). Each call moves the first character to the end of the result being built: shrink("code") = shrink("ode") + "c" = shrink("de") + "o" + "c" = shrink("e") + "d" + "o" + "c" = "edoc". The string is fully reversed.

Question 3. Consider the following method.

public static int broken(int n)
{
    if (n == 0)
    {
        return 0;
    }
    return n + broken(n + 1);
}

Which of the following best describes the behaviour of a call to broken(5)?

• (A) It returns 15.
• (B) It returns 5.
• (C) It returns 0 after one recursive call.
• (D) It never reaches the base case and eventually causes a StackOverflowError.
• (E) It does not compile.

Answer: (D). The recursive call *increases* n (6, 7, 8, ...), moving away from the base case n == 0 forever. Reduction must shrink toward the base case — here it does the opposite.

Free-Response Question. This question involves writing recursive methods. You may not use loops in either part; both methods must be implemented recursively. (a) Write the static method sumDigits, which takes a non-negative int and returns the sum of its decimal digits. sumDigits(402) returns 6; sumDigits(7) returns 7; sumDigits(0) returns 0. (b) Write the static method isPalindrome, which takes a String and returns true if the string reads the same forwards and backwards, and false otherwise. isPalindrome("racecar") returns true; isPalindrome("java") returns false; strings of length 0 or 1 are palindromes.

Scoring guideline (9 points). Part (a) — 4 points:

• +1 Correct method header: static, returns int, one int parameter
• +1 Base case: a value less than 10 (including 0) returns itself / 0 handled correctly
• +1 Recursive case reduces the number (divides by 10) so the base case is reachable
• +1 Returns the last digit (n % 10) added to the recursive result

Part (b) — 5 points:

• +1 Correct method header: static, returns boolean, one String parameter
• +1 Base case: strings of length 0 or 1 return true
• +1 Compares the first and last characters (e.g. via substring(0, 1) and substring(length - 1), using equals)
• +1 Returns false immediately when the end characters differ
• +1 Recurses on the inner substring (both ends removed) and returns that result for the equal case

Neither part:

• −0 points formally, but any use of a loop forfeits the points for that part per the question's constraint

Model solution.

public static int sumDigits(int n)
{
    if (n < 10)
    {
        return n;
    }
    return n % 10 + sumDigits(n / 10);
}

public static boolean isPalindrome(String s)
{
    if (s.length() <= 1)
    {
        return true;
    }
    if (!s.substring(0, 1).equals(s.substring(s.length() - 1)))
    {
        return false;
    }
    return isPalindrome(s.substring(1, s.length() - 1));
}


## Going deeper: recursive binary search, traced
Lesson 12's binary search returns as recursion in Unit 10 — same halvings, new control structure. The method takes the array plus the current `low`/`high` window:

public static int search(int[] arr, int target, int low, int high) { if (low > high) { return -1; } int mid = (low + high) / 2; if (arr[mid] == target) { return mid; } else if (target < arr[mid]) { return search(arr, target, low, mid - 1); } else { return search(arr, target, mid + 1, high); } }

Trace `search(arr, 38, 0, 9)` on {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}: frame 1 computes mid 4 (value 16) and recurses with (5, 9); frame 2 computes mid 7 (value 56) and recurses with (5, 6); frame 3 computes mid 5 (value 23) and recurses with (6, 6); frame 4 computes mid 6 (value 38) and returns 6 — which each waiting frame returns unchanged on the way up. The base case here is doubled: success (found) or an empty window (`low > high`) — a recursive method may need both, and "what are ALL the ways this stops?" is the first question to ask of any recursive code.

**Bonus question.** How many frames are created in total by the trace above, and what does `search(arr, 40, 0, 9)` return?
- (A) 4 frames; returns 6
- (B) 4 frames; returns −1
- (C) 5 frames; returns −1
- (D) 3 frames; returns −1
- (E) 4 frames; returns 7

**Answer: (B).** The traced search for 38 creates 4 frames: the initial call plus three recursive calls, ending in the frame whose window is (6, 6). The call `search(arr, 40, 0, 9)` returns −1: it follows the same path to the window (6, 6), finds 38 ≠ 40 with 40 larger, and recurses once more into the window (7, 6) — an empty window, where the base case returns −1. Note the asymmetry worth remembering: an unsuccessful search always ends one frame deeper than the corresponding successful one, in the empty-window frame.