COSC122 Lab 4

Recursion

Goals

This lab will give you some practice with several problems that can be solved using recursion, and a

number of recursive algorithms. In this lab you will:

• compute a number of simple problems (factorials, exponentiation, etc.) using recursive functions;

• have more fun with linked lists (or at least improve your understanding of linked lists);

• compare iterative and recursive solutions and think about where recursive methods are (in)appropriate;

• experiment with, and draw fractals.

You should be familiar with the material in Chapter 4 of the textbook (online link here) before attempting this lab.

The recursion.py module has a number of functions and function stubs for solving simple problems recursively.

Fibonacci Numbers

A Fibonacci number is a number that features in the Fibonacci sequence of numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Given that the first two numbers are 1 and 1 (the 1st and 2nd numbers, respectively), all other numbers in the sequence are calculated as the sum of the last two numbers. For example, the 5th Fibonacci

number is the 3rd + the 4th (2+3 = 5).

def fib_iterative(n):

if n == 0:

return 0

elif n == 1:

return 1

else:

fib_n_minus2 = 0

fib_n_minus1 = 1 # start with fib of 2 which equals 1

for i in range(1,n): # there will be n+1 numbers including the 0’th

curr_fib = fib_n_minus1 + fib_n_minus2

fib_n_minus2 = fib_n_minus1

fib_n_minus1 = curr_fib

return curr_fib

Try calculating various Fibonacci numbers with fib_iterative, eg, 5, 10, 100, 1000, 2000, 10000.

You will see that the fibonacci numbers become very large. Luckily Python can handle such large integers but we might need to think about how much space such numbers will take up.

It is far more elegant to solve this problem recursively. Think about solving f i b(4) as ‘f i b(3) +

f i b(2)’, and solving f i b(3) as ’f i b(2) + f i b(1)’, and so on. . .—that is, solving f i b(n) is the same as

‘f i b(n − 1) + f i b(n − 2)’. The recursive version has been implemented for you in the fib_recursive

function in the recursion.py module.

While running the method fib_recursive, try to inspect how the Python stack behaves (as explained in the lectures).

Try calculating the following Fibonacci numbers using fib_recursive: 5, 10, 20, 30, 40. You will

find that although recursion is elegant, in this case it isn’t so efficient. 1

1

In fact, to calculate the nth fibonacci number, the number additions will be roughly equal to the fibonacci number being

calculated – and this grows very fast, ie, the function will be O(2n

) – think about why. The iterative version can be used to see how

many additions the recursive version would be doing for large n’s.

To see why the recursive method gets out of hand, try drawing the start of the tree of calls from

fib_recursive(10) – don’t go all the way down to fib_recursive(0) though. For example, fib_recursive(10)

calls fib_recursive(9) and fib_recursive(8), then fib_recursive(9) calls fib_recursive(8)

and fib_recursive(7), etc…

The recursive function definition for quick_power is given below:

x

n =

1 if n is 0

(x

n/2)

2

if n is even

x.x

n−1

if n is odd

> Complete the Hand cranked recursion questions in Lab Quiz 4.

Recursive Implementations

Your should now open recursion.py module and complete the functions that are missing implementations—

referring back to this section for extra information.

When thinking about how to write these functions, you need to think of a base case where the

method does not recurse any further, and each time it calls itself, it must move towards the base case.

Linked lists are recursive

Using recursion to traverse linked listed is more natural than iteration (eg, the while loops that were

used in the linked list lab). This is because you can think of a linked list as a recursive structure—the

whole list is simply the current node followed by the list starting at the current node’s next node. For

example, to print a list starting at node1 we simply need to print the data in note1 and then print the rest

of the list, which is simply the list starting from the next node in the list (ie, starting at node1.next_node).

Once you have your recursive print function working compare it with the print functions for printing

stacks and queues in the linked list lab.

Good compilers/interpreters will usually turn such simple tail recursion in to iteration for efficiency

so we get the elegance of recursion with the efficiency of iteration. Unfortunately Python doesn’t do

well in this area, so be careful to only use recursion where it isn’t likely to cause stack blow-outs.

