Fun with Fractals

In these exercises we're trying to sharpen your eye for recursive structure.

The Chessboard

Our first image is the chessboard. Though arguably not a fractal, the chessboard does contain itself: a 4x4 chessboard can be constructed from 4 2x2 chessboards, an 8x8 from 4 4x4s, and so on. The picture below shows this.

$Figure Some(#fig:fractals:chessboards): caption$

Your mission in this exercise is to identify the recursive structure in a chessboard, and implement a method to draw chessboards. The method skeleton is

def chessboard(count: Int): Image =
  ???

Implement chessboard. Remember we can use the structural recursion skeleton and reasoning technique to guide our implementation.

chessboard is a structural recursion over the natural numbers, so right away we can write down the skeleton for this pattern.

def chessboard(count: Int): Image =
  count match {
    case 0 => resultBase
    case n => resultUnit add chessboard(n-1)
  }

As before we must decide on the base, unit, and addition for the result. We've given you a hint by showing the progression of chessboards in Figure recursion:chessboards. From this we can see that the base is a two-by-two chessboard.

val blackSquare = Image.rectangle(30, 30).fillColor(Color.black)
val redSquare   = Image.rectangle(30, 30).fillColor(Color.red)

val base =
  (redSquare.beside(blackSquare)).above(blackSquare.beside(redSquare))

Now to work out the unit and addition. Here we see a change from previous examples. The unit is the value we get from the recursive call chessboard(n-1). The addition operation is (unit.beside(unit)).above(unit.beside(unit)).

Putting it all together we get

def chessboard(count: Int): Image = {
  val blackSquare = Image.rectangle(30, 30).fillColor(Color.black)
  val redSquare   = Image.rectangle(30, 30).fillColor(Color.red)

  val base =
    (redSquare.beside(blackSquare)).above(blackSquare.beside(redSquare))
  count match {
    case 0 => base
    case n =>
      val unit = chessboard(n-1)
      (unit.beside(unit)).above(unit.beside(unit))
  }
}

If you have prior programming experience you might have immediately thought of creating a chessboard via two nested loops. Here we're taking a different approach by defining a larger chessboard as a composition of smaller chessboards. Grasping this different approach to decomposing problems is a key step in becoming proficient in functional programming.

Sierpinkski Triangle

The Sierpinski triangle, show below is a famous fractal. (Technically, Figure fractals:sierpinski shows a Sierpinkski triangle.)

The Sierpinski triangle.

Although it looks complicated we can break the structure down into a form that we can generate with structural recursion over the natural numbers. Implement a method with skeleton

def sierpinski(count: Int): Image =
  ???

No hints this time. We've already seen everything we need to know.

The key step is to recognise that the basic unit of the Sierpinski triangle is triangle.above(triangle.beside(triangle)). Once we've worked this out, the code has exactly the same structure as chessboard. Here's our implementation.

def sierpinski(count: Int): Image = {
  val triangle = Image.triangle(10, 10).strokeColor(Color.magenta)
  count match {
    case 0 => triangle.above(triangle.beside(triangle))
    case n =>
      val unit = sierpinski(n-1)
      unit.above(unit.beside(unit))
  }
}

←Fractals Nested Methods→