AP® Computer Science A · Unit 4 · Topic 4.17
Recursive Traversal of Strings and Arrays
A recursive traversal processes one element of a string or array, then calls itself on the rest, until an empty or single-element piece stops the recursion.
A string or array is just a sequence, and recursion can walk that sequence the same way a loop can. The usual pattern: handle the first character (or element), then call the method again on everything after it. Each call gets a smaller input than the one before, because the "rest" is always one shorter. That shrinking is what makes the recursion end — eventually the input is empty, or has one element left, and that becomes the base case that returns without calling itself again.
Trace reverse("CODE"): it calls reverse("ODE") and appends C to the end of that result. reverse("ODE") calls reverse("DE") and appends O. This keeps unwinding until reverse("") returns the empty string, and the appends happen in reverse order on the way back up, building "EDOC". For counting, countA("BANANA") checks if the first letter is A, then adds the result of countA on the rest; the count only grows on the way back up once the base case (empty string) returns 0.
Peeling off one element per call means a string of length n takes n calls to shrink to empty, plus one more for the empty base case: n+1 calls total. That is a lot of levels for a large array, which is why some recursive algorithms split the array in half instead — each call hands off two halves rather than one smaller piece. That cuts the recursion depth from roughly n down to roughly log2(n), the same idea that makes merge sort and binary search fast, and it sets up the jump from simple traversal to divide-and-conquer recursion.
Key terms
- base case
- The smallest input (often an empty string or array) where the method returns directly without recursing.
- recursive case
- The part of the method that processes one element and calls itself on the smaller remaining piece.
- recursion depth
- The number of nested calls made before reaching the base case.
- divide-and-conquer
- A recursive strategy that splits the input into smaller pieces, often halves, rather than removing one element at a time.
Watch it explained
- How it worksHow does taking the first character and recursing on the rest cover the whole string?
- Worked exampleTrace a recursive method that reverses the string CODE one character at a time.
- Worked exampleFind what a recursive method counting the letter A in BANANA returns at each level.
- Going furtherWhat changes when the recursion splits the array in half instead of peeling one off?
Check yourself
End of topic.