> Complete the Recursion with linked lists questions in Lab Quiz 4.

The problem with slicing

Suppose you have written a recursive sum function such as the following:

def sum(data):

if len(data) == 0:

return 0

else:

return data[0] + sum(data[1:])

The problem with such a function is that it will have quadratic complexity because evaluating data[1:]

involves copying the entire list except the first item. Using string slicing in a similar fashion will cause

the same problem, eg, see your simple recursive string print function. Imagine if you had a list of cars

to wash and each time you washed a car you generated a new list of cars still to wash by rewriting the

whole list but without the id of the car you had just washed – surely it would be easier to simply cross

out the car you had just washed and move on to the next car in the list.

The solution to this problem is to pass the same unmodified list to all recursions and pass additional

parameter(s) to select which portion of that list the function should be operating on. For example:

def sum(data , start=0):

if len(data) <= start:

return 0

else:

return data[start] + sum(data , start + 1)

2

The quadratic complexity isn’t quite as much of a problem as you might expect, because the default

maximum recursion depth of 1000 tends to kill the run before the quadratic complexity becomes too

much of a problem. However, for reasons that we won’t go into here, when doing dynamic programming

we do not want to pass a different list to each recursive call. So let’s re-do a few of the questions with

the added constraint that, when passing lists around, you must always pass the same list to all recursive

calls, ie, you must never extract sub-lists using slicing. You will either need to add extra parameters with

default values, as above, or call a support function for the main task where the support function has

extra parameters.

> Complete the Recursion with Python lists and strings questions in Lab Quiz 4.

Fractals

A fractal is a geometrical shape that possesses an infinite level of detail. They are generated through a

repeating pattern, such that zooming into them reveals smaller versions of the larger whole. One of the

most popular examples of this is the Mandelbrot set, shown in Figure 1; zooming into the Mandelbrot

set reveals an incredible level of geometric complexity and eventually, smaller versions of the entire set

again.

While fractals may seem very complicated, their final form after many iterations simply masks the

simple drawing instructions that they are built on.

(a) (b) (c) (d)

Figure 1: Zooming into the Mandelbrot set; from http://en.wikipedia.org/wiki/Mandelbrot_

set.

Turtle Graphics

The fractals we’re going to be looking at can be drawn using a technique known as turtle graphics. In

turtle graphics, you move a robotic pen across a canvas by issuing it simple commands—such as ‘move

forwards’, ‘turn left’, ‘lift up’, etc. Think about strapping a pen underneath a turtle and walking the turtle

around—going forwards, turning left or right, etc. Python comes with the turtle module that allows

you to easily use a turtle to draw. Try this out in the shell:

from turtle import *

shape(“turtle”) # Shapes the pen like a turtle

forward(50)

left(90) # The parameter is the number of degrees to turn

forward(50)

left(90)

forward(50)

right( -90) # This is the same as left(90)

forward(50)

As soon as you call shape, a Python Turtle Graphics window will appear. You can resize this window and

keep typing commands into the shell (use reset() to re-centre the turtle in the window)—the turtle

in the graphics window will move in response to your commands, leaving a trail behind it. You should

now have a small square in the graphics window. You can do anything you want with the turtle. Check

out the spiral below:

3

from turtle import *

for i in range(1 ,60):

width(i/4)

forward(i)

right(30)

NOTE: If you close the turtle window manually (by clicking on the close button) then it may crash.

In this case you will need to restart the shell in Wing. To do this click on the options button (top right of

Shell window in Wing) and select restart shell.

The commands should be simple enough for you to follow with a pen and paper if you find the code

a bit confusing. See help(RawTurtle) or the Python Manual2

for a complete list of commands you can

issue to the turtle.

A simple introductory fractal is a tree (this code is included in recursion.py):

from turtle import *

from random import *

def random_tree(size , level):

if level > 0:

forward(random() * size)

x = pos()

angle = random() * 20

right(angle)

random_tree(size * 0.8, level – 1)

setpos(x)

left(angle)

angle = random() * -20

right(angle)

