# Spirals, Snowflakes & Trees: Recursion in Pictures

Recursion is a powerful and subtle concept. A great way to gain an intuition of its structure is to visualise different patterns of recursion with graphics. In this chapter, we will use a simplified interface to the vector graphics library Rasterific to generate recursive images.

### Programming Environment Rasterific is included and ready to use in Haskell for Mac. No further installation is required. To use Rasterific with a different Haskell system, please install it by executing `cabal install Rasterific` in a command line shell.

## Simple Pictures

Previous examples already used a `Point` type to represent points in a 2-dimensional plane as a pair of floating point values denoting the point's x- and y-coordinates:

``type Point = (Float, Float)``

On top of that, we use two new definitions, `Line` and `Path`, which represent a line as a pair of the start point and end point as well as a path as a list of arbitrarily many points:

``````type Line = (Point, Point)
type Path = [Point]``````

Furthermore, a colour consists of four values, specifying the red, green, blue, and alpha (opacity) components of that colour — also known as an RGBA colour representation. The individual component values should be between 0 and 255. Bigger values and smaller values are interpreted modulo 256.

``````-- Quadruple of red, green, blue, and opacity component.
-- These values should all be between 0 and 255.
type Colour = (Int, Int, Int, Int)``````

To simplify the use of colours, we predefine constant values for some basic colours. (We can combine multiple type signatures using the same type into one by listing all value or function names, separated by commas, and then, writing the type only once.)

``white, black, blue, red, green, lightgreen, orange, magenta :: Colour``

Finally, we regard a picture as a list of pairs of `Path` and `Colour`:

``type Picture = [(Colour, Path)]``

The function `drawPicture`, applied to a `Picture` value, draws this picture on a black canvas of size 800x800, where the origin `(0,0)` is located at the left most, upmost corner, and `(800, 800)` at the right most, lower most corner.

To get you started, we provide a Haskell for Mac project including all of the above type definitions together with an implementation of `drawPicture`: Fractals.hsproj. This project includes two Haskell modules: `LineGraphics` and `Fractals`. The former contains the graphics definitions for you to use. The latter is where you can add code while working through this chapter. Just open `Fractals.hsproj` in Haskell for Mac and proceed as in the screencasts. Run GHCi inside the `Fractals.hsproj` directory after downloading and unpacking. Then, load the `Fractals` module. To visualise your drawings, you need to write them to disk as a PNG image file. To do so, use the writePng function as follows:

``writePng FILENAME (drawPicture LINEWIDTH PICTURE)``

As a first, simple example we define the paths `house` and `door`

``````house :: Path
house = [(300, 750), (300, 450), (270, 450), (500, 200),
(730, 450), (700, 450), (700, 750)]

door :: Path
door = [(420, 750), (420, 550), (580, 550), (580, 750)]``````

and then call

``drawPicture 2.0 [(lightgreen, house), (red, door)]``

where the first argument, `2.0`, specifies the line width. It will display this picture. In the following screencast, we incrementally construct the house in a playground and experiment with a few different colours.

Creating pictures by explicitly enumerating all the coordinates is tedious, though — instead, we want to write functions which do the work for us.

## Manipulating Lines and Colours

The spiral picture below is seemingly more complex than the one above, but actually takes a lot less effort to produce! The reason for this becomes clear, once we look at the picture more closely: it is composed of a set of lines, all originating at the same point. They differ in length, orientation, and colour, with the outer lines less and less opaque, but these changes clearly follow a simple pattern. This is good news, because it means once we identify the pattern, we can write a program that takes a line as argument and creates the picture. A function —let's call it `spiralRays`— drawing this spiral pattern needs to be able to perform three operations repeatedly, each of which we can implement as separate functions:

• `rotateLine :: Float -> Line -> Line`: rotate a line at its origin by a given angle.

• `scaleLine :: Float -> Line -> Line`: change the length of a line.

• `fade :: Colour -> Colour`: decrease the opacity of a colour.

