C H A P T E R 14
Recursion
Recursion has an undeserved reputation for being hard to do and hard to control. For various reasons, many developers have trouble using recursion as one of their programming tools. I suspect the difficulty stems from two predicaments: having to give up control so that the recursive classes or methods can do their work and not being able to “see” the recursion work (though the debugger can solve the latter problem). Also, the first try at recursion usually ends poorly, resulting in an infinite loop (that is, a process that never stops), and software developers are trained to be very wary of infinite loops. All of these problems can be overcome with surprisingly easy-to-use and easy-to-understand techniques, which I'll address later in the chapter.
Before I dive into how to work with recursions, though, let's take a close look at what recursion is.
Recursion is Natural
The main reason I am surprised that so many developers distrust recursion is that recursion is a feature of human language. We all use it every day when we talk to one another. English utilizes recursion in a number of situations. One of the rules (from the field within Linguistics called Transformational Grammar, which I studied in college) of the English language is that one sentence can be embedded into another sentence. I won't dive into the sentence diagrams to prove it, but I'll give you an example in the form of a children's rhyme from long ago:
This is the house that Jack built.
This is the malt that lay in the house that Jack built.
This is the rat that ate the malt that lay in the house that Jack built.
As you can see, kids can keep going for as long as they can think of things to add (or until their parents yell at them to stop). English supports recursion in other situations as well. For instance, another rule in English is that we can stack up prepositional phrases as deep as we like, thus:
The princess lives in the castle.
The princess lives in the castle on the hill.
The princess lives in the castle on the hill by the road.
The princess lives in the castle on the hill by the road in the swamp.
Again, we can keep doing this for as long as it amuses us to do so.
Recursion is Common
You encounter instances of recursion every day and never think twice about them. The only notable feature about the following sentence is that it involves a princess and a castle: “The princess lives in the castle on the hill.” How many times have you said something similar to “I live in a red house on Mulberry Street"?
Recursion is common in the field of computer science, too. A number of languages use recursion as their main idiom for processing data. The most famous recursive programming language is probably Lisp. Lisp stands for “List processing” and treats everything as a list. The usual method of processing in Lisp is to read the first item of a list (reducing the original list), process it, read the first value of the remaining list, process it, and so on until the list is empty. XSLT (a grandchild of Lisp through another language called DSSSL) works in a similar way, processing XML nodes until it runs out of nodes.
All the programming languages with which I am familiar also have one mechanism or another for supporting recursion. Recursion may be easier or harder to achieve depending on the language, but in my experience, it's always possible.
Know Your Stop Condition
Now that you know what recursion is and have discovered that recursion is actually all around us, let's look at how to make it work. We'll start with a problem that many software developers fear: the infinite loop.
Recursion usually generates an infinite loop because the developer fails to check for a stop condition or for the correct stop condition. The trouble is that the stop condition always depends on what you're doing. If you're processing a factorial, your stop condition is the argument to the factorial symbol. Therefore, if you're calculating 10! (10 factorial), you stop when you get to 10. Similarly, if you're processing an XML file, the stop condition is the last child node.
The other problem is that those conditions are not similar enough for many developers. People like to be sure of things: they don't want to have to figure out the stop condition every time. This issue often persuades developers to avoid recursion, even when recursion is the best way to solve a problem.
Let's look at one of the examples I just mentioned, calculating a factorial:
Listing 14-1. Calculating a Factorial
package com.bryantcs.examples.factorial;
public class Factorial {
int calculate(int number) {
if (number < 0) {
throw new IllegalArgumentException("integer must be 0+");
}
if( number == 0) { return 1;
} else {
return number * calculate (number - 1);
}
}
public static void main(String[] args) {
Factorial factorial = new Factorial();
System.out.println(factorial.calculate(4));
}
}
In the calculate method, after checking for valid input, check for the stop condition, which is the argument “1". (Note the recursion in the preceding sentence: “In … after … .” It really is common.)
When to Avoid Recursion
The biggest problem with recursion is that each pass through the method puts another object in the call stack. If you have a lot of recursion to do, you can overflow the stack. As the following image shows, there are four instances of the calculate method on the stack when the factorial of four (4!) is calculated.
Figure 14-1. calculate Methods on the Call Stack
If I had calculated the factorial of ten (10!), I would have had ten instances of the calculate method on the stack. To avoid this problem, I can rewrite the method to use a loop instead, thus:
Listing 14-2. Converting Recursion to a Loop
package com.bryantcs.examples.factorial;
public class Factorial {
int calculate(int number) {
if (number < 0) {
throw new IllegalArgumentException("integer must be 0+");
}
if( number == 0 || number == 1)
return 1;
else {
int total = 1;
for (int i = 1; i < number + 1; i++) {
total *= i;
}
return total;
}
}
public static void main(String[] args) {
Factorial factorial = new Factorial();
System.out.println(factorial.calculate(4));
}
}
Since it contains no calls to itself, the calculate method appears on the stack only once. Therefore, the lesson here is that any time you can easily replace recursion with a loop, you should do so.
When to Use Recursion
If you should replace recursion with loops whenever you can easily do so, when should you use recursion? The simple (but not helpful) answer is: when it's useful to do so. But when is that? Essentially, you should use recursion when you can't know (or can't be sure of) the number of times you need to process something. Processing an XML file is a good illustration of this problem. When you write a program to process an XML file, you can't be sure how many nodes will be in the given XML file. It is possible to solve these kinds of problems with while loops, but in this case, recursion is easier both to code and to understand.
In addition to parsing, other problems are simply easier to code with recursion. If you can significantly reduce the size of your code or gain an algorithm that is easier to understand, you should consider recursion, even in cases where the problem can be solved with loops. What sorts of things are solved with recursive algorithms? Let's look at some common problems that utilize recursion (and I'll code some of the more interesting ones later in the chapter):
- Repetitive mathematical functions, such as a factorial, a sum of digits, the Fibonacci sequence, and many others
- Any problem in which the depth of processing is hard to predict (e.g., processing files and other data streams)
- Certain kinds of searches (such as finding all the instances of a substring within a string and finding all the instances of a particular data element in a tree structure)
- Fractal images (which I'll focus on later in the chapter).
Without further ado, I'll get to the fun stuff: coding solutions to problems that are a good fit for recursion.
Calculating the Fibonacci Sequence
The Fibonacci sequence (named after Italian mathematician Leonardo Bigollo, also known as Fibonacci) is a sequence of numbers consisting of 0, 1, and numbers that are each the sum of the previous two. Thus, the Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and so on for as long as one cares to do the math.
While the Fibonacci sequence can be calculated with a loop, it's commonly used as an example when folks discuss recursion. I'll stir up my own code for it:
Listing 14-3. Recursively Calculating the Fibonacci Sequence
package com.bryantcs.examples.fibonacci;
public class Fibonacci {
private int calculate(int length) {
if (length < 0) {
throw new IllegalArgumentException("Input must be 0 or greater");
}
if (length <= 1) {
return length;
} else {
return calculate(length - 1) + calculate(length - 2);
}
}
public static void main(String[] args) {
Fibonacci fibonacci = new Fibonacci();
for (int i = 0; i < 10; i++){
System.out.println(fibonacci.calculate(i));
}
}
}
Note Fibonacci numbers turn up in all kinds of interesting places. They are closely linked to the golden ratio (important in the history of art and architecture), appear in the ratios of a number of objects in nature, and have been used to determine when to buy stocks. While they are well beyond the scope of this book, the origin and uses of the Fibonacci sequence are interesting subjects in their own right.
Calculating Fractals
Fractal images involve using the output of one calculation as the input to a subsequent calculation–a perfect task for recursion. I'll start with my personal favorite.
Drawing a Sierpinski Triangle
A Sierpinski triangle (named after Polish mathematician Waclaw Sierpinski) is a triangle consisting of other triangles. Each smaller triangle can itself consist of other triangles. Thus, you can have triangles within triangles within triangles to any depth you like. (Note the recursion within the preceding sentence; just talking about recursion requires recursion.)
Here's a pair of classes that draw a Sierpinski triangle to a depth of 7 (a number I picked because I liked the resulting output). As usual, I've created a program class that uses another class to do the drawing.
Here's the program class:
Listing 14-4. SierpinskiTriangle.java
package com.bryantcs.examples.fractals;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JFrame;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;
public class SierpinskiTriangle implements ActionListener {
private SierpinskiTrianglePanel
sierpinskiTrianglePanel = new SierpinskiTrianglePanel();
private JFrame frame = new JFrame("Sierpinski Triangle");
private void addMenu(JFrame frame) {
JMenu file = new JMenu("File");
file.setMnemonic('F'),
JMenuItem exitItem = new JMenuItem("Exit");
exitItem.setMnemonic('x'),
exitItem.addActionListener(this);
file.add(exitItem);
JMenuItem redrawItem = new JMenuItem("Repaint");
redrawItem.setMnemonic('r'),
redrawItem.addActionListener(this);
file.add(redrawItem);
JMenuBar menuBar = new JMenuBar();
menuBar.add(file);
frame.setJMenuBar(menuBar);
}
private void createAndShowGUI() {
addMenu(frame);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
sierpinskiTrianglePanel.setPreferredSize(new Dimension(400, 400));
sierpinskiTrianglePanel.setBackground(Color.WHITE);
frame.getContentPane().add(sierpinskiTrianglePanel);
frame.pack();
frame.setVisible(true);
}
public static void main(String[] args) {
SierpinskiTriangle sierpinskiTriangle = new SierpinskiTriangle();
sierpinskiTriangle.createAndShowGUI();
}
public void actionPerformed(ActionEvent e) {
if (e.getActionCommand() != null) {
if (e.getActionCommand().equals("Exit")) {
System.exit(0);
}
if (e.getActionCommand().equals("Repaint")) {
sierpinskiTrianglePanel.repaint();
}
}
}
}
By now, you're accustomed to how this kind of program class works: it handles the input from the user, sets up the window that holds your content, and manages the class that does the more interesting work.
Here's the class that does the drawing:
Listing 14-5. SierpinskiTrianglePanel.java
package com.bryantcs.examples.fractals;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.geom.Point2D;
import javax.swing.JPanel;
public class SierpinskiTrianglePanel extends JPanel {
private static final long serialVersionUID = 1L;
int maxLevel = 7;
private void drawTriangle(int level, Graphics g, Point2D.Double point1,
Point2D.Double point2, Point2D.Double point3) {
if (level < maxLevel) {
// Work our way down through the levels
Point2D.Double midPoint1 = getMiddlePoint(point1, point2);
Point2D.Double midPoint2 = getMiddlePoint(point2, point3);
Point2D.Double midPoint3 = getMiddlePoint(point1, point3);
g.setColor(new Color((int)(Math.random() * 0xFFFFFF)));
drawTriangle(level + 1, g, point1, midPoint1, midPoint3);
drawTriangle(level + 1, g, midPoint1, point2, midPoint2);
drawTriangle(level + 1, g, midPoint3, midPoint2, point3);
} else {
// At the bottom level, draw the actual triangles
// (which are parts of the larger triangles)
int[] xPoints = {
new Double(point1.getX()).intValue(),
new Double(point2.getX()).intValue(),
new Double(point3.getX()).intValue()
};
int[] yPoints = {
new Double(point1.getY()).intValue(),
new Double(point2.getY()).intValue(),
new Double(point3.getY()).intValue()
};
g.fillPolygon(xPoints, yPoints, 3);
}
}
private Point2D.Double getMiddlePoint(Point2D.Double point1,
Point2D.Double point2) {
double newX = (point1.getX() + point2.getX()) / 2;
double newY = (point1.getY() + point2.getY()) / 2;
return new Point2D.Double(newX, newY);
}
public void paint (Graphics g) {
super.paintComponent(g);
int height = this.getHeight();
int width = this.getWidth();
// Here's one way to get the height of an equilateral triangle Double doubleHeight
= Math.sqrt(height * height - (width / 2) * (width / 2)); // 0 on the Y axis is at the bottom, so this seems upside-down
Point2D.Double lowerLeft = new Point2D.Double(0, doubleHeight);
Point2D.Double lowerRight = new Point2D.Double(width, doubleHeight);
Point2D.Double top = new Point2D.Double(width / 2, 0);
drawTriangle(1, g, lowerLeft, lowerRight, top);
}
}
The SierpinskiTriangleJava class really starts in the paint method, where it calculates the corners of the outer triangle and passes those values to the drawTriangle method. Then the drawTriangle method calculates a series of triangles within triangles, down to the depth specified in the maxLevel variable that is stated at the top of the class. You can change the depth by changing that value, and a good exercise is to add setting that value to the user interface.
The actual drawing happens only after the class reaches the maximum level. At that point, there are 729 (3 to the 6th power) triangles that draw themselves and 364 triangles that contain other triangles. Three hundred and sixty-four is not a power of 3, so how was that number obtained by calculating six levels of depth? The following table shows the progression:
As you can see, the inclusion of the outer triangle throws off the numbers a bit so that the total is never a power of three. However, the difference between any two steps is a power of three. This kind of pattern appears whenever a single item contains other items that scale in a regular fashion.
Within the drawTriangle method, I calculated the midpoints of the current triangle and created three new triangles based on those points. That's the essence of the Sierpinski algorithm. The remaining code in the method does the work of drawing and of making sure I don't miss the stop condition.
Note The code for drawTriangle could be made simpler by starting at the outermost layer and counting backwards. However, I wanted to have a maxLevel value to make setting the depth as easy as possible. I also used Point2D rather than Point to obtain a greater level of accuracy (and thus prevent small mismatches in the positions of the triangles within the window).
Finally, here's the result of my SierpinskiTriangle program:
Figure 14-2. Output from the SierpinskiTriangle Program
Drawing a Fractal Tree
One of my other favorite fractals is the fractal tree because it really does resemble a tree (at first glance, anyway). Here's the program class:
Listing 14-6. FractalTree.java
package com.bryantcs.examples.fractals;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JFrame;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;
public class FractalTree implements ActionListener {
private FractalTreePanel
fractalTreePanel = new FractalTreePanel();
private JFrame frame = new JFrame("Fractal Tree");
private void addMenu(JFrame frame) {
JMenu file = new JMenu("File");
file.setMnemonic('F'),
JMenuItem exitItem = new JMenuItem("Exit");
exitItem.setMnemonic('x'),
exitItem.addActionListener(this);
file.add(exitItem);
JMenuItem redrawItem = new JMenuItem("Repaint");
redrawItem.setMnemonic('r'),
redrawItem.addActionListener(this);
file.add(redrawItem);
JMenuBar menuBar = new JMenuBar();
menuBar.add(file);
frame.setJMenuBar(menuBar);
}
private void createAndShowGUI() {
addMenu(frame);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
fractalTreePanel.setPreferredSize(new Dimension(600, 450));
fractalTreePanel.setBackground(Color.WHITE);
frame.getContentPane().add(fractalTreePanel);
frame.pack();
frame.setVisible(true);
}
public static void main(String[] args) {
FractalTree fractalTree = new FractalTree();
fractalTree.createAndShowGUI();
}
public void actionPerformed(ActionEvent e) {
if (e.getActionCommand() != null) {
if (e.getActionCommand().equals("Exit")) {
System.exit(0);
}
if (e.getActionCommand().equals("Repaint")) {
fractalTreePanel.repaint();
}
}
}
}
As I'm sure you know by now, the FractalTree class merely manages the user interface and provides a place for another class to do the drawing. So let's move on to the class that does the fun stuff: drawing our fractal trees.
Listing 14-7. FractalTreePanel.java
package com.bryantcs.examples.fractals;
import java.awt.Color;
import java.awt.Graphics;
import java.util.Random;
import javax.swing.JPanel;
public class FractalTreePanel extends JPanel {
private static final long serialVersionUID = 1L;
private final static double RADIANS = Math.PI / 180.0;
Random rand;
public FractalTreePanel() {
rand = new Random();
}
private void drawSegment(Graphics g, int x1, int y1, double angle, int depth) {
if (depth == 0) return; // the stop condition
int xAngleOffset = new Double(Math.cos(angle * RADIANS) * depth * 10.0).intValue();
int yAngleOffset =
new Double(Math.sin(angle * RADIANS) * depth * 10.0).intValue();
int x2 = x1 + xAngleOffset;
int y2 = y1 + yAngleOffset;
int colorValue = 256 - ((depth - 1) * 32) - 1;
if (colorValue < 0) {
colorValue = 0;
}
g.setColor(new Color(0, colorValue, 0));
g.drawLine(x1, y1, x2, y2);
int randFactor = rand.nextInt(20) + 10; // a value between 10 and 30
drawSegment(g, x2, y2, angle - randFactor, depth - 1);
randFactor = rand.nextInt(20) + 10; // a value between 10 and 30
drawSegment(g, x2, y2, angle + randFactor, depth - 1);
}
public void paint(Graphics g) {
super.paintComponent(g);
drawSegment(g, getWidth() / 2, getHeight(), -90, 9);
}
}
The algorithm for a fractal tree is quite simple: draw a line; from the end point of that line, draw two more lines; and so on. I can do that by using fixed values, but I will generate trees that are more realistic by adding some randomness. To that end, I also changed the color for each part of the tree, using lighter shades of green towards the top.
In my case, I configured the algorithm from the maximum depth down to 0. For this kind of algorithm, doing so results in less code (and so should be easier to understand). Since I liked the look of the tree with a depth of 9, I didn't set the depth value out separately like I did in the SierpinskiTrianglePanel class. Another interesting feature of this class is that the initial angle is -90. If it were 0, the tree would grow sideways to the right. This would happen because an angle of 0 draws a line that lies on the X-axis. Thus, to make the lines go up the Y-axis, I had to rotate 90 degrees to the left (i.e., -90). An angle of 90 would produce a tree that grew downward (which could be a handy way to model roots).
The next page shows one result (each result is a bit different) of the FractalTree program.
Figure 14-3. Output from the FractalTree Program
Summary
In this chapter, I explained the unusual but sometimes useful idea of working with items that refer to themselves, known as recursion. In particular, you learned that:
- Recursion occurs in human languages.
- Recursion happens all the time (but we often don't notice it).
- Recursive algorithms need stop conditions.
- It's sometimes a good idea to avoid recursion.
- Conversely, recursion is sometimes the best answer to a problem.
- Recursion can be an elegant solution to some problems, such as that of generating the Fibonacci sequence.
- Recursion is the underlying algorithm in making fractals.
I hope you enjoyed this chapter. It was one of my favorites to write, and I enjoyed creating sample code for it. In fact, I played with many variations of the code, just for fun. You should do the same. In particular, regarding the Sierpinski triangle program, try changing colors at every other depth or every third depth value rather than at every depth value (hint: use the modulus operator). Then, play with the values that control the appearance of the fractal tree. In particular, play with different numbers as inputs to the randInt method. Also, rotate the tree and fiddle with the colors to create roots instead of the branches of a tree.
I leave you with two challenges that will help you grow as a programmer. First, create a Sierpinski gasket (a square of squares rather than a triangle of triangles). Second, create a Mandelbrot or Julia fractal. I nearly included sample code for a Julia fractal (one of my favorites), but I thought it would be a great exercise for you, now that you know the basics of recursion in Java. You'll need to do a bit of research to find the algorithms and math behind the Sierpinski gasket and the Mandelbrot and Julia fractals, but discovering algorithms and formulae is part of the job when you develop software. I'm sure you'll get used to performing this kind of research.