Recursion - Building Java Programs: A Back to Basics Approach - page 721

Let's think about what happens when you call the method and request a line of
three stars:
writeStars(3);
Imagine that you're calling up the first person from the writeStars army and
saying, “I want a line of three stars.” That person looks at the code in the method and
sees that the way to write a line of three stars is to execute the following lines:
System.out.print("*");
writeStars(2);
In other words, the first member of the army writes a star and calls up the next
member of the army to write a line of two stars, and so on down the line. Just as in
the earlier example you had a series of people figuring out their places in line, now
you have a series of people each printing one star and then calling on someone else to
write the rest of the line. In the line example, you eventually reached the person at the
front of the line. In this case, you eventually reach a request to write a line of zero
stars, which leads you into the if branch rather than the else branch. At this point,
you complete the task with a simple println .
Here is a trace of the calls that would be made to print the line:
writeStars(3); // n > 0, execute else
System.out.print("*");
writeStars(2); // n > 0, execute else
System.out.print("*");
writeStars(1); // n > 0, execute else
System.out.print("*");
writeStars(0); // n == 0, execute if
System.out.println();
A total of four different calls are made on the method. Continuing the analogy,
you could say that four members of the army are called up to solve the task together.
Each one solves a star-writing task, but the tasks are slightly different (three stars,
two stars, one star, zero stars). This is similar to the example in which the various
people standing in line were all answering the same question but were solving
slightly different problems because their positions in line were different.
Structure of Recursive Solutions
Writing recursive solutions requires you to make a certain leap of faith, but there is noth-
ing magical about recursion. Let's look a bit more closely at the structure of a recursive
solution. The following method is not a solution to the task of writing a line of n stars:
// does not work
public static void writeStars(int n) {
writeStars(n);
}