# The Chessboard

In this exercise and the next we're trying to sharpen your eye for recursive structure.

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 in Figure fractals:chessboards shows this.

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.

<div class="solution">
`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))
}
}
```

</div>

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 in Figure fractals:sierpinski, is a famous fractal. (Technically, Figure fractals:sierpinski shows a Sier*pink*ski 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.

<div class="solution">
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))
}
}
```

</div>