Many lessons ago, you learned a way to repeat a list of instructions some number of times. This allowed you to reduce the size of your programs. Your programs were thus easier to enter correctly, easier to read, and easier to modify. You use repeatwhen you notice you are doing something identical over and over.
A few lessons later you learned how to write procedures with inputs. Invocations to these procedures can be substituted for patterns of instructions in your programs that match the functionality provided by the procedures you write.
Successful use of these features of a programming language depend upon a programmer’s ability to notice patterns in the code they have written or are thinking about writing. This is what makes programming fun and a bit challenging – the programmer is solving a puzzle. In this lesson you will be challenged to discover patterns that are a bit more subtle. And, the structure of the procedures that you write will also be a bit more complex. But, I’ve got some fun programs for you to write, puzzles for you to solve.
In this lesson, you will learn
- A more powerful way to iterate some set of instructions. You are going to invoke a procedure from within its own definition. This is called recursion.
- How to stop execution of a procedure without outputing a value.
Drawing a Squiral
Take a close look at the following trail of the turtle.
What are the instructions that can be given to get the turtle to draw this squareish spiral? Here is the TG applet; play around a bit until you get it.
|alt=”Your browser understands the <APPLET> tag but isn’t running the applet, for some reason.” Your browser is completely ignoring the <APPLET> tag!|
What you need to do is move the turtle forward, make a right turn 90 degrees, go forward a little bit further than you did last time, turn right 90 degrees, go forward – again, a little bit further than last time, etc… Do you see the pattern in what the turtle is doing?
A few lessons ago, you learned how to discover patterns in your code and then use a repeat command to make what you are doing clearer. Well, just in case you didn’t get the squiral code above, here is my version.
fd 5 rt 90 fd 10 rt 90 fd 15 rt 90 fd 20 rt 90 fd 25 rt 90 ...
Go back to the TG applet above and try to use a repeat command to draw the squiral. It can’t be done, can it?
You need a way to change the distance that you move forward.
Back in the lesson on predicates and the if command, I introduced recursion to eliminate choosing white in a random color procedure. But, I didn’t explain it; I said it is something I’d cover in a later lesson. It’s time to cover it… It’s what we need now.
- when you want to do something a number of times (iteration), you put what you want to do inside the square brackets of a repeat instruction.
- when you want to do things that are sort-of the same, but different in ways that can be handled with parameters, you put what you want to do in a procedure that has inputs for the things that are different, the parameters.
Recursion, which is invoking the current procedure from within the body of the procedure, is the combination of these two important programming concepts,.
With recursion you get the iteration of a bunch of stuff with all of the flexibility provided by a procedure with inputs that control what happens.
Here’s a start at our squiral program.
to squiral :steps fd :steps rt 90 squiral sum :steps 5 end squiral 5
Looks simple enough, doesn’t it? Go back up to the TG applet and type in this definition. Then, invoke it with an input of 5. What happens?
If you didn’t make a typing error, you got the square spiral we wanted.
But, if you try to get the turtle to do something else, you’ll notice that it isn’t listening to you. It’s still busy. You might not have ever noticed this before – checkout the rightmost side of the CommandCenter name stripe.
The problem is that the program never ends. It is easy to get into this situation when you are learning about recursion.
So, how do you get out of this situation? Hold down the [Ctrl] key and press Q (which stands for QUIT). However, for this to work, the CommandCenter must be the active subwindow, the one that has focus. You can tell by looking at the cursor – if it’s blinking, then the subwindow has focus.
So – back to squiral.
What we need is called a stop rule. A stop rule is an instruction that terminates the recursive execution.
You already know one way of terminating the execution of a procedure: output. However, if a procedure outputs a value, it has to go somewhere. So, there’s another command, stop, which terminates execution of the current procedure – without producing a value.
Here’s are descriptions of output and stop.
|OUTPUT||value||Execution of the current procedure is complete. output‘s input (value) is passed back to the instruction that the current procedure’s invocation is part of.||OUTPUT “true|
|STOP||The current invocation of the procedure in which STOP exists terminates.||IF LESS? :inp 0 [STOP]|
We can use an if instruction with stop to force our squiral program to terminate. Here’s how. Try it out in the applet above.
to squiral :steps if greater? :steps 50 [ stop ] fd :steps rt 90 squiral sum :steps 5 end squiral 5
In this example, I picked the ending value of 50 for a specific reason. Once you have squiral working and before you increase this ending value, I want you to trace the execution of squiral. If you don’t remember how to use trace, I introduced it in the lesson: “Defining Your Own Operators”.
So, use trace to see what is going on when you execute a recursive procedure. In this case, you are not using trace to help with debugging; you are using it to give you a visualization of a pattern produced in executing a recursive procedure.
Drawing a Tree
Alright, what is the pattern in this tree? What is the minimum object that can be drawn over and over that results in a tree that’s at least similar to this one?
Well, the first thing I did when I wrote my version of the program was to simplify the problem. Even though I noticed that the branches of the tree get thinner the further out from the trunk, I decided to skip this detail at first. My style of programming is to get something working first, and then add complexity. So, the left side of Figure 11.4 shows a tree with a constant pen size of 1.
Look close – the tree is nothing but a bunch of ‘Y’s. In the right half of Figure 11.4, I’ve highlighted the ‘Y’s making up the leftmost edge of the tree.
Well, the biggest clue you’ve got on how to solve this puzzle is that the solution has to be recursive, otherwise I wouldn’t have included it in this lesson. And, looking at the tree with the highlighting, it’s obvious that we need to write a procedure that draws a ‘Y’.
to tree :len forward :len left 30 forward difference :len 8 back difference :len 8 right 60 forward difference :len 8 back difference :len 8 left 30 back :len end tree 60
Here’s a program that draws a ‘Y’ – check it out. Next, an easy guess is that the lines of instructions that draw the branches need to be replaced with invocations to tree.
to tree :len forward :len left 30 tree difference :len 8 right 60 tree difference :len 8 left 30 back :len end
What’s missing? Test it out.
It’s missing a stop rule. Since each recursive invocation of tree decreases the input len, we can use this to determine when the procedure should just stop.
to tree :len if less? :len 5 [stop] forward :len left 30 tree difference :len 8 right 60 tree difference :len 8 left 30 back :len end
OK. This works… Now your turn to complete the project. Add code that decreases the width of the branches of the tree. As the branches become smaller in length, decrease their width.
The von Koch Curve and Snowflake
A Koch SnowFlake, first described by Helge von Koch in 1904, is one kind of a thing called a fractal. To draw one, you start with an equilateral triangle (see the left-most object in Figure 11.5). For each side of the triangle, you
- divide it into three equal parts
- replace the inner third of it with an equilateral triangle
- repeat the first two steps on all lines of the new figure – this can be done indefinitely
This is another classic problem where recursion saves the day. Have fun. Treat this as a puzzle. Don’t be afraid to just play around at first. Get something working and then refine your program until you have an elegant solution…
Exercise: Graphing Equations
Graphing calculators are popular these days. But, now that you have TG, you can instruct the turtle to graph ANY equation you want.
Checkout the line drawn in Figure 11.6; it is the results of plotting the equation: y = x / 2 + 20.
|y = x/2 + 20|
You know how to draw a point; we did this way back in Lesson 4 when we instructed the turtle to draw a circle by drawing lots of points along the perimeter. Here’s one way, assuming a pensize of 4.
to drawPoint forward 2 back 4 forward 2 end
Chances are that you learned how to draw a straight line via the slope-intercept method in your study of Algebra. If you didn’t or you want to refresh your memory, here is a tutorial on it.
Given this knowledge, here is the rest of the code for drawing the line.
to gotoPoint :x :y penup setxy :x :y pendown end to gotoNextPoint :rise :run penup setheading 0 forward :rise setheading 90 forward :run pendown end to drawLine :yIntercept :rise :run gotoPoint 0 :yIntercept repeat 150 [ drawPoint gotoNextPoint :rise :run ] gotoPoint 0 :yIntercept repeat 150 [ drawPoint gotoNextPoint minus :rise minus :run ] end ;for equation: y = x/2 + 20 ;the y-intercept=20, rise=1, run=2 drawLine 20 1 2
But, this method draws a lousy line if the slope is either very shallow or very steep. Type in the code I’ve given you. Get it to work, then modify it to plot the equation: y = x / 10 + 50. See what I mean?
The good news is that since you now know a bit about recursion. You can use it to fix this problem. And, it will also allow you to draw lines for equations that the slope-intercept method doesn’t handle, e.g., y = x2 – 7.
The definition for line gives us a clue on how to approach the problem. Here is a definition for line that I found on the Internet.
So to draw a line, all we need to do is place the turtle on one of the end points of the line segment to be drawn (a coordinate pair) and then move it to a series of consecutive points. The points (coordinate pairs) can be produced by solving the concerned equation for a series of values.
For the equation y = x2 – 7, we can write a procedure that gives us the Y coordinate for an X coordinate provided as an input. Here it is.
to yValue :xValue output difference product :xValue :xValue 7 end
Given this, we can get the turtle to move to a point on the line with a procedure I’ve named gotoPoint. Here it is.
to gotoPoint :xValue setxy :xValue yValue :xValue end
And, this is where recursion come in. To draw the line, we need to supply gotoPointwith a series of inputs which represent x values. The solution is a pair of procedures.
to drawLineHelper :curX :maxX if greater? :curX :maxX [stop] gotoPoint :curX drawLineHelper sum :curX 1 :maxX end to drawLine :firstXValue penup gotoPoint :firstXValue pendown setpencolor 1 setpensize 2 drawLineHelper :firstXValue minus :firstXValue end
There you have it! I’ve used recursion to iterate through a series of x values, computing corresponding y values, and using setxyto move the turtle through the path of the points.
Figure 11.7 shows my version of the finished program. If you’ve jumped right in and used the above procedures to put together a program to plot the y = x2 – 7 equation, super! And if it doesn’t look like mine, congratulations! To get your graph to look like mine, you need to scale the points.
What do I mean by scale the points? Well, I have made twenty (20) turtleSteps equal to one (1) unit on the graph. You must be familiar with scaling. Maps have scales. Models of things have scales. In Figure 11.7, each of the tic marks on the axes are at 20 turtleStep increments, which means they are drawn at integer values. So, the line you see is for a series of points starting with x = -4 and going through x = 4.
The challenge is for you to write a program that duplicates what my graph looks like. So, you too need to add scaling to your program.
|y = x2 – 7|
Want a another challenge??? Simulate a 3D plane and plot the same equation over a Z axis, as I did in Figure 11.8.
|y = x2 – 7|
I’ve given you an introduction to one of the most powerful mechanisms for writing software that you will ever learn. Although recursionis often confusing and appears to work as if by magic, it actually only consists of a couple of simple pieces.
- The recursive invocation changes at least one of the inputs, which will change its behavior and move the process one step closer to terminating.
- A stop rule must exist, consisting of an if command which tests whether an input matches the termination condition.
Hopefully clarifying this, Figure 11.9 shows two ways to draw a box.
to box :size repeat 4 [ forward :size right 90 ] end
to boxHelper :size :num :maxNum if greater? :num :maxNum [ stop ] forward :size right 90 boxHelper :size sum :num 1 :maxNum end to box :size boxHelper :size 1 4 end
|New jLogo Procedures Used In This Lesson|
|MINUS||number||Outputs the negative of number||MINUS 122|
|STOP||The current invocation of the procedure in which STOP exists terminates.||IF EQUAL? :inp 0 [STOP]|