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

Nested Methods→