21.8. Avoiding Unsafe Raw Types

[Page 640 ( continued )]

19.4. Problem Solving 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. If a subproblem resembles the original problem, you can apply the same approach to solve the subproblem recursively. This subproblem is almost the same as the original problem in nature but with a smaller size .

Let us consider the simple problem of printing a message for n times. You can break the problem into two subproblems: one is to print the message one time and the other is to print the message n - 1 times. The second problem is the same as the original problem with a smaller 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 n == 0  } 

---

[Page 641]

Note that the fib method in the preceding example returns a value to its caller, but the nPrintln method is void and does not return a value to its caller.

Many of the problems presented in the early chapters can be solved using recursion if you think recursively . Consider the palindrome problem in Listing 7.1. 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 to check 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 with a smaller size. There are two base cases: (1) the two end characters are not same; (2) the string size is or 1 . In case 1, the string is not a palindrome; and in case 2, the string is a palindrome. The recursive method for this problem can be implemented in Listing 19.3.

Listing 19.3. Recursive Palindrome Method

 1   public static boolean   isPalindrome(String s) {  2   if   (  s.length() <=   1    )  // Base case  3   return true   ;  4   else if   (  s.charAt(     ) != s.charAt(s.length() -   1   )  )  // Base case  5   return false   ;  6   else   7    return   isPalindrome(s.substring(1, s.length() -   1   ));  8 } 

The substring method in line 7 creates a new string that is the same as the original string except without the first and last characters in the original string. 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.