Page 2: The Base Case

Unit 7, Lab 1, Page 2

On this page, you will learn how to stop recursion from going on forever.

It seemed to make sense to replace all the look-alike numbered tree scripts with a single recursive script with the same structure:
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 3, size: (size #) { move (size) steps turn counterclockwise (25) degrees tree 2, size: (size ✕ 0.65) turn clockwise (25) degrees turn clockwise(35) degrees tree 2 size: (size ✕ 0.85) turn counterclockwise (35) degrees move(-1 ✕ size) steps } → 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 }

But it didn’t work:
Tree drawing never terminates, stuck at a single branch

Betsy: I ran tree, level 9 size 50, but look what happened. What’s going wrong?

Alphie: It never stops!

Gamal: After it turns to the left, it should make a smaller tree, but then it’s supposed to finish and turn to the right and do a tree there too.

Betsy: Yeah! It’s not making it to the right side at all.

Gamal: Hmmm, in each recursive call to tree, the sprite draws smaller and smaller left branches until it seems to be just spinning around in one place. It never turns right to finish the tree it’s working on.

Alphie: Hey look! The tree 1 block is different from the others; it just draws a line, no branches, and it puts the sprite back where it started.

Alphie points to the tree 1 code and to the figure it draws.
tree 1 size:(size#){move(size) steps; move(-1*size) steps} tree1 result: Trunk of tree drawn

Betsy: So our recursive tree block has to do something different at the lowest level!

Gamal: Yup! It has to draw just a line without adding another branch.

Base Case

This different version for the lowest level of a recursive script is called the base case.

  1. Correct the recursive tree block from the bottom of the previous page so that it includes a base case to stop the script from calling itself forever.

    Click for a hint.
    On Unit 3 Lab 1 Page 3: Using Abstraction to Nest Triangles, you only drew the nested triangle if size > 9. That is one way to stop the recursion from going on forever. Click here if you need a bigger hint.

    Here are two ways you could correct the recursive tree block. There are more. Use whatever makes most sense to you.
    if(level=1){move(size) steps; move(-1*size) steps}else{...Build more branches...} move(size) steps; if(level>1){...Build more branches...}; move(-1*size) steps

  1. Test your code: Run tree, level: 9 size: 50. If it is working properly, you should get a result like this.
    Tree with trunk and 8 levels of branches

Take turns speaking

Recursive blocks call themselves. In order for them to finish, there must be some special case in which they don’t call themselves. That is the base case, a simpler version of the block’s script that doesn’t call the block itself.

There is usually a conditional with two cases: a base case for the lowest level that stops the recursion from going on forever and a recursive case that calls the block itself at lower levels until it reaches the base case.

If a block keeps recursively calling itself forever (as when the sprite was just spinning around in one place), that’s a bug, and we say the program is stuck in an infinite loop.

  1. Talk with Your Partner Look at your corrected recursive tree script. Identify the base case and the recursive case, and discuss how recursion works in this script.

  1. Does tree run in reasonable or unreasonable time? You could think this out, you could try timing the script for levels 8 through 12, or you could create a global count variable and add one to it first thing in the tree block in order to record the number of times that the procedure is called for trees of different levels.

    You learned about reasonable and unreasonable time on Unit 5 Lab 1 Page 5: Categorizing Algorithms.