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

Haskell for Mac

Rasterific is included and ready to use in Haskell for Mac. No further installation is required.

Command Line Haskell

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:

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:

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.

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.)

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.

Download

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.

Haskell for Mac

Just open Fractals.hsproj in Haskell for Mac and proceed as in the screencasts.

Command Line Haskell

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)

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)]

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:

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
    newColour = fade colour
    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

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:

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
    newColour = fade colour
    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
        newColour = fade colour
        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

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:

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):

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.

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:

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.

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.

Haskell implementation

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:

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 * 4ⁿ 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.

$bi-coloured fractal tree not using right angles$

Download

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.

Spirals, Snowflakes & Trees: Recursion in Pictures

Programming Environment

Haskell for Mac

Command Line Haskell

Simple Pictures

Download

Haskell for Mac

Command Line Haskell

Manipulating Lines and Colours

Drawing Spirals and Polygons

Koch Snowflakes

The geometry of Koch snowflakes

Haskell implementation

Pythagorean Trees

Construction

Download

Exercises