random_tree(size * 0.8, level – 1)

left(angle)

setpos(x)

random_tree(100 ,5) # draw a random tree

The fractals.py module contains the FractalCanvas class that sets up a simple user interface for

drawing fractals, including a turtle. The fractal_drawing module is where you will be implementing

sub-classes of the Fractal class that actually do some drawing.

> Complete the Bring out the Turtle question(s) in Lab quiz 4.

The Sierpinski Triangle

The fractal_drawing module contains a complete SierpinskiTriangle class, and some code at the

very bottom for setting up Tkinter. Running the module as-is should produce a window like that shown

in Figure 2.

This fractal is known as the Sierpinski triangle—built from a repeating set of triangles within other

triangles. If you click on the Draw Fractal button (at the top of the window), it will show you the construction of the triangle. You can also adjust the parameter to the SierpinskiTriangle constructor at

the bottom of the module to change how many levels of triangles are drawn—but be warned: drawing

becomes very slow after around 7 levels; think about how many triangles are being drawn!

The ‘level’, or degree of a fractal is a count of how many times it recurses into itself. In this case, it is

drawing five levels of triangles stacked inside each-other.

The draw method in SierpinskiTriangle sets up some basic parameters for the drawing—the

co-ordinates of the outer triangle, the colours to use, and resetting the turtle. draw_triangle is where

the recursive drawing happens:

1. It draws a triangle for the points it has been given (for the first level, these are the points for the

outer triangle).

2. If there are more levels to draw. . .

2http://docs.python.org/library/turtle.html

4

Figure 2: The Sierpinski triangle drawn to 5 levels.

3. . . . calculate the points for the three inner triangles, and call draw_triangle to draw them.

Take a moment to experiment with the Sierpinski triangle to understand its drawing code before continuing.

> Complete the Sierpinski Triangles question(s) in Lab quiz 4.

The Koch Snowflake

The Koch snowflake is one of the oldest fractal curves; constructed by repeatedly dividing the sides of

an equilateral triangle into thirds, and drawing triangles on the middle segment. Figure 3 shows the

first few iterations of the snowflake. A snowflake is actually made up of three Koch curves drawn at

120◦

angles; for this exercise we will only draw a single curve (one side of the triangle), but you can

implement a snowflake if you wish (see the Extras section).

(a) (b) (c)

Figure 3: Constructing the Koch snowflake from level 0 to 2.

The Koch Curve

The fractal_drawing module contains an incomplete KochCurve class that you will complete, based

on the procedure described below.

5

The draw method in KochCurve is completed for you, and positions the turtle on the screen at the

vertical centre of the left edge; it then calls draw_koch with the number of levels to draw, and the length

of the curve.

The drawing algorithm for the curve is:

• If we’re at the lowest level of the curve (level 0), move forward by the given length (and call

self.update_screen()).

else

• Divide the length by 3.

• Draw the curve for the next level (ie, level – 1).

• Turn left 60◦

.

• Draw the curve for the next level.

• Turn right 120◦

.

• Draw the curve for the next level.

• Turn left 60◦

.

• Draw the curve for the next level.

Try tracing these instructions out on a piece of paper for the first couple of levels to get a better

feeling for what your turtle will be doing.

Figure 4: The Koch curve drawn to four levels.

Implement these drawing instructions in the draw_koch method, using the self.turtle object as

your turtle. Remember that the levels decrease as you decend into deeper levels of the curve, and you

should stop when you hit the base case.

Change the code at the bottom of the module to create a new instance of KochCurve instead of

SierpinskiTriangle and run the code. If you implemented everything correctly, you should see

something similar to Figure 4 draw on the screen.

> Complete the Koch Curves question(s) in Lab quiz 4.

6

Extra Exercises

• Write a recursive function that appends an item to the end of a linked list.

• A Koch snowflake is three Koch curves drawn at 120◦

angles to each other (a triangle). Implement

a KochSnowflake class that draws this fractal.

• A Koch starflake is just like the snowflake except with the Kochcuve angle changed to 80 degrees.

Implement a KochStarflake class that draws this fractal. We have provided some extra code in