A caller of the `spiralRays` function should be able to specify the number of lines in the picture, the initial line, and the initial colour (we could generalise it to also accept the rotation angle and scale factor as parameters, but let's keep it simple for now). The function `spiralRays` itself is a recursive function following the list generator pattern that we discussed in Recursion: If `spiralRays` is called with a first argument of `0`, it returns an empty list. Called with a first argument greater than 0, it returns the current line as the first element of the result list, and as tail, the result of the recursive call on `n - 1`, with a faded colour, and a rotated and scaled line:

``````spiralRays :: Int -> Colour -> Line -> Picture
spiralRays n colour line@(p1, p2)
| n <= 0    = []
| otherwise = (colour, [p1, p2]) : spiralRays (n - 1) newColour newLine
where
newLine   = scaleLine 1.02 (rotateLine (pi / 40) line)``````

The third argument pattern of `spiralRays` uses an `@`-pattern (pronounced, “at pattern”). Here, we are using `line@(p1, p2)`, which at once binds the variable `line` to the third argument and the two variables `p1` and `p2` to the first and second component of the pair that represents the line. This is convenient as we want to refer to the line as whole (as `line` in the calculation of `newLine`), but also to its components `p1` and `p2` when constructing the path of length two for the first picture `[p1, p2]`.

Now, that we discussed the overall recursive structure, let us look at the three functions `rotateLine`, `scaleLine`, and `fade` in turn.

Rotation. Dusting off our school geometry knowledge (or doing a quick web search) tells us that rotating a line `((0, 0), (x, y))` by a given angle `alpha` around the origin results in a line `(0, 0), (x', y'))` where Writing out the matrix-vector multiplication, we get

``````x' = x * cos alpha - y * sin alpha
y' = x * sin alpha + y * cos alpha``````

``````rotateLine :: Float -> Line -> Line
rotateLine alpha ((0, 0), (x, y))
= ((0, 0), (x', y'))
where
x' = x * cos alpha - y * sin alpha
y' = x * sin alpha + y * cos alpha``````

In general, though, we want to rotate lines that do not start at the origin `(0, 0)`. Nevertheless, we want to perform the rotation around the first point of the line (i.e., its starting point). We achieve this by first moving the line to the origin (by subtracting the `x1`- and `y1`-values of the starting point), then rotating the resulting line using the above calculation, and finally, moving the rotated line back to its original starting point. Overall, we get

``````rotateLine :: Float -> Line -> Line
rotateLine alpha ((x1, y1), (x2, y2))
= ((x1, y1), (x' + x1, y' + y1))
where
x0 = x2 - x1
y0 = y2 - y1
x' = x0 * cos alpha - y0 * sin alpha
y' = x0 * sin alpha + y0 * cos alpha``````

Scaling. To scale a line by a given factor, we also shift it to start at the origin `(0, 0)`, then multiply the `x2`- and `y2`-values of the endpoint of the shifted line with the scaling factor, and finally, shift the line back to its actual starting point:

``````scaleLine :: Float -> Line -> Line
scaleLine factor ((x1, y1), (x2, y2))
= ((x1, y1), (x' + x1, y' + y1))
where
x0 = x2 - x1
y0 = y2 - y1
x' = factor * x0
y' = factor * y0``````

Fading. The `fade` function simply substracts `1` from the opacity component of the colour:

``````fade :: Colour -> Colour
= (redC, greenC, blueC, opacityC - 1)``````

Generalising. To keep matters simple, our implementation started with a constant angle and scale factor. Let's generalise this now. We can approach this in two ways. Firstly, we can pass the two additional arguments on to the recursive calls:

``````spiralRays :: Float -> Float -> Int -> Colour -> Line -> Picture
spiralRays angle scaleFactor n colour line@(p1, p2)
| n <= 0 = []
| otherwise = (colour, [p1, p2]) : spiralRays angle scaleFactor (n - 1) newColour newLine
where
newLine   = scaleLine scaleFactor (rotateLine angle line)``````

However, since these two parameters stay constant during the recursion, another, more elegant option, is to define a local function that performs the recursion and which doesn't explicitly pass the angle and scale factor as arguments:

``````spiralRays :: Float -> Float -> Int -> Colour -> Line -> Picture
spiralRays angle scaleFactor n colour line
= spiralRays' n colour line
where
spiralRays' n colour line@(p1, p2)
| n <= 0 = []
| otherwise = (colour, [p1, p2]) : spiralRays' (n-1) newColour newLine
where
newLine   = scaleLine scaleFactor (rotateLine angle line)``````

By changing colour, angle, and scaling factor, we can generate many different pictures with this one recursive function.

The following screencast illustrates the use of the `spiralRays` and will give you an idea of the possible variations.

The orange spiral at the beginning of the section was generated by modifying the calculation of the `newColour` by calling the `fade` function in the calculation of `newColour` only on every third recursive step, where `mod` calculates the remainder of division on integral numbers — i.e., we used

``newColour = if (n `mod` 3 == 0) then fade colour else colour``

All images so far used integer fractions of `pi` for the rotation angle. By using other fractions, we can achieve a whole range of different effects:

You can add more interesting colour effects by replacing the `fade` function with other colour manipulation operations — for example, one which gradually cycles through the colour spectrum. Or you can slowly increase or decrease the rotation angle - even with this simple function, we have a huge number of possibilities to produce all kind of interesting effects. The following screencasts demonstrates some colour effects by modifying `fade`.

## Drawing Spirals and Polygons

If we change our `spiralRay` function, such that, instead of all lines having the same starting point, each lines starting point is the end point of the previous line, we get a spiral shaped path. To this end, we need another helper function, `connectLine`. It takes two lines and moves the second line's starting point to the end point of the first, without changing the length or orientation of the line:

``````connectLine :: Line -> Line -> Line
connectLine (_, pE) line2 = startLineFrom pE line2``````

Here we use a bit of new Haskell syntax: the underscore (`_`) in the pattern for the first line is a so-called anonymous variable: since we don't use that component of the line, we don't need to come up with a name for it; instead, we can just call it `_`. We can use anonymous variables repeatedly within the same pattern. In addition to the convenience, this notation also increases the readability of the code, as an anonymous variable signals to the reader that the result of the function does not depend on that part of the input.

The function `connectLine` defers the actual work to `startLineFrom` (where we use an `@`-pattern again):

``````startLineFrom :: Point -> Line -> Line
startLineFrom startPoint@(x0, y0) ((xS, yS), (xE, yE))
= (startPoint, ((x0 + xE - xS, y0 + yE - yS))) ``````

Now we already have everything in place to implement the new `spiral` function. For now, it returns just a single `Path`, not a `Picture`, and hence, is independent of the colour choice:

``````spiral :: Float -> Float -> Int -> Line -> Path
spiral angle scaleFactor n line
= spiral' n line
where
spiral' n line@(p1, p2)
| n <= 0    = []
| otherwise = p1 : spiral' (n - 1) newLine
where
newLine = connectLine line (scaleLine scaleFactor (rotateLine angle line))``````

As with `spiralRays`, this function produces regular looking spirals for angles which are integer fractions of `pi`.

It produces more chaotic patterns for other angles.

For a scaling factor of one (that is, the lines are all the same length) and angles that are integer fractions of `pi`, the resulting path is simply a polygon, so we can define a polygon function in terms of `spiral`:

``````polygon :: Int -> Line -> Path
polygon n line | n > 2 = spiral rotationAngle 1 (n + 1) line
where
rotationAngle = (2 * pi) / (fromIntegral n)``````

To generate even more varied spirals, we could generalise `spiral` to change the angle in each recursive step by a given factor (instead of using a constant angle), or we could generate multi-coloured spirals. The latter change would require, though, that we pair each line as a path with a colour, instead of returning the spiral as one single path. The following screencasts illustrates a few of the possible variations.

## Koch Snowflakes

Fractals are patterns which keeps repeating themselves in the same or similar forms. Fractal-like patterns can be found in nature, for example, the florets of cauliflower, or the leaves of a fern.

Koch-snowflakes (after the Swedish mathematician Helge von Koch) are one of the simplest examples of such patterns. They are constructed by starting from an equilateral triangle, and then, in each iteration, adding an equilateral triangle of a third of the size of the previous one the middle of each line, and then, removing the line that the new triangle and the base line share.

In pictures, we proceed as illustrated in the following display. The initial equilateral triangle Adding one new triangle bump per line of the original triangle Adding one triangle bump for each of the twelve lines of the previous snowflake

The third, fourth and fifth recursive step add triangle bumps to all `48`, `4 * 48`, and `4 * 4 * 48` lines, respectively — as illustrated in the next three images.   As the size of each line is reduced by a third in each recursive step, we can hardly make out the individual lines anymore after five recursive steps.

### The geometry of Koch snowflakes

It is apparent from the shape of the Koch snowflakes that the sequence of operations applied to each line in each recursive step is always the same. So, let's have a closer look at those operations. We start with a line from a point `pS` to a point `pE` We need to chop this line into three equal parts to get the base line of the equilateral triangle that we want to construct. Since we already implemented the function `scaleLine`, we can use it to get the first base point of this triangle, `p1`, which is the end point of the scaled line `l1`. To get the third point of the small triangle, we can connect `l1` with itself, (or alternatively, we could have scaled the original line by two thirds). Here, we use `@`-patterns as well as anonymous variables to bind the lines to variables `l1` and `l2`, and at the same time extract the end points of both lines, `p1` and `p3`, respectively.

Now, all we need to do is to find the missing point of the new triangle, the “peak” of the triangle. Again, we can use a function that we already implemented, namely `rotateLine`. We rotate the second line, `l2`, clockwise by 5/6th of a full rotation (which corresponds to 5/3π radians). The only component of the rotated line that we are interested in is the end point, `p2`, which we extract by pattern matching.

Now we have got all the ingredients for implementing the recursive construction of one of the three parts of a Koch snowflake (each part corresponds to one line of the initial equilateral triangle).

``````kochLine :: Int -> Point -> Point -> Path
kochLine n pS pE
| n <= 0 = []
| otherwise
= [pS] ++ kochLine (n - 1) pS p1
++ kochLine (n - 1) p1 p2
++ kochLine (n - 1) p2 p3
++ kochLine (n - 1) p3 pE
++ [pE]
where
l1@(_, p1) = scaleLine (1 / 3) (pS, pE)
l2@(_, p3) = connectLine l1 l1
(_, p2)    = rotateLine (5 / 3 * pi) \$ l2``````

Note how we use pattern matching on the results of invoking the functions `scaleLine`, `connectLine`, and `rotateLine` in the `where` bindings. As long as we know that pattern matching is successful, we can use pattern matching in `where` bindings in exactly the same way as we use it for function arguments. The three `where` bindings of `kochLine` produce the three points `p1`, `p2`, and `p3` of the triangle that we need to impose on the line specified by the start and end points `pS` and `pE` passed as arguments to `kochLine` — just as illustrated by the three diagrams in the preceding section. We, then, recursively use `kochLine` on all four lines that we get from imposing one triangle bump on the line from `pS` to `pE`.

This use of recursion is interesting as it is our first function that recursively calls itself multiple times in a single recursive step. Specifically, `kochLine` uses fourway recursion whereas we only defined singly recursive functions in Recursion.

To produce the complete snowflake, all that remains is to combine three Koch lines to get the entire Koch snowflake. To this end, we recycle the `polygon` function to construct the initial equilateral triangle given the recursive depth and the base line:

``````kochFlake :: Int -> Line -> Path
kochFlake n line
= kochLine n p1 p2 ++ kochLine n p2 p3 ++ kochLine n p3 p1
where
[p1, p2, p3, _] = polygon 3 line``````

We again decompose the result of `polygon` using pattern matching in a `where` binding. When testing the function, please be aware that the number of recursive calls grows very quickly: a recursive depth of n, leads to 3 * 4n invocations of `kochLine`!

## Pythagorean Trees

Just as we generated vaguely snowflake-like looking diagrams using recursion in the previous section, we are now going to generate plant-like shapes, called Pythagorean trees.   Can you guess the geometric pattern used to construct these trees? If not, consider the first steps of constructing the first of the three trees displayed above.      The tree consists of a sequences of squares, stacked onto each other. This results in a surprisingly soft, organic looking structure. The triangles formed by the red lines define a Pythagorean triple of squares: the area of the base square is the sum of the areas of the two squares added in the following iteration. The trees only differ in which triangle was used to calculate the size and orientation of the squares in each step.

### Construction

We can construct right-angled triangles with a base line `a` to `b`, by drawing a circle with centre `m` right in the middle of that line, and radius that is the distance from `a` to `m`: Any point on that circle forms a right angled triangle with `a` and `b`. We can use this fact to calculate the coordinates of the points in our tree path.

We start building our tree given the base `line`. First, we calculate the points of the square using the previously defined `polygon` function. The last point is the same as the first, so we are not interested in it and bind it to the anonymous variable (`_`): As next step, we need to construct a right angled triangle with hypotenuse `(p3, p4)` — the hypotenuse is the longest side of the right angled triangle. We can do that by first scaling the line `(p3, p4)` by `0.5`, resulting in a line from `p3` to the middle of the line. To construct the circle, we flip the direction of that line (by swapping the end points around) with a new function `flipLine`: Now, we rotate the line `r` by any angle between zero and Pi to get the third point of a right angled triangle. Here, we use `0.7 * pi`, which happens to be the angle used to construct the first example tree. The lines `(p4, p5)` and `(p5, p3)` then form the base lines for the next iteration of the recursive construction of the tree: In our program, we don't want to hard code the rotation angle, and rather pass it in as parameter. Combining all these steps into a recursive function, we get

``````fractalTree :: Float -> Int -> Line -> Path
fractalTree factor n line = fractalTree' n line
where
fractalTree' 0 line = []
fractalTree' n line
= [p1, p4] ++ fractalTree' (n-1) (p4, p5) ++
fractalTree' (n-1) (p5, p3) ++
[p3, p2]
where
-- flip direction of line
flipLine :: Line -> Line
flipLine (pS, pE) = (pE, pS)

[p1,p2,p3,p4,_] = polygon 4 line
r               = flipLine (scaleLine 0.5 (p3, p4))
(_, p5)         = rotateLine (factor * pi) r ``````

The structure of this function is not unlike that of `kochLine` with a bit of `kochFlake` mixed in by way of using `polygon` to get the corners of a polygon (although, we are using a square here and used a equilateral triangle in `kochFlake`). Moreover, `fractalTree` only is binary recursive —i.e., it contains two recursive calls— whereas `kochLine` was four-way recursive.

If we pass `n` equals one to `fractalTree`, it returns the three upper lines of the square, as the recursive call with `n == 0` returns an empty path. The second and third example tree at the beginning of this section were generated with a variation of this function which changed the rotation factor to `1 - factor` in every third and fifth iteration, respectively. The following screencast demonstrates how to achieve these variations in code.

There are many other possible variations — for example, using triangles that are not right-angled as the basis, cycling through a range of different factors, or adding colour effects. Here, to close this chapter, a small selection of these variations.   If you want to save yourself copying the code from this chapter in pieces, here is a version of the `Fractals` module with all definitions that we discussed: Fractals.hs. Just copy its contents into the module with the same name in the Haskell project, `Fractals.hsproj`, that you downloaded at the beginning of this chapter.
1. Implement a function `colouredFTree :: Float -> Int -> Colour -> Line -> Picture` that elaborates on `fractalTree` by accepting the colour of the tree as an additional argument.
2. Vary `colouredFTree` by using the `fade` function, which we discussed in the context of spiral rays, to incrementally alter the colour in each recursive step.
3. Vary `colouredFTree` further by implementing and using `factor` as demonstrated in the last screencast.