BFOIT Introduction      to Programming      Recursion (Advanced Iteration)

Introduction

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

1. 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.
2. How to stop execution of a procedure without outputing a value.

Drawing a Squiral

Figure 11.1

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!

TurtleGraphics Applet

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
    ...

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

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.

Figure 11.2

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.

Name	Input	Description	Example
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

Figure 11.3

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.

(A)	(B)
Figure 11.4

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

    to tree :len
      forward :len
      left 30
      tree difference :len 8
      right 60
      tree difference :len 8
      left 30
      back :len
      end

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

Exercise:

The von Koch Curve and Snowflake

Figure 11.5

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

1. divide it into three equal parts

   

2. replace the inner third of it with an equilateral triangle

   

3. 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

Checkout the line drawn in Figure 11.6; it is the results of plotting the equation: y = x / 2 + 20.

y = x/2 + 20

Figure 11.6

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

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

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 = x² - 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.

A line is a spatial feature that is given a precise location that can be described by a series of coordinate pairs.

For the equation y = x² - 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

    to gotoPoint :xValue
      setxy :xValue yValue :xValue
      end

    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

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 = x² - 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

Figure 11.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

Figure 11.8

1. Recursion's base is the procedure with inputs.  The body of the procedure contains a recursive invocation, an invocation to itself.
2. The recursive invocation changes at least one of the inputs, which will change its behavior and move the process one step closer to terminating.
3. 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

Figure 11.9

New jLogo Procedures Used In This Lesson
Name	Input	Description	Example
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]