Recursive Tree

In this lab, you will create a tree-drawing program that uses recursion to draw the branches by drawing smaller and smaller trees.

On this page, you will explore nesting code for trees inside code for trees.

The branching pattern on many plants has fractal structure: the smaller parts are like miniature copies of the whole plant.

: Fractal

A fractal is an infinite repeating pattern made up of copies (or slight variations) of the same shape. In this picture, the green branch is (essentially) the same shape as the entire picture.

fractal tree

  1. "U7L1-Tree"Start a New Project called U7L1-Tree
  2. Build the first level.
    1. Build a tree 1 block. It looks simple, but things will get more complicated soon.
      tree 1, size: (size #) { move (size) steps move (-1 ✕ size) steps<br> }
    2. Point the sprite up, put the pen down, and run tree 1, size: (50). You should get a result like this:
      tree 1 result: Trunk of tree drawn
    3. Talk with Your Partner Where does your sprite start? In what direction is it facing? Where does it stop?
  3. Using tree 1 to draw the branches in tree 2 is using abstraction.
    Build a tree 2 block that uses tree 1 as its branches.
    tree 2, size: (size #) { move (size) steps turn counterclockwise (25) degrees tree 1, size: (size ✕ 0.65) turn clockwise (25) degrees turn clockwise(35) degrees tree 1 size: (size ✕ 0.85) turn counterclockwise (35) degrees move(-1 ✕ size) steps }
    tree 2, size: (50)
    tree 2 result: Trunk of tree and two branches drawn
  4. Talk with Your Partner Describe exactly the position and direction of the sprite when the first tree 1 stops running. Why is that essential for tree 2 to work?
: State Transparency

State transparency means putting everything back exactly as it was when you started. It is especially important when blocks depend on other blocks. Usually, this means returning the sprite to the same position and direction and returning the pen to the same color and size.

  1. Make a tree 3 block that uses the tree 2 block as branches.
    Right-click (or control-click on a Mac) a block to "duplicate" or "relabel" blocks to make these tasks much faster. Click for an example.
    Needs better alt/title text. --MF, 6/18/20
    duplicate and relabel menu options
  2. Make a tree 4 block that uses the tree 3 block as branches.
  3. If you like, make a tree 5 block that uses the tree 4 block. Running tree 5 size:(50) should produce a result like this. Save your work
    tree5 result: Tree with trunk and branches

These blocks all look essentially the same except that tree 5 uses tree 4, while tree 4 uses tree 3, and tree 3 uses tree 2, etc. So it makes sense to wonder if we can replace all these blocks with a single tree block by using a variable for the number that changes.

: Recursion

Using a procedure inside of itself is called recursion.

You learned about recursion on Unit 3 Lab 1 Page 3: Using Abstraction to Nest Triangles.
  1. This is the general idea for the recursive version. Talk with Your Partner What are the differences between this recursive tree script and the code for tree 2 and tree 3, and why are these differences needed?
    tree, level: (level #) size: (size #){ move (size) steps turn counterclockwise (25) degrees tree, level: (level - 1) size: (size ✕ 0.65) turn clockwise (25) degrees turn clockwise (35) degrees tree, level: (level - 1) size: (size ✕ 0.85) turn counterclockwise (35) degrees move(-1 ✕ size) steps }
  2. Here is what happens if you run tree, level: 9 size: 50.
    Tree drawing never terminates, stuck at a single branch
    It doesn't work. Try to debug the script. Consider building the code and running it yourself. Talk with Your Partner What's going wrong?