LOGO Recursion

Recursion – An Alternate to Iterative Loops

Recursion is a powerful technique to loop a procedure. Recursion can be used to create complex shapes such as fractals and Fibonacci Sequences.

Before we start to discuss the topic of recursion, let us first review how we can add Parameters to the LOGO Procedure (TO Command)

Recap of TO Command

In the LOGO Procedures chapter, we learned how to add new words to the Turtle’s vocabulary. Adding new words was done using the TO statement that defines new procedures. To recap, first you type the TO command along with the name of the procedure of your choice as in the statement below.

TO procedure_name

Then, you type the instructions (procedure) that the new procedure is intended to execute. At the end of all the procedure instructions, you enter the END command.  

LOGO then saves this new procedure name for you to use in your main program.

Recap of TO Command With Parameters

In the LOGO Procedures chapter, the TO statement did not specify any parameters. We learned how to include parameters in the Parameters chapter. 

To further explain how to write the TO procedure with parameters, let us use an example to write a procedure to multiply any two numbers. We call this procedure MPY. This procedure will multiply any two numbers y and z. The statements below define the MPY procedure.

The programmer can then use the procedure name, MPY in any subsequent programs. The main program will call this procedure by typing the procedure name (MPY in this case). The Program Example below shows how the main program calls the MPY procedure.

Now, suppose you want to find out the multiply result of numbers 11 and 13.  To do that, the main program has just one statement.

MPY 11 13

This statement calls the MPY procedure and passes arguments 11 and 13. It asks the procedure to show the result of multiplying the numbers 11 and 13. Parameters 11 and 13 replace the variables y and z respectively in the TO procedure

Below is the complete program.

PROGRAM EXAMPLE: TO STATEMENT WITH PARAMETERS

TO MPY :y :z
SHOW :y * :z
End

MPY 11 13; Call procedure MPY and pass the parameters y = 11 and z = 13.
143; Program’s output

We will now introduce the concept of recursion. The Program Examples on this page make use of TO procedures with parameters.

Note: Recursion is an advanced concept and may be skipped by beginning learners.

What is RECURSION?

When a calling program calls a procedure that, in turn, calls itself (meaning the same procedure), which in turn calls the same procedure, and so on, this process is called recursion. Such a procedure is called a recursive procedure. Since the procedure calls itself, the calling process never ends. The calling process goes on an infinite number of times.  We will discuss a little later how the IF command can be used to stop the never-ending recursion calls.

Why Use Recursion

You might wonder why use recursion techniques since all the problems can be also solved in normal iterative loops. The following are a few reasons why recursion is a useful technique to learn.

• Learning and practicing recursion helps you improve your problem-solving skills. Recursion techniques make you a better programmer.
• Recursion code is simpler and shorter than iterative code. The recursion function is generally written in fewer lines of code and will be easier for debugging.

The Recursion Procedure

Let us again use ‘SQUARE’ procedure as an example to explain recursion. This program is repeated below from LOGO Procedures chapter for reference.

  ; Add ‘SQUARE’ to turtle’s vocabulary (Define ‘SQUARE’ procedure).
 TO SQUARE
   REPEAT 4 [ FORWARD 100 RIGHT 90 ]
   END
   SQUARE; Call ‘SQUARE’ procedure.

We will use the above SQUARE procedure and modify it to make it a recursive procedure. If the ‘SQUARE’ procedure calls the ‘SQUARE’ procedure, which again calls the ‘SQUARE’ procedure, and this continues forever, it forms a never-ending calling sequence.

Now let us imagine that when the ‘SQUARE’ procedure calls the ‘SQUARE’ procedure, we change a parameter (side length) in the ‘SQUARE’ procedure. In the next call to procedure ‘SQUARE’, the side length is reduced. This process of reducing the side length of the ‘SQUARE’ continues indefinitely. Due to this process, the program will keep on drawing squares of smaller and smaller dimensions in a never-ending sequence and will never stop.

Let us look into how we can stop a program that uses recursion.

The IF Instruction

We discussed the IF command in the LOGO Control Commands chapter. We use the same IF command to terminate a recursive procedure. IF command helps us add intelligence to the program by giving the program the capability to make decisions based on doing a test for a specified condition. If the IF instruction condition test passes (true) the specified condition, the program takes a certain branch of the program and executes one set of instructions.  If the condition test fails (false) the specified condition, the program takes a different branch and executes a different set of instructions.

Thus, by specifying a test condition, we can use the IF instruction along with the STOP command to either continue calling the recursive procedure or stop a recursive program.

How Is Recursion Used?