the method and you should be able to copy in your code from the snowflake and update it. Have

a play with the number of turns that the starflake makes.

• Add some colour to your fractals to indicate some parameter such as the level or age of the line

being drawn (for example, SierpinskiTriangle draws deeper levels of the triangle in darker

shades). You can set the colour of the turtle by calling its pencolor() method with the RGB

values (0–255), for example: self.turtle.pencolor(0, 0, 255) is blue.

• Implement a class for drawing a Hilbert curve (see below).

• Implement a class for drawing a Dragon curve (see below).

The Hilbert Curve

The Hilbert curve is a type of fractal known as a space-filling curve—given a square grid of points, it will

draw a single line that runs through every point exactly once.

The construction of a Hilbert curve is shown in Figure 5. The first iteration in Figure 5a covers all

points in a 2 × 2 grid. If we double the size of the grid to 4 × 4 we take the first iteration, and place it

in the corners of the 4 × 4 grid—the lower two are placed as-is, the upper two are rotated 90◦

left and

right, respectively—with connecting lines added between the shapes (Figure 5b). If we want to double

the size of the grid again, we repeat this procedure using the last iteration (Figure 5c).

(a) (b) (c)

Figure 5: Constructing the Hilbert curve to 3 levels.

7

The drawing algorithm for this curve is:

• If level is 0 then do nothing. That was easy. . .

else

1. Turn to the right by the given angle.

2. Draw the curve for the next level (ie, level – 1).

3. Move forward to create a connecting line.

4. Turn to the left by the given angle.

5. Draw the curve for the next level.

6. Move forward to create a connecting line.

7. Draw the curve for the next level.

8. Turn to the left by the given angle.

9. Move forward to create a connecting line.

10. Draw the curve for the next level.

11. Turn to the right by the given angle.

As you decend into deeper levels, the angle you will need to turn will alternate between 90 and −90 to

get the inner curve orientated properly. That is, make the recursive call with draw_hilbert(level-1,

-angle) for the first and last call to draw_hilbert from within draw_hilbert and simply use draw_hilbert(level-1,

angle) for the other two calls. . . phew, recursion can be hard to explain! Don’t worry it will be fun playing around with the method and seeing the weird and wonderful shapes you can generate.

The Dragon Curve

The Dragon curve is another type of fractal that draws its name from its similarity at high levels to the

mythical creature. It is drawn by taking a line and replacing it with two lines at 45◦

angles to the original

line; this process is repeated on the new line segments, alternating the side at which the new lines are

drawn on. Figure 6 shows the first few iterations of this process.

The fractal_drawing module contains an incomplete DragonCurve class that you will complete,

based on the procedure described below.

The drawing algorithm for the curve is:

• If we’re at the lowest level of the curve (level 0), move forward by the given length (and call

self.update_screen()).

else

• Divide the length by 1.4 (to fit the curve on the screen).

(a) (b) (c) (d)

Figure 6: Levels 1–4 of the Dragon curve (level 0 is a straight line).

8

(a) (b)

Figure 7: The Dragon curve drawn to (a) 5 and (b) 15 levels.

• Turn right, using the current value of angle.

• Draw the next dragon level with angle set to 45◦

(ie, level – 1)

• Turn left by 2 times the angle.

• Draw the next dragon level with angle set to −45◦

.

• Turn right by the value of angle.

The draw_dragon method takes in three parameters: the level of the curve, the length to draw the

current segment at, and the angle to turn; this angle determines whether we are dividing current line

segment with new lines on either its left or right.

Using the instructions above, implement the draw_dragon method using the self.turtle obejct

as your turtle. Remember that the levels decrease as you descend deeper into the curve, and to check

for the base case.

Change the code at the bottom of the module to create a new instance of DragonCurve and run the

code. If you implemented everything correctly, you should see something similar to Figure 7a draw on

the screen. Experiment with the number of levels; the curve looks best at high levels (around 15), as

shown in Figure 7b.

> Complete the Bonus question(s) in Lab quiz 4 — relax the bonus question(s) are not marked.

9

Sale!