Java Arena
Start learning
Step 3 of 6

Recursion on strings and arrays

A string is its first character followed by a shorter string, and that view makes many string problems recursive. text.charAt(0) is the first character, and text.substring(1) (module 16) is the rest, one character shorter. The base case is usually the empty string, which has no first character.

Counting a character

A typesetter wants to know how many times a letter appears in a headline:

public class Main {
    public static void main(String[] args) {
        System.out.println(count("banana bread", 'a'));
        System.out.println(count("", 'a'));
    }

    public static int count(String text, char letter) {
        if (text.isEmpty()) {
            return 0;
        }
        int rest = count(text.substring(1), letter);
        if (text.charAt(0) == letter) {
            return rest + 1;
        }
        return rest;
    }
}
Output
4
0

Each call looks at one character and leaves the rest to the recursive call. The empty string has no a in it. Every call makes the string one character shorter, so the calls reach the empty string.

Arrays: pass an index

For arrays, the usual way is to pass an index instead of copying the rest (a copy on every call would take time and memory): the method gets the array and an index, the place where "the rest" starts, and the recursive call moves the index one place along. The base case is an index at the end of the array, where the rest is empty:

public class Main {
    public static void main(String[] args) {
        int[] temperatures = {4, -2, 7, -5, 0};
        System.out.println(countBelowZero(temperatures, 0));
        System.out.println(countBelowZero(temperatures, 3));
    }

    public static int countBelowZero(int[] values, int start) {
        if (start == values.length) {
            return 0;
        }
        int rest = countBelowZero(values, start + 1);
        if (values[start] < 0) {
            return rest + 1;
        }
        return rest;
    }
}
Output
2
1

countBelowZero(temperatures, 0) counts the whole array; countBelowZero(temperatures, 3) counts only from index 3 on.

Building a string

A recursive method can also return a string it builds from the smaller call's string. This one spaces out a word's letters for a sign:

public class Main {
    public static void main(String[] args) {
        System.out.println(spaced("OPEN"));
    }

    public static String spaced(String word) {
        if (word.length() <= 1) {
            return word;
        }
        return word.charAt(0) + " " + spaced(word.substring(1));
    }
}
Output
O P E N

Here the base case is a word of at most one letter, which needs no spaces; the empty string is covered by it too.

Your task

Challenge 1 of 3

An ambulance has its name painted backwards on its hood, so that drivers ahead read it the right way around in their mirrors. Write the method reverse(String text), which returns the text backwards, with recursion and no loop: the reverse of a text is the reverse of its rest (text.substring(1)) followed by its first character. Don't use StringBuilder. The check runs:

System.out.println(reverse("AMBULANCE"));
System.out.println(reverse("stressed"));

and expects:

ECNALUBMA
desserts

Challenge 2

A word game gives bonus points for palindromes, words that read the same backwards, such as kayak or noon. Write the method isPalindrome(String word) with recursion and no loop: a word is a palindrome if its first and last characters are the same and the part between them is a palindrome. A word of 0 or 1 characters is always a palindrome. word.substring(1, word.length() - 1) is the part between the ends: isPalindrome itself calls itself on it, not through a helper method. Don't reverse the word: compare its ends. The check runs:

System.out.println(isPalindrome("kayak"));
System.out.println(isPalindrome("noon"));
System.out.println(isPalindrome("kayaks"));

and expects:

true
true
false

Challenge 3

A hiking trail is split into stages, and an array holds each stage's length in kilometers. Write the method kilometersFrom(int[] stages, int start), which returns the total length of the stages from index start to the end of the array, with recursion and no loop: the stage at start plus the kilometers from start + 1. When start is the array's length, no stages are left, and the total is 0. The check runs:

int[] stages = {12, 8, 15, 6, 9};
System.out.println(kilometersFrom(stages, 0));
System.out.println(kilometersFrom(stages, 3));

and expects:

50
15
Previous: Base case and return value Next: When recursion goes wrong