Recursive Algorithms

Recursion is a natural part of functional programming. The classic functional data structure---the single linked list---is recursive in nature. We can similarly create interesting drawings using recursion.

Let's start with a simple example---a set of concentric circles. We can create this image by recursing over the natural numbers. Each number corresponds to the next layer of the image:

Note the recursive pattern here:

• the n = 1 case is the base case;

• every other case is the n - 1 case (shown in black) surrounded by an extra circle (shown in red).

Given these two rules, we can generate a picture for any value of n >= 1. We can even model the rules directly in Scala:

def concentricCircles(n: Int): Image =
  if(n == 1) {
    // Return a circle
  } else {
    // Return a circle superimposed on the image from n - 1
  }

Exercise: Concentric circles

Create an image containing 20 concentric circles using the approach described above:

For extra credit, give each circle its own hue or opacity by gradually changing the colour at each level of recursion:

<div class="solution"> The basic structure of our solution involves two methods: one for drawing a single circle and one for drawing n circles:

def singleCircle(n: Int): Image =
  ???

def concentricCircles(n: Int): Image =
  if(n == 1) {
    singleCircle(n)
  } else {
    singleCircle(n) on concentricCircles(n - 1)
  }

concentricCircles(20)

There is a clean division of labour here: concentricCircles handles the recursion through values of n and the composition of the shapes at each level, while singleCircle decides which actual shapes we draw at each level.

Here is the implementation of singleCircle we need to draw monochrome circles. We calculate an appropriate radius from the value of n provided. The n = 1 circle has radius 55 and each successive circle is 5 pixels larger:

def singleCircle(n: Int): Image =
  Circle(50 + 5 * n)

To create multicolour circles, all we need to do is modify singleCircle. Here is an implementation for the extra credit example above:

def singleCircle(n: Int): Image =
  Circle(50 + 5 * n) strokeColor (Color.red spin (n * 10).degrees)

Here is another implementation that fades out the further we get from n = 1:

def singleCircle(n: Int): Image =
  Circle(50 + 5 * n) fadeOut (n / 20).normalized

We can make countless different images by tweaking singleCircle without changing the definition of concentricCircles. In fact, concentricCircles doesn't care about circles at all! A more general naming system would be more suitable:

def singleShape(n: Int): Image =
  ???

def manyShapes(n: Int): Image =
  if(n == 1) singleShape(n) else (singleShape(n) on manyShapes(n - 1))

</div>

Exercise: Sierpinski triangle

Sierpinski triangles are a more interesting example of a recursive drawing algorithm. The pattern is illustrated below:

Here is an English description of the recursive pattern:

• The base case for n = 1 is an equilateral triangle. We can draw this in Doodle as follows:

  Triangle(10, 10)

• Every other case involves three copies of the n - 1 case arranged in a triangle.

Use this description to write Scala code to draw a Sierpinski triangle. Start by dealing with the n = 1 case, then solve the n = 2 case, then generalise your code for any value of n. Finish by drawing the n = 10 Sierpinkski triangle below:

You may notice that the final result is extremely large! For extra credit, rewrite your code so you can specify the size of the triangle up front:

def sierpinski(n: Int, size: Double): Image = ???

Finally, for double extra credit, answer the following questions:

1. How many pink triangles are there in your drawing?

1. How many Triangle objects is your code creating?

1. Is this the answer to question 2 necessarily the same as the answer to question 1?

1. If not, what is the minimum number of Triangles needed to draw the n = 10 Sierpinski?

<div class="solution"> The simple solution looks like the following:

def triangle: Image =
  Triangle(1, 1) strokeColor Color.magenta

def sierpinski(n: Int): Image =
  if(n == 1) {
    triangle
  } else {
    val smaller = sierpinski(n - 1)
    smaller above (smaller beside smaller)
  }

sierpinski(10)

As we hinted above, each successive triangle in the Sierpinski pattern is twice the size of its predecessor. Even if we start with an n = 1 triangle of side 1, we end up with an n = 10 triangle of side 1024!

The extra credit solution involves specifying the desired size up front and dividing it by two each time we recurse:

def triangle(size: Double): Image =
  Triangle(size, size) strokeColor Color.magenta

def sierpinski(n: Int, size: Double): Image =
  if(n == 1) {
    triangle(size)
  } else {
    val smaller = sierpinski(n - 1, size / 2)
    smaller above (smaller beside smaller)
  }

sierpinski(10, 512)

Finally let's look at the questions:

First, let's consider the number of pink triangles. There is one triangle in the n = 1 base Sierpinski, and we multiply this by 3 for each successive level of recursion. There are 3^9 = 19,683 triangles in the n = 10 Sierpinski!

That's a lot of triangles! Now let's consider the number of Triangle objects. This question is designed to highlight a nice property of immutable data structures called structural sharing. Each Sierpinski from n = 2 upwards is created from three smaller Sierpinskis, but they don't have to be different objects in memory. We can re-use a single smaller Sierpinski three times to save on computation time and memory use.

The code above actually shows the optimal case. We use a temporary variable, smaller, to ensure we only call sierpinski(n - 1) once at each level of recursion. This means we only call triangle() once, no matter what value of n we start with.

We only need to create one Triangle object for the whole picture! Of course, the draw method has to process this single triangle 19,683 times to draw the picture, but the representation we build to begin with is extremely efficient. </div>