CPSC 120: Principles of Computer Science
Fall 2002
xLab 8: Subroutines and Recursion
SUBROUTINES WERE INTRODUCED in Lab 6. This lab will continue the study of subroutines. The lab concentrates on the idea of a subroutine as a black box and on recursive subroutines that call themselves, either directly or indirectly.
You should be familiar with the material from Chapter 7 of The Most Complex Machine, Sections 1 and 3, especially with the material on recursive subroutines. The Koch curve and the binary tree introduced in that section will be used in the lab.
The exercises for this lab ask you to save some files in the "homework" directory in your Linux account. Under Windows, make sure that your math account is mounted as a network drive. Goto the Lab8 folder in the cpsc120 folder and double-click the icon named "Run xTurtle Lab8". Assuming that your math account has been mounted, you will be able to directly save files into your homework directory. Please be sure to give your files obvious names, or make a sub-folder for them inside the homework folder.
You can also run xTurtle off the web by clicking the following button. However, if you do this , you will not be able to save your work:
Black Boxes
You are familiar with the idea of a subroutine as a black box. When you use predefined subroutines such as forward and moveTo, you don't need to know exactly how they work. All you need to understand is how to use them and what they will do. User-defined subroutines can also be used as black boxes, provided that someone else has written them for you.
The xTurtle applet that you launched for use in this lab is set up to load a sample program called "SymmetrySubroutines" This program contains the definitions of six subroutines for drawing symmetric pictures. These subroutines are meant to be used in the same way as the usual drawing subroutines such as forward and circle. For example, one of the subroutines defined in "SymmetrySubroutines" is multiForward. This subroutine is similar to the built-in forward command, except that instead of just drawing one line, it draws eight lines in a symmetrical pattern. The "SymmetrySubroutines" program defines the following six subroutines, each of which draws a symmetric pattern: multiForward, multiBack, multiMoveTo, multiMove, multiCircle, and multiArc.
To see how this works, select the "SymmetrySubroutines" program from the pop-up menu at the top of the xTurtle applet, and use the "Run Program" button to run the program. Nothing appears on the screen, since all the program does is define some subroutines. However, once the subroutines are defined, you can use them as commands, just as you would use any of xTurtle's built-in commands.
As an example, type the following commands into the text-input box below the xTurtle drawing area, pressing return after you enter each command:
multiArc(5,40)
turn(-40)
multiforward(3)
multicircle(2)
Also try some other commands. If you want to make a more complicated picture, go back to the "SymmetrySubroutines" program and add your commands at the end of that program (after the definitions of all the subroutines). For example, add the following commands to the end of the program, and then hit the "Run Program" button:
LOOP
multiforward(0.5)
face(randomInt(360))
EXIT IF 1=2
END LOOP
You will have to end the program with the "Stop" button. (The statement "exit if 1=2" in this program is a fancy way of saying "Never exit.")
In the previous part of the lab, you used several subroutines as black boxes, without having to understand what went on inside the box. But you should remember that "not having to know what's inside" is only part of the black box story! When you write a subroutine yourself, you are working inside the box. While you are writing the subroutine, you can concentrate on making it perform the specific task it is designed to do, without worrying for the moment exactly what role it will play in a complete program. From the point of view of a programmer trying to design a complex program, subroutines are a tool for breaking a complex problem down into smaller, more manageable subproblems.
Recursive Trees and Recursive Walks
A recursive subroutine is one that calls itself. A recursive subroutine is a black box that uses itself as a black box. Section 7.3 in the text introduces recursive subroutines using the example of a binary tree. The program for this example is in the Sample program "BinaryTrees". Select this program from the pop-up menu at the top of the xTurtle applet and run it. Nothing will happen, since the file only defines some subroutines. The main subroutine defined in the file is called TestTree. If you enter this into the text-input box beneath the drawing area of the applet, you will be asked to specify a complexity level. The computer will draw a tree with the complexity that you specify. Try this, for example, for a complexity level of 5.
A binary tree of complexity zero is defined to be a single straight line segment. A binary tree of complexity greater than zero is defined to consists of a "trunk," which is just a line segment, with two "branches" attached to it. Each of the branches is a binary tree, which is smaller than the complete tree and which has smaller complexity than the complete tree. This is a recursive definition because we are saying that a tree contains pieces which are themselves trees. Because binary trees are defined recursively, they can be drawn by a recursive subroutine. You should try to understand the definition of the Tree subroutine.
An element of randomness can make a recursive picture look more realistic. Although we won't get very close to realism in this lab, the sample program named "RecursiveBush" shows what happens when you add some color and some randomness to a recursive tree-drawing program. Each time you run this program, it will draw a different recursive bush.
A third example of recursion is contained in the sample program "KochCurves." This example is also taken from Section 7.3 in The Most Complex Machine. A Koch curve is a way of getting from one point to another -- with a lot of detours. To help you understand this, run the sample program "KochCurves." After you have run the program, you can use the command TestKoch in the xTurtle applet's text-input box. When you do so, you will be asked to specify a complexity level for the Koch curve. You should try complexity levels of 0, 1, 2, 3, and 4.
A Koch curve of complexity 0 is defined to be a straight line segment. A Koch curve of complexity 1 is a line segment with a "bump" or "detour." The complexity-one curve is made up of four line segments, but you should think of each line segment a Koch curve of complexity zero. A Koch curve of complexity 2 is obtained from the curve of complexity 1 by adding a detour to each line segment in the curve. You should look at a Koch curve of complexity 2 as being made up of four smaller pieces, where each piece is a Koch curve of complexity 1. More generally, a Koch curve of complexity N is made up of four smaller Koch curves of complexity N-1. Once again, this is a recursive definition, and the subroutine that draws Koch curves is a recursive subroutine. Try to understand how the pictures you see are produced by the Koch subroutine.
The "KochCurves" program also defines a subroutine named "Snowflake" which draws "Koch snowflakes." A Koch snowflake is made by joining three Koch curves together at their endpoints, producing a symmetric, snowflake-like picture. Try it!
Exercises
These exercises are due next Friday, November 8. For Exercises 2, 3, and 5, you should save a program in your homework directory. In the lab report that you turn in, you should tell me the file names for your programs, and if you are working with someone, you should tell me whose directory to look in to find the program. You should turn in your answers to Exercises 1 and 4 on paper. You do not need to turn in a program for Exercise 1.
Exercise 1: Add the following lines to the end of the "SymmetrySubroutines" sample program, after all the subroutine definitions. Run the program a few time, to see what it does. Then write a short essay explaining exactly how the program works and why it produces the pictures that it does. (Try running this at fastest speed, with the turtle turned off.)
declare x
x := 0
loop
face(360*random)
hsb(x,1,1)
multiforward(0.4)
x := x + 0.005
if x > 1 then
x := 0
end if
exit if 1 = 2
end loop
Exercise 2: The Speed pop-up menu in the xTurtle applet works by inserting delays betweens commands. Since circle is a single command, a complete circle is drawn instantaneously, no matter what the setting of the speed menu. This disappointed one of my students, who wanted to be able to watch the circles being drawn. Write a subroutine
SUB SlowCircle(radius)
that will draw a circle by drawing 60 arcs, where each arc covers 6 degrees. Then use your subroutine to (slowly) draw a picture like the following:
Finally, modify your SlowCircle subroutine so that it draws each of the arcs of the circle in a different color. The color of an arc can be set to hsb(hue,1,1). At the beginning, the value of hue should be zero. After drawing each arc, it should be increased by 1/60. Place a copy of the completed program in your homework directory.
Exercise 3: The text notes that you can add randomness to a Koch curve by deciding randomly whether to detour to the left (using turns of 60, -120 and 60) or to the right (using turns of -60, 120, and -60 instead). Make this change to the program "KochCurves" sample program, and try it out. (The only changes you need to make are inside the subroutine that begins with "SUB Koch".) In the subroutine, you can declare a variable named x (for example) and set x := RandomInt(2). Use the value of x to decide whether to detour to the left or to the right. (When you have made the change, the SnowFlake subroutine will automatically produce a "Koch Island" instead. Try it!) Place a copy of the program in your homework directory.
Exercise 4: This exercise asks you to find the number of line segments in a binary tree of a given complexity. It is similar to the previous exercise, but it's harder to find a formula in this case. Run the "BinaryTrees" example program, and then use the TestTree subroutine to draw trees of complexity 0, 1, 2, 3, 4, and 5. For each of these trees, count the number of straight line segments that it contains. For example, in a tree of complexity 1, the number of line segments is 3 -- each branch is a single line, and the trunk is the third line. You should try to find a formula that gives the number of line segments for any given complexity. You might not be able to find a formula that gives the number directly, but you should at least be able to find a formula that tells how the number of line segments changes as you go from one complexity level to the next.
One way to approach this problem is first to determine how many new lines are added to the tree when you go from a tree of complexity N to one of complexity N+1. Then use that to figure out the total number of line segments. Another approach is to "think recursively": Remember that a tree of complexity N+1 is made up of a trunk plus two trees of complexity N. Turn in your answer, including an explanation of your reasoning.
Exercise 5: For this exercise, you will write a recursive subroutine that displays an element of randomness. The subroutine will be called "mountain", because it draws pictures that look a bit like a mountain range. Here are two pictures produced by the subroutine:
Each of these pictures was produced with the commands:
clear penUp moveTo(-7,0) penDown mountain(7,0,10)
The command mountain(x,y,c) should move the turtle along a jagged path from its current position to the point (x,y). The amount of jaggedness is specified by the "complexity," c. If the third parameter, c, is zero, then mountain(x,y,c) simply draws a straight line from the current position to (x,y). If c > 0, then mountain(x,y,c) will choose a random point, (x1,y1), somewhere between the current position and (x,y). It will draw a "mountain" of complexity c-1 to the point (x1,y1) and from there it will draw a second mountain curve of complexity c-1 to the point (x,y). The trick is to choose the intermediate point (x1,y1). This can be done by finding the midpoint between the current position and (x,y), and then moving the y coordinate of that midpoint up or down by a random amount. This computation can be done as follows, recalling that the current position of the turtle is given as (xcoord,ycoord):
x1 := (xcoord + x) / 2
y1 := (ycoord + y) / 2
y1 := y1 + (random - 0.5) * (xcoord - x)
Try to put all this together into a definition of mountain(x,y,complexity). Remember to declare x1 and y1 at the beginning of your subroutine. Place a copy of your program in your homework directory.
--David Eck (eck@hws.edu)