Java

Broccoli (Recursion)

10 points

Recursion is a powerful technique in programming that involves solving a problem by dividing the problem into small pieces, and then putting the pieces back together. In recursion, you typically use the 'recursive case' until you've finished dividing the problem into small pieces. At this point, the 'base case' in recursion provides a stopping point. Then you put the small pieces together and generate a solution.

Factorial
A good example of a simple use of recursion is to calculate n!, where n is an integer. You can calculate n! = (n)(n-1)(n-2)...(3)(2)(1), of course. A recursive approach is: 'if n is 1, the value is 1. If n is any number larger than 1, find the factorial by multiplying n by (n-1)!.' The 'if n is 1, the value is 1' part is the 'base case'. The 'multiply n by (n-1)' part is the 'recursive case'.

Let's take 4! as an example. How do you find 4! recursively? Since 4 is larger than 1, we calculate: (4)(3!). How do we find (3!)?. It equals (3)(2!). How do we find (2!)? It equals (2)(1!). How do we find (1!)?. We have arrived at the base case, and we know that 1! equals 1. Working backwards then, 2! = (2)(1) = 2. 3! = (3)(2) = 6. 4! = (4)(6) = 24. So after breaking the problem of finding 4! down into smaller and smaller factorial problems, we put the pieces back together (by multiplying) and find that 4! = 24. Download and run this recursive factorial program to get a clearer sense of how this process works.

Broccoli


Here is a computer-generated image that is supposed to resemble broccoli. This broccoli is the result of applying a simple recursion. The 'recursive case' says: to draw broccoli, first draw a stem. Then, starting at the end of the stem, draw some new broccoli, then rotate left 20° and draw some broccoli, then rotate right 20° and draw a third piece of broccoli. Each of these three pieces of broccoli will then draw some broccoli straight ahead, left 20° and right 20°. (Each time broccoli is drawn, it is only 80% of the size of the 'parent' broccoli.) This recursive process continues, with each broccoli 'parenting' three more broccoli, until the 'base case' is reached. The 'base case' says: when the stem of the broccoli is below a certain length, instead of drawing three more broccoli, draw three buds, and stop. This way you should get a full head of broccoli, topped by buds or flowers, and the process has a way to stop.

You can download below the 5 Java source files you'll need. Begin a new BlueJ project and add all 5 files to the project.

Broccoli.java
In Broccoli.java, in the 'private instance variables' section, declare three variables 'left' 'center' and 'right' of type BroccoliPart. Also declare a variable 'stem' of type AngLine.

The Broccoli constructor takes a starting Location 'startCoords', a length 'size', an angle (measured in radians) 'direction', and the 'canvas'. Inside the constructor, use a call to 'new' to create and draw the object 'stem' of type AngLine (see below). Then set the color of 'stem' to green (like broccoli). Then declare a variable 'destCoords' of type Location, and set it equal to the ending point of 'stem' by calling 'stem.getEnd()'.

Then set up an IF - ELSE statement. If 'size' is greater than 25 (if the recursive case is going to continue), create and draw a new piece of Broccoli called 'center' by making a call to 'new'. 'center' should be identical to its 'parent' except that it is only 80% as long as its 'parent'. 'center' should start to draw where 'stem' left off, at 'destCoords'. Also draw a new piece of Broccoli 'left' which has a direction that is shifted 20° (Math.PI/9.0) to the left. And draw a third new piece of Broccoli 'right' which has a direction that is shifted 20° to the right.

If 'size' is not greater than 25 (if you are handling the base case), you enter the ELSE branch. You've reached the end of the broccoli road, and it is time to draw some buds at the ends of the broccoli spears. The instructions are identical to the instructions in the IF branch, except that instead of drawing Broccoli, here you create and draw objects of type Flower. The lengths are again 80% of the lengths of the 'parent', and the angles (20° left for 'left' and 20° right for 'right') are the same.

Flower.java
In the 'private instance variables' section, declare a variable 'stem' of type AngLine, and a variable 'bud' of type FilledOval.

In the constructor, just as in Broccoli.java, create 'stem', color it green, and find its ending coordinates. Then create and draw 'bud' with a call to 'new FilledOval'. FilledOval has this constructor:
FilledOval(Location origin, double width, double height, DrawingCanvas c)
Then call 'setColor' to make the bud yellow.

Drawing.java
Drawing.java holds the method 'begin' that creates an object of type Broccoli and thereby gets the drawing going. A Broccoli object needs a starting Location, a size and a direction. Declare a variable of type Location and create a Location object with a call to 'new'. Declare a variable of type int and assign it a value; this will be the initial size (in pixels) of the broccoli spears. Declare a variable of type double and assign it a value; this will be the initial direction (in radians) in which the broccoli spears will be drawn. (A good value for this is Math.PI/2.0 or 90°.) Then create a Broccoli object with a call to 'new', sending these three variables, and the ever-present 'canvas' variable, into the Broccoli constructor. The Broccoli object creates new Broccoli objects, which in turn create new Broccoli objects, etc. until finally some Flower objects are created at the end.

AngLine.java
AngLine.java is complete. An AngLine is a type of line, where the user supplies a starting point, a length and an angle that the line forms with the horizontal.

BroccoliPart.java
This file defines an 'interface' that the Broccoli and Flower objects implement. This file is complete.

 

Starting Point

You can download Broccoli.java, Flower.java, Drawing.java, BroccoliPart.java and AngLine.java to use as a starting point in writing your program.

Note: This example is taken directly from Java: An eventful approach by Bruce, Danyluk, and Murtagh.