Now we will write a program that uses recursion. It makes use of the IF command and the STOP command to prevent the recursive procedure to run indefinitely.

We will use drawing squares as an example. This program uses a TO statement to define a procedure to draw a square.  Then, the procedure calls itself within the procedure (recursion) to draw squares of half size at each recursion step. To ensure that the recursion does not continue forever an infinite number of times, the program uses the IF command to test for a certain condition. If the result of the condition is True, the program executes the STOP command to prevent further recursion calls.

PROGRAM EXAMPLE: RECURSION USING LOGO

TO SquareRecursion :LENGTH :RecursionStep  ;Line 1)
;LENGTH is length of the square. RecursionStep is the number of recursion steps we want.  
IF :RecursionStep = 0 [STOP]               ;Line 2) 
;stop recursion if RecursionStep is zero.
REPEAT 4 [ FORWARD :LENGTH RIGHT 90 ]      ;Line 3 
;Draw a square of :LENGTH specified in the call.
SquareRecursion :LENGTH / 2 :RecursionStep – 1 ;Line 4)
SquareRecursion 200 4                       ;Line 5)
; Call SquareRecursion procedure with length of square = 200; do four recursions steps. 

Detailed Step-by-step Description of the Program

Line 1) TO SquareRecursion :LENGTH :RecursionStep

Using the TO statement, we define a procedure named “SquareRecursion” with two parameters, RecursionStep, and LENGTH. The parameter LENGTH is the length of the side of the SQUARE. RecursionStep is the step number in the recursion call.

Line 2) IF :RecursionStep = 0 [STOP]

Use the IF condition to test if the RecursionStep has decremented to zero.  If it has reached zero, stop further calling the recursive procedure.  On the other hand, if RecursionStep is greater than zero, continue making a call to the recursive procedure.

Line 3) REPEAT 4 [ FORWARD :LENGTH RIGHT 90 ]

In line 3), we define the procedure to draw a SQUARE. The procedure uses the REPEAT command and draws a SQUARE using :LENGTH parameter.

Line 4) SquareRecursion :LENGTH / 2 :RecursionStep – 1

Call the procedure SquareRecursion with parameters Length = :LENGTH/2 and parameter RecursionStep = RecursionStep -1.

As a result, the next square drawn by the program will have half the side length of the original square. This call also decrements the parameter “RecursionStep” by 1.

Thus, at each recursion step, the program reduces the square’s length to half and reduces the Number of recursion counts by 1.

According to the test condition in step 2)

IF :RecursionStep = 0 [STOP]

the recursion stops when the “RecursionStep” count reaches zero after several recursion calls.

The Main Program

Line 5) SquareRecursion 200 4

This is the main program. SquareRecursion 200 4 statement calls the procedure

SquareRecursion :LENGTH :RecursionStep

The call passes the parameter “RecursionStep” as 4, meaning we want the program to do four recursion calls. It also passes the parameter LENGTH = 200 for the length of the first square as 200. 

Since the parameter “RecursionStep” is decremented by one at each recursive call, the parameter “RecursionStep” will reach zero after four recursion calls. When that happens, the statement (step 2)

IF :RecursionStep = 0 [STOP]

will stop further recursion calls and stop the program.  The final shape drawn by the program is four squares with sides 200, 100, 50, and 25.

The following is the screen shot of the above recursion program.

Draw Spiral Using Recursion

Let us now write a recursion program to draw a spiral. The program’s name is SpiralRecursion. It uses one parameter ‘n’ as defined in the TO statement

TO SpiralRecursion :n.

PROGRAM EXAMPLE: DRAW SPIRAL USING RECURSION

TO SpiralRecursion :n ;Line 1) Define procedure with parameter 'n'.
   IF :n < 1 [stop] ;Line 2) Stop calls to procedure SpiralRecursion if n < 1
   FORWARD :n       ;Line 3)
   RIGHT 20
   SpiralRecursion 0.97 * :n ;Line 4) Recursive call to procedure SpiralRecursion.
END
;Main program below.
SPIRAL 50           ;Line 5) 
;Call procedure SpiralRecursion with parameter n = 50

The following is the program output.

Detailed Explanation of the program:

Line 1) TO SpiralRecursion :n

Define a procedure “SpecialRecursion” with one parameter “n”

Line 2) IF :n < 1 [STOP];

At each recursive call to procedure “SpiralRecursion”, keep on multiplying the variable “n” by 0.97. (See step 4). If the parameter “n” decrements to less than 1, stop calling the recursive procedure ‘SpiralRecursion’.

Line 3) FORWARD :n  RIGHT 20

