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

triangles. In other words, the level 2 figure is composed of three level 1 figures.
Similarly, the level 3 figure is composed of three level 2 figures, each of which in
turn is composed of three level 1 figures. In general, if we are asked to draw a level n
figure, we do so by drawing three level (n - 1) figures.
We can turn these observations into code to complete the recursive method:
public static void drawFigure(int level, Graphics g,
Point p1, Point p2, Point p3) {
if (level == 1) {
// base case: simple triangle
Polygon p = new Polygon();
p.addPoint(p1.x, p1.y);
p.addPoint(p2.x, p2.y);
p.addPoint(p3.x, p3.y);
g.fillPolygon(p);
} else {
// recursive case, split into 3 triangles
Point p4 = midpoint(p1, p2);
Point p5 = midpoint(p2, p3);
Point p6 = midpoint(p1, p3);
// recurse on 3 triangular areas
drawFigure(level - 1, g, p1, p4, p6);
drawFigure(level - 1, g, p4, p2, p5);
drawFigure(level - 1, g, p6, p5, p3);
}
}
There is a limit to the number of levels down that we can go. The DrawingPanel
has a finite resolution, so at some point we won't be able to subdivide our triangles
any further. Also bear in mind that at each new level the number of triangles that we
draw triples, which means that the number of triangles increases exponentially with
the level.
The complete program is available from http://www.buildingjavaprograms.com.
Remember that you need to also download DrawingPanel.java to execute the
program.
12.5 Case Study: Prefix Evaluator
In this section, we will explore the use of recursion to evaluate complex numeric
expressions. First we will examine the different conventions for specifying numeric
expressions and then we will see how recursion makes it relatively easy to implement
one of the standard conventions.