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