One of the things computers are good at is performing dull repetitive tasks. In Logo, the easiest way to get a computer to do something over and over (and over and over) is recursion. A Logo procedure is called recursive if it calls itself as a subprocedure. In other words, a recursive procedure repeats itself.

If the last thing a procedure does is start itself up all over again, the computer will never stop running the procedure. For some purposes you will want to accept this, and use Command-. to stop your program when you want it to stop. At other times, you can use a counter to tell the procudure to stop after a certain number of repetitions.

to bore
print [Hello world!]
bore
end

Read through the program, imagining what it does at each step. This is called tracing the program, and is the first thing to try when a program is not working. It is a good idea to quickly read through any program before running it.

The following is an example of a recursive procedure which stops after a specified period. Try tracing its behavior for some small values of n before testing it. Can you predict whether it will print the number 0?

to countdown :n
ifelse :n<1 [print [Done!]] [print :n countdown :n - 1]
end

There are some new commands in this program. The ifelse command takes three inputs: a logical expression (:n<1), a command to execute if the expression is true (print [Done!]) and a command to execute if the expression is false (print :n countdown :n - 1). Notice that the program checks to see whether n is less than 1, rather than checking that n=0. This is a quick and easy way to handle inputs like .5 and -20. As you are writing programs, you should keep in mind that their inputs may not be what you expect.

One possible use of a recursive procedure is computation of Fibonacci numbers, using the definition that each n^th Fibonacci number is the sum of the two preceding Fibonacci numbers. To do this, we need a new command, output (abbreviated op), which lets a procedure "return a value" which can then be used as an argument to another procedure, printed out, evaluated, added to the output of another procedure, etc. Try tracing the following program by hand -- what is the effect of writing a procedure that calls itself twice?

to fib :n
ifelse :n<3 [output 1] [output (fib :n - 1) + (fib :n - 2)]
end

You can run this program by typing, for example, fib 6, but you get the error message You don't say what to do with 8. This is because the procedure outputs the value 8 and Logo then trys to evaluate that output. If you type print fib 6 Logo sends the output of fib to the procedure print, and the error message goes away.

Running the program on large values of n causes the program to call itself a large number of times (roughly 2^n). This may crash your computer, and is in general a bad idea. A large part of the job of computer scientists is to find ways of making programs like this more efficient. In this case, it is most efficient to keep a list of the Fibonacci numbers you have already calculated and consult the list, rather than recompute each Fibonacci number every time you run the program.

to pollyspi :side :ang :inc
fd :side rt :ang
pollyspi (:side + :inc) :ang :inc
end

Type in the program and run it. Use Command-. to stop it when you need to. Try running it with different values of side length, turn angle, and increase. Try at least two examples where the turn angle is close to the exterior angle of a regular polygon and the increase is small relative to the side length.

Try polyspi 10 89 1. Notice the four inward turning spirals. Spirals like this can be seen in pine cones, sunflowers and other plants, such as the one shown on this web page. Despite its use of terms such as "the most irrational number", the web page is worth reading. All else being equal, a new branch of a tree, seed of a sunflower, or floweret of broccoli will grow in the position and direction in which there is the most room, which happens to be at an angle of approximately 137.5 degrees away from the last branch, seed, or floweret. The results of this growth pattern provide surprising examples of Fibonacci numbers in nature.

We can use Logo to illustrate this effect for us. To simulate the growth of new sunflower seeds, we would place a seed at each point of the star-shaped spiral generated by polyspi 10 137.5 1. Alas, simply typing in polyspi 10 137.5 1 generates an attractive but confusing mess. We will write a program to place a small dot at each point of the star. We can later replace the instructions in the dot program with a program to draw a sunflower seed (if we're feeling ambitious.)

to dot
repeat 2 [fd 1 rt 180]
end

to dotspi :side :ang :inc
pd dot pu fd :side rt :ang
dotspi (:side + :inc) :ang :inc
end

First, compare the results of running pollyspi 10 89 1 to the output of dotspi 10 89 1.

Now try running the command dotspi 3 137.50776 3. Look for both clockwise and counter-clockwise spirals similar to the four spirals generated by dotspi 10 89 1. You should see thirteen spirals curving inward in a clockwise direction and eight sprials curving inward in a counter-clockwise direction. (The eight spirals will curve in much more slowly than the others, and so will be harder to see.) The fact that eight and thirteen are sequential Fibonacci numbers is not a coincidence!

Try varying the increment variable (:inc) and re-running dotspi. Each time you run dotspi with the angle 137.50776 you should see Fibonacci numbers of spirals coming outward from the common center.

Challenge: erase the procedure dot and replace it with a procedure that draws broccoli flowerets or sunflower seeds or some other appropriate pattern. Experiment with adding arguments to dot to make the flowerets or seeds increase in size as they spiral outward.