Problem Solving Using Recursion

If you think recursively, you can solve many problems using recursion. The preceding sections presented two classic recursion examples. All recursive methods have the following characteristics:

• The method is implemented using an if-else or a switch statement that leads to different cases.
• One or more base cases (the simplest case) are used to stop recursion.
• Every recursive call reduces the original problem, bringing it increasingly closer to a base case until it becomes that case.

In general, to solve a problem using recursion, you break it into subproblems. Each subproblem is the same as the original problem but smaller in size. You can apply the same approach to each subproblem to solve it recursively.

Recursion is everywhere. It is fun to think recursively. Consider drinking coffee. You may describe the procedure recursively as follows:

public static void drinkCoffee(Cup cup) {
if (!cup.isEmpty()) {
cup.takeOneSip(); // Take one sip
drinkCoffee(cup);
}
}

Assume cup is an object for a cup of coffee with the instance methods isEmpty() and takeOneSip(). You can break the problem into two subproblems: one is to drink one sip of coffee and the other is to drink the rest of the coffee in the cup. The second problem is the same as the original problem but smaller in size. The base case for the problem is when the cup is empty.

Consider the problem of printing a message n times. You can break the problem into two subproblems: one is to print the message one time and the other is to print it n - 1 times. The second problem is the same as the original problem but it is smaller in size. The base case for the problem is n == 0. You can solve this problem using recursion as follows:

public static void nPrintln(String message, int times) {
if (times >= 1) {
System.out.println(message);
nPrintln(message, times - 1);
} // The base case is times == 0
}

Note that the fib method in the preceding section returns a value to its caller, but the drinkCoffee and nPrintln methods are void and they do not return a value.

If you think recursively, you can use recursion to solve many of the problems presented in earlier chapters of this book. Consider the palindrome problem in Palindrome.java. Recall that a string is a palindrome if it reads the same from the left and from the right. For example, “mom” and “dad” are palindromes, but “uncle” and “aunt” are not. The problem of checking whether a string is a palindrome can be divided into two subproblems:

• Check whether the first character and the last character of the string are equal.
• Ignore the two end characters and check whether the rest of the substring is a palindrome.

The second subproblem is the same as the original problem but smaller in size. There are two base cases: (1) the two end characters are not the same, and (2) the string size is 0 or 1. In case 1, the string is not a palindrome; in case 2, the string is a palindrome. The recursive method for this problem can be implemented as shown in the code below.

The substring method in line 8 creates a new string that is the same as the original string except without the first and last characters. Checking whether a string is a palindrome is equivalent to checking whether the substring is a palindrome if the two end characters in the
original string are the same.