how to draw a tree recursively in java

Note: This lab should exist done in partners.

Note: This lab is adapted from the Beauty and Joy of Computing (BJC) curriculum.

Goals

• Learn how to manipulate the coordinate organization using interpret() and rotate().
• Understand the techniques to solving problem recursively.
• Imagine how the reckoner follows the instructions in a recursive program.

Recursive Tree

Our goal is to draw a tree that looks something like this:

But for the sake of simplicity and to better illustrate the recursion, we'll showtime with a simpler version like the one shown below on the left. The key to understanding this technique is to notice the tree is a fractal , that is, a moving picture that contains smaller versions of itself (run across the cerise and bluish trees shown below on the right).

We're going to create a function tree() to draw our tree. It will first draw the trunk of the tree, rotate slightly, telephone call tree() to draw the right branch, rotate once more, and so phone call tree() to draw the left branch.

We will build upwardly to the overall tree starting with simpler steps.

Step 0: Manipulating the Coordinate Filigree

Take some fourth dimension to read parts of this tutorial on second Transformations in Processing. Focus on "Translation: Moving the Grid" and "Rotation" sections. You do not need to understand or apply pushMatrix and popMatrix for this lab.

Set up a basic program in Processing with a drawing canvas size of your choice. First with the following draw() function:

void depict() {   translate(width/2,peak);          // move origin          rotate(radians(0));          // rotate (degrees)          // try cartoon something to run across where it shows up!          noLoop();          // just draw once          }        

The phone call to translate() above will motility the origin of your coordinate system to the eye of the bottom edge of your drawing canvas regardless of the size of your sail!

Play around with the lawmaking to a higher place to brand sure that you understand the effects of the translate() and rotate() functions:

• Insert some drawing statements to meet where things now show upward on your canvass.
  • If the sail looks bare, you may be drawing off the bottom.
• Alter the 0 in the rotate() role to run into how it alters your drawing.
  • Rotations occur in the clockwise direction around the origin.
  • Make sure to attempt both positive and negative numbers betwixt -360 and +360.

Step i: Explicit Trees

Copy the functions tree1() and tree2x() below into your program. These both explicitly depict out minor trees -- tree1() is just a trunk and tree2x() has a trunk and 2 branches.

void tree1(bladder len) {   line(0,0,0,-len);          // depict trunk          }  void tree2x(float len) {   line(0,0,0,-len);          // draw trunk          translate(0,-len);          // move origin to top of trunk          rotate(radians(15));          // rotate slightly to right          line(0,0,0,-len*0.75);          // draw right co-operative          rotate(radians(-thirty));          // rotate back to the left (twice as much as before)          line(0,0,0,-len*0.75);          // depict left branch          rotate(radians(15));          // rotate back to "normal"          translate(0,len);          // motion origin back to bottom of body          }        

Find that tree2x() is deliberately symmetric with calls to rotate() and translate() -- returning the coordinate system to where yous started is a central part to making this work properly.

Try calling tree1() and/or tree2x() from describe() and make sure the output matches your expectations. We encourage you to play with the non-zero values in tree2x() to increase your understanding of the event of each instruction.

At this rate, it'll take y'all forever to brand the beautiful version of the tree! Let'southward meet if nosotros tin simplify this procedure.

Step ii: Edifice Up Trees

Make a copy of the tree2x() role and rename it tree2(). Observe whatever similarities with tree1()? Supercede the code to describe the branches in tree2() with calls to tree1().

Now make a tree3() office that works the same fashion simply calls tree2() to draw the branches. The output should await something like the following:

Footstep 3: Making It Recursive

These blocks all look exactly the aforementioned, don't they? So it makes sense to wonder if we tin replace them all with a single tree() function. Here's the big idea: we can write a tree() function that calls itself, provided that it knows how many levels information technology's expected to describe! And then it volition need a levels input in addition to the length (len) input.

In the previous Step, tree3() used tree2() and tree2() used tree1(). If you actually had the patience to piece of work upwards to tree120(), what office would information technology phone call for its two branches? To generalize the pattern, tree() volition call tree(), but reduce levels past 1:

void tree(float len, int levels) {          // what code should go in here?   // brand certain that it calls tree() to brand the branches          }        

It should look similar to the other tree functions yous take written up to this point. Try reproducing the tree3 image using tree().

Unfortunately, it does non work! You should go something that looks like the image below. Note: your drawing sail window will likely get very laggy and Processing may throw y'all an interesting error bulletin.

Discuss with your partner: what's wrong with the function? Information technology may help to trace the program execution.

Stride 4: Fixing the Recursion

The trouble is that the original numbered tree functions aren't still. The start one, tree1(), is different; it only draws a body, without any branches.

Fix tree() so that information technology does something unlike when levels is 1. levels == 1 is the base case and the balance is the recursive case.

With this change, nosotros can draw trees of any complexity! Here's a level-9 tree:

Pace v: Color Your Tree

Which parts of the tree correspond to which level? To assist you visualize, we will color each level of the tree differently. The colors and implementation will be left up to you, simply our suggestions include using a color array or an algebraic formula to create a slope.

When you lot draw a due north-level tree, is the trunk of the tree level 1 or level n? Include your reply in a comment at the outset of your programme.

Step 6: Vary Your Tree [OPTIONAL]

It is recommended that you piece of work on a separate copy of your tree code then that yous don't pause your previous work! If you practice brand changes that yous are happy with and wish to submit it, brand sure yous document the additions you made in comments at the top of the program.

Play effectually with the post-obit changes one at a time to determine their effect on your tree:

• Change the scale factor (was 0.75).
• Modify the plow angle of one or both branches (was fifteen degrees left/right).
• Change the number of branches (number of recursive calls; was 2).

Y'all tin can even try adding randomness to the scale gene and turn angle! Of import: call up carefully about how yous can ensure that the coordinate organisation is returned to same position during a call to tree().

If you would similar to, you tin endeavor to make a drawing equally shut to the "realistic" tree at the beginning of this lab as possible!

Submission

• Make sure that your name is included in your file.
• Make sure that most of your lines of code have comments so that someone else can understand information technology.
• Make sure your response virtually the level of the trunk is included in your comments.
• Brand sure that your tree has at to the lowest degree 5 levels and that every level of your tree is a different color.
• Submit your finished .pde file from Step 5 (or Step six) to the Canvas assignments page.
• You lot should add this program to your portfolio.

Source: https://courses.cs.washington.edu/courses/cse120/17sp/labs/11/tree.html

Posted by: smithmeren1989.blogspot.com

Share this post