Java Reference
In-Depth Information
Recursion is everywhere. It is fun to
think recursively
. Consider drinking coffee. You may
describe the procedure recursively as follows:
think recursively
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
recursive call
}
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 topic. Consider the palindrome problem in Listing 9.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 of checking
whether a string is a palindrome can be divided into two subproblems:
think recursively
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 Listing 20.3.
L
ISTING
20.3
RecursivePalindromeUsingSubstring.java
1
public class
RecursivePalindromeUsingSubstring {
2
3
public static boolean
isPalindrome(String s) {
method header
base case
if
(s.length() <=
1
)
// Base case
4
return true
;
5
else if
(s.charAt(
0
) != s.charAt(s.length() -
1
))
// Base case
base case
6
return false;
7
else
8
return
isPalindrome(s.substring(
1
, s.length() -
1
))
;
recursive call
9 }
10
11
public static void
main(String[] args) {
