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

The code in the else part will deal with lines that have more than zero stars on
them. Your instinct will probably be to fill in the else part with the for loop shown
earlier, but you'll have to fight the instinct to solve the entire problem that way. To
solve this second part of the problem, it is important to think about how you can do
just a small amount of work that will get you closer to the solution. If the number of
stars is greater than zero, you know you have to print at least one star, so you can add
that action to the code:
public static void writeStars(int n) {
if (n == 0) {
System.out.println();
} else {
System.out.print("*");
// what is left to do?
...
}
}
At this point in the process you have to make a leap of faith: You have to believe
that recursion actually works. Once you've printed a single star, what's left to do?
The answer is that you want to write (n - 1) more stars, along with a println . In
other words, after writing one star, the task that remains is to write a line of (n - 1)
stars. You may think, “If only I had a method that would produce a line of (n - 1)
stars, I could call that method.” But you do have such a method—the method you're
writing. So, after your method writes a single star, you can call the writeStars
method itself to complete the line of output:
public static void writeStars(int n) {
if (n == 0) {
System.out.println();
} else {
System.out.print("*");
writeStars(n - 1);
}
}
Many novices complain that this seems like cheating. You're supposed to be writ-
ing the method called writeStars , so how can you call writeStars from inside
writeStars ? Welcome to the world of recursion.
In the earlier example, we talked about people standing in a line and solving a
problem together. To understand a recursive method like writeStar s , it is useful to
imagine that each method invocation is like a person in the line. The key insight is
that there isn't just one person who can do the writeStars task; there's an entire
army of people, each of whom can do the task.