Recursion on Strings

Part of: Recursion

Strings Are Recursive Too A String can be viewed as a first character plus the rest of the string. That self-similar structure makes strings perfect for recursion. The key tools are: - s.length(), number of characters; length() == 0 is the natural base case. - s.substring(0, 1), the first character as a one-character string. - s.substring(1), everything except the first character (the smaller problem). Reversing a String To reverse, put the first character last : reverse the rest, then append the first character. Trace reverse("cat"): - reverse("cat") = reverse("at") + 'c' - reverse("at") = reverse("t") + 'a' - reverse("t") = "t" (base case) - Build up: "t" + "a" = "ta", then "ta" + "c" = "tac" Counting Occurrences The same pattern counts a target character: check the first char, then recurse on the rest. Why This Pattern Works Each call handles one character and delegates the remaining n-1 characters to a recursive call. Because the string shrinks by one each time, it always reaches the empty (or single-char) base case. A Note on Performance substring(1) creates a new String each call, so string recursion is not the fastest approach, but it is wonderfully clear and a common AP pat

Challenge: Recursive String Reverse