Java Reference
In-Depth Information
Some problems involve multiple base cases and some problems involve multiple
recursive cases, but there will always be at least one of each case in a correct recur-
sive solution. If you are missing either, you run into trouble. Without the ability to
step down from one rung to the one below, you'd be stuck at the top of the ladder.
Without the ability to recognize when you reach the ground, you'd keep trying to step
down onto another rung even when there were no rungs left in the ladder.
Keep in mind that your code can have infinite recursion even if it has a proper
recursive case. Consider, for example, this version of writeStars :
// does not work
public static void writeStars(int n) {
System.out.print("*");
writeStars(n - 1);
}
This version correctly reduces from the case of n to the case of n-1 , but it has
no base case. As a result, it goes on infinitely. Instead of stopping when it reaches the
task of writing zero stars, it instead recursively tries to write
1 stars, then
2 stars,
then -3 stars, and so on.
Because recursive solutions include some combination of base cases and recursive
cases, you will find that they are often written with if/else statements, nested if
statements, or some minor variation thereof. You will also find that recursive pro-
gramming generally involves a case analysis, in which you categorize the possible
forms the problem might take into different cases and write a solution for each case.
12.2 A Better Example of Recursion
Solving the writeStars task with recursion may have been an interesting exercise,
but it isn't a very compelling example. Let's look in detail at a problem in which
recursion simplifies the work to be done.
Suppose you have a Scanner that is tied to an external input file and you want to
print the lines of the file in reverse order. For example, the file might contain the fol-
lowing four lines of text:
this
is
fun
no?
Printing these lines in reverse order would produce this output:
no?
fun
is
this
 
Search WWH ::




Custom Search