Move the turtle forward by amount “n” and turn right by 20 degrees.

Line 4) SpiralRecursion 0.97 * :n

Call procedure “SpiralRecursion” while multiplying parameter “n” by 0.97.

The Main Program

Line 5) SpiralRecursion 50

The main program is just one line. It makes a call to procedure “SpiralRecursion” with parameter n = 50. Recursive call stops when n * 0.97 * 0.97 * 0.97 *…….. is less than 1.

Fibonacci Sequence

Fibonacci Sequence is a sequence of numbers with the property that any number in the sequence is the sum of two numbers just before it.

For example, if 1 and 1 are the first two numbers in the sequence, then the third number is the sum of  1 + 1, that is 2. So, the Fibonacci Sequence becomes [1 1 2]. 

The next number in the sequence is the sum of 1 and 2, that is 1 + 2 = 3.  So, the Fibonacci sequence becomes {1 1 2 3]. 

The next number in the sequence is the sum of 2 and 3 = 5.  The sequence is now [ 1 1 2 3 5]. 

Now you can see the next number in the sequence is 3+ 5, which is 8. The next number is the sum of 5 and 8 = 13.

So, the Fibonacci Sequence so far is [1 1 2 3 5 8 13]. 

You can continue using this algorithm and keep on creating the next numbers in the Fibonacci Sequence.

Using the above algorithm, let us write a LOGO program using recursion to create Fibonacci Numbers.

The Fibonacci Sequence is discussed in much more detail in the Python section of this website in the Math Applications chapter, where we create Fibonacci numbers using Python programming language.

Fibonacci Sequence Program Generation

The program starts with defining a procedure using the TO command that uses one parameter :N, where N is the location of the number in the Fibonacci sequence.

The number at location N=1 is 1. The number at location N = 2 is 1.  The number in location N = 3 is 2, and so on.  The number at location N = 0 is defined as 0.

As indicated above, any Fibonacci number at location N can be created by adding the previous two Fibonacci numbers.  The program uses this fact in statement in Line 4)

(FIB :n – 1) +  (FIB :n -2)

PROGRAM EXAMPLE: FIBONACCI SEQUENCE USING LOGO

; Define procedure FIB using TO command
TO FIB :N           ; Line 1)
; Below are the procedure statements.
IF :N = 0 [output 0] ; Fibonacci number at location 0 is defined as 0.; Line 2)
IF :N = 1 [output 1] ; The First Fibonacci number in the sequence is 1.; Line 3)
OUTPUT (FIB :n - 1) + (FIB :n - 2); Line 4)
END
; Procedure end
;The following statements call the FIB :N procedure.
PRINT fib 0 ; Call the FIB procedure for N = 0
0
PRINT FIB 1; Call the procedure FIB for N = 1
1
PRINT FIB 2: Call the procedure FIB for N = 2.
1
PRINT FIB 3; Call the procedure FIB for N = 3.
2
PRINT (FIB 4); Call the procedure FIB for N = 4
3
PRINT (FIB 5); Call the procedure FIB for N = 5.
5
PRINT (FIB 6); Call the procedure FIB for N = 6.
8
PRINT (FIB 7); Call the procedure FIB for N = 7
13

SHOW FIB 7; Call the procedure FIB for N = 7.  Use SHOW command.
13

(PRINT FIB 1 FIB 2 Fib 3 Fib 4 Fib 5 FIB 6 FIB 7 Fib 8)
1 1 2 3 5 8 13 21

So, the Fibonacci Sequence generated by the program is 1, 1, 2, 3, 5, 6, 13, 21…….

Note that each number in the sequence is sum of the preceding two numbers.

The following section introduces the subject of Fractals. The Fractals can be created using recursion, which we discussed in the above sections.

Self-similarity and Fractals

Two shapes are called self-similar if they are similar to each other at all scales (magnification). Thus, a zoomed-in portion of a small portion of a shape looks similar to the whole shape.

This self-similarity occurs in nature such as in leaves of trees, snowflakes, spirals of pinecones, broccoli, etc. 

Why do we study self-similarity?  Because it opens up a new field of mathematics called FRACTALS.

What Are Fractals

A fractal is a geometric shape in which each part of that shape is approximately a reduced-size copy of the whole shape. Every part of the fractal, regardless of how zoomed-in (magnified using a magnifying glass), or zoomed-out, looks very similar to the whole image. Thus, every part of the Fractal pattern appears similar at all levels of magnification.

A fractal is a never-ending pattern that repeats itself indefinitely at smaller and smaller scales. Fractals are created by repeating a function over and over again using recursion. 

