Basic Programming 101: Session III

Recursion

Recursion, one of the great and subtle features of mathematics and programming, means to define a function or procedure using itself. Classic examples include factorial and the fibonacci sequence. Fibonacci has real world parallels (with leaf and population growth) and even touches upon fundamental mathematical constants. All from one little self-defined function.

In this program, we display levels of triangles and play sounds when each triangle is drawn. The program asks the user to input the number of triangle levels, then, using two recursion steps (one for each level, one within a level), it draws the triangles. At no time does it track how many triangles it needs to draw, it only checks to see if it reached the end of the levels and the end of a row. The frequency of the sound played scales linearly with the number of levels while the duration of the sound falls (shortens) with the square of the levels. That's because the area of a triangle is proportional to the square of its height (or side).

First, we set up some variables. These determine the size of a border region on the graphics window (bd) and the height and width of the drawable region on that window (py, px).

10 bd = 10
20 py = 433
30 px = 500

Next, we ask the user for number of levels to display and compute the delta width and height, which becomes the width and height of the triangles (dx, dy). We also compute the sound frequency (frq) and the duration of the sound (dur). If the duration is less than 1/20 of a second, it won't play, so we make sure its at least that duration.

100 input "How many levels of triangles would you like? ",levels
110 dx = px/levels
120 dy = py/levels
130 frq = 110+110*levels
140 dur = 1/levels/levels
150 if (dur < .05) then dur = .05

Open the graphics window and be sure to include a border around it. Call our draw_triangle recursion routine with the point at which it is to start displaying the triangles and pass the number of levels to draw and an indicator to draw multiple levels. The point we pass is the lower left corner of the triangles - the recursive routine computes its drawing from the bottom up.

160 graphics window 25,25,px+2*bd,py+2*bd

170 draw_triangle(bd,py+bd,levels,1)

180 end

Here we have the routine that does the heavy lifting. It takes the lower left point, the current level and a boolean variable indicating whether we should draw sub levels (levels above this level). If is_full is ZERO, we only draw this level of triangles. Line 1010 tells us to stop if we have fewer than ONE level to draw. Line 1020 tells us if is_level is not ZERO, to draw the next level of triangles (level-1), and make sure it's a half triangle width to the right and a full triangle higher on the screen.

1000 sub draw_triangle(x,y,level,is_full)

1010 if (level < 1) then return

1020 if (is_full <> 0) then draw_triangle(x+dx/2,y-dy,level-1,is_full)

Here we draw the actual triangle then play a sound. Note the points on the triangle are computed from dx and dy.

1030 graphics triangle x,y,x+dx,y,x+dx/2,y-dy
1035 sound frq,dur,10

Finally, our second recursion step draws the remaining triangles for this row. Notice how is_full will be ZERO, so none of the triangles drawn from this call will hit the lower levels. That's OK, we already took care of that above. Also, note that we are drawing the row with this call, so the point we pass is one triangle to the right and on the same line. Remember to decrement level by one when we make the call.

1040 draw_triangle(x+dx,y,level-1,0)
1050 end sub