Basic Programming 101: Session IV

For-Loop and Counting

The for-loop construct allows us control specific execution of a programs actions. It says: "do this for this many times." The program can count up, count down, count by fractions, whole numbers or whichever scalar value we choose. Recursion, although powerful, may have resource limitations (every function call takes memory). If the algorithm doesn't require "state" or memory, a for-loop does nicely.

We have two examples here, a very short program that shows the for-loop and a second program that graphs functions.

For-Loop

10 REM Simple for-loop prints nums 1..10
20 for i = 1 to 10
30 print i
40 next i

Function Grapher

In this next example, we build a function graphing program that steps through a range of values and plots each of the points. We could do this in whole number steps, but the plotted functions may not appear continuous; they'll look more like points than connected curves/lines. The finer the grain of step, the more likely the function appears continuous.

Lines 10 & 100 set up some constants and open a graphics window of the appropriate size. In this case, we keep two constants which represent the center of our graphics screen.

10 xc = 250 : yc = 200
100 graphics window 25,25,xc*2,yc*2

Next, Line 110 contains our for-loop. It has a range of [-250..250] and granularity (step) of 1/10. You might need to make this finer (smaller) depending upon the kind of function you have. In this case, it could be step 1, because the function is a simple line.

110 for t = -250 to 250 step 0.1

Lines 120 and 130 contain the function. We set variables x and y to t. This will graph the line y=x. You might wonder why we didn't just make x the for-loop variable ("for x = -250 to 250"). There's a good reason for this, I will explain below.

120 x = t
130 y = t

Line 140 does our work: set a point at . Not really because we have xc and yc in the calculations. Remember, is the center of the graphics window (the size of the window is 2*xc, 2*yc). Also, note that we subtract y from yc instead of add. That's because graphics windows are upside-down when compared to Euclidean graphs, which have positive Y going up the page. Computer graphics windows have positive Y going down the page and the origin (0,0) in the upper-left corner, a natural consequence of the way information is displayed on a computer's screen.

140 graphics pset xc+x,yc-y

Finally, we close the for-loop in Line 150 and, as I like to be disciplined in my coding, Line 160 ends the program. This line is not strictly needed, but if we ever implement a subroutine, you would want the program to end here, so make it a habit.

150 next t
160 end

Why is X not the loop variable?

We could have made x the loop variable, but didn't. Why? Because, not every equation to be plotted has only one value of y for every x. What does that mean? Consider the equation y^2 = x. This is a parabola, but tilted on its side 90 degrees. In all but one case, there are two values of y that satisfy any particular x. If x = 4, y = 2 or -2. To plot this equation, use y = t and x = t^2.

Making a circle would be a challenge, since the equation for a circle is x^2 + y^2 = r^2. Fortunately, BASIC, like all good programming languages, provides a math library to assist us. Some of you may not have had trigonometry, yet, but there are well known functions from trig that address this problem: sine and cosine. In BASIC, these are sin and cos. They take an angle and return the Y or X value appropriate for that angle. In fact, cos(t)^2 + sin(t)^2 = 1 for every angle t. The math library uses radians, instead of degrees.

To plot a circle, use x = 100*cos(t) and y = 100*sin(t). This paints a circle with radius 100. If you want an oval, change the constant (100) in either or both of the equations.

In fact, playing around with programs is a great way to understand how they work. Feel free to play with this code and see what types of shapes and patterns you can draw. I've included some of the interesting ones I've found below. Use the comments section to add your own and tell us what it makes.

Infinity: [-250..250],1/10,x=110*cos(t),y=100*sin(t)*cos(t)

Spiral: [0..250],1/1000,x=t^2*cos(t)/2,y=t^2*sin(t)/2

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