The fractal algorithm starts at a desired dimension and uses recursion to reduce the dimension by a desired factor at each step of the recursion loop. The first recursion step is denoted by depth = 1. The second recursion step corresponds to depth = 2, and so on.

Self-similarity and fractals are presented at length in the Turtle 2 section of the website in Chapter Recursion and Fractals.

Sierpinski Triangle

Sierpiński triangle is a famous example of fractals and self-similarity.  The Sierpiński Triangle is a self-similar fractal. It consists of an equilateral triangle from which smaller equilateral triangles (self-similar triangles) are removed recursively at each recursion loop. This process can be continued indefinitely with ever-decreasing smaller triangles removed from the previous recursion step’s larger triangles. 

More details of the Sierpiński Triangle are in Turtle 2 section of this website in the chapter Recursion and Fractals.

The program below uses a recursive procedure defined by the statement:

TO SIERPINSKI :LENGTH :RecursionStep;  

The TO statement uses two parameters called “LENGTH” and “RecursionLevel”.  As in the previous recursive procedure example, we use the IF condition to stop the recursion calls, when the IF condition tests True.

More information on Sierpinski Triangle is here and here.

PROGRAM EXAMPLE: SIERPINSKI TRIANGLE USING LOGO

TO SIERPINSKI_A :LENGTH :RecursionLevel ;1)

IF :RecursionLevel > 0 [ 
    RIGHT 30
    REPEAT 3 [FORWARD :LENGTH RIGHT 120 ] ;2)
    LEFT 30
SIERPINSKI_A :LENGTH / 2 :RecursionLevel - 1 ;3)
    RIGHT 30
    FORWARD :LENGTH / 2
    LEFT 30
SIERPINSKI_A :LENGTH / 2 :RecursionLevel - 1 ; 4)
    RIGHT 30
    BACK :LENGTH / 2
    RIGHT 60
    FORWARD :LENGTH / 2
    LEFT 90
SIERPINSKI_A :LENGTH / 2 :RecursionLevel - 1 ; 5)
    LEFT 90
    FORWARD :LENGTH / 2
    RIGHT 90
    ]

end    :6)

; The main program
sierpinski_A 300 4       ;7)

Detailed Step-by-Step Description of the Program:

Step 1) TO SIERPINSKI_A :LENGTH :RecursionLevel

Define a procedure SIERPINSKI_A with two parameters LENGTH and RecursionLevel.  LENGTH is the length of the equilateral triangle.  RecursionLevel is the number of recursion calls that the main program makes to the SIERPINSKI_A procedure.

Step 2) REPEAT 3 [FORWARD :LENGTH RIGHT 120]

Draw an equilateral triangle of side length 300 pixels as specified by the main program in step 7). The angle is specified as 120,degrees since the external angle of an equilateral triangle is 120 degrees.

Step 3) SIERPINSKI_A :LENGTH / 2 :RecursionLevel – 1

Step 3) makes a recursion call to the procedure SIERPINSKI_A. The call specifies the length of the new triangle as half the original triangle’s length. It also decrements the RecursionLevel by 1.

Step 4) SIERPINSKI_A :LENGTH / 2 :RecursionLevel – 1

The step 4) is similar to step 3) except it is done on the second side of the original triangle. It makes a recursive call to procedure SIERPINSKI_A and decrement the parameter RecursionLevel by 1.

Step 5) SIERPINSKI_A :LENGTH / 2 :RecursionLevel – 1

The step 5) is similar to step 3) except it is done on the third side of the original triangle.

The Main Program

At each recursion call, the procedure SIERPINSKI_A divides the parameter LENGTH by 2. This results in the drawn triangle to be half the size. It also decrements the parameter RecursionLevel by 1 at each recursion call.

The main program continues to make recursion calls to the SIERPINSKI_A procedure as long as the parameter RecursionLevel value is greater than zero.

If the main program calls the Sierpinski_A procedure specifying RecursionLevel as 4, no further recursive calls are made by the main program to the SIERPINSKI_A procedure after four recursion calls have been made.

The following figures are the outputs of the SIERPINSKI_A procedure with RecursionLevel = 5, 4, 3, and 2.

For RecursionLevel = 5, the program drew triangles of five sizes. With each recursion call, the triangles are half the size of the triangles of the previous recursion step.

For RecursionLevel = 4, the program made four recursion calls.

For RecursionLevel = 3, the program made three recursion calls.

For RecursionLevel = 2, the program made two recursion calls.

Copyright © 2019 – 2021 softwareprogramming4kids.com

All Rights Reserved