**New Required Java Skills: **Recursion

# Java: Lesson 17 – Finch Fractals

#### Resources

Resources available for teachers. Login/Get Access

In this last lesson, you will explore recursion with the Finch. Recursion is when a function calls itself. In this lesson, you will use recursion to draw Koch fractals.

The Koch fractal, also called the Koch snowflake, can be drawn with increasing levels of complexity. The level of complexity is called the order of the Koch fractal. A Koch fractal of order 0 is just a straight line with some length *L* . Starting from order 0, which we call the base case, we can build Koch fractals with larger orders. To create the order 1 fractal, we make four copies of the order 0 fractal; each copy has a length of *L*/3. We put them together so that the first and last copies lie along a straight line, while the two middle ones protrude from the line and make a 60° angle. We continue this process to make the order 2 fractal. We make four copies of the order 1 fractal where each copy is 1⁄3 the size of the original. Then we put these four copies together so that the two copies in the middle form a 60° angle. You can keep going in this way to make a fractal for any positive order *n*! As *n* approaches infinity, the length of the Koch fractal also approaches infinity because the length of each order of the fractal is 4/3 times the length of the previous order. As you zoom in on a portion of the Koch snowflake, it is self-similar, meaning that each smaller portion looks like the larger whole. The Koch snowflake is a fractal because a simple algorithm generates a complex, self-similar pattern.

#### Exercise 1:

To draw Koch fractals with your Finch, you will need two turning methods, one to turn the robot left 60° and one to turn the robot right 120°. The right wheel should always have a speed of 0 for these turns; make sure that only the left wheel moves when the Finch is turning. Also, the left wheel should move slowly (approximately speed 77).

As you draw fractals in this lesson, you may want to get a picture of your Finch’s movement. You could attach a marker to the Finch, but it is hard to get a good picture of your fractal that way. Instead, attach a CR2302 battery to a small LED and tape it to the Finch so that the LED is directly over the right wheel (the wheel that is stationary during turns).

Now you can use a long exposure photograph follow the “light trail” of the LED as the Finch moves. The pictures here were taken with the Slow Shutter Cam app, but other methods of taking long exposure photographs can also be used (LongExpo is a free app). You will need to make sure that the camera is very still during the exposure, so a tripod is a good idea if you have access to one.

#### Exercise 2:

If you have attached an LED to your Finch, use a long-exposure photograph to check the angles that the Finch turns when you use your methods from Exercise 1. Make sure these functions are as accurate as possible so that you will get nice pictures of your fractals.

In the description of Koch fractals above, we started with order 0 and then worked our way up to larger orders. To draw a fractal with your Finch, you will actually need to do the opposite. You will start with some number *n*, and you will want to draw a Koch fractal with that order. Luckily, there is an algorithm for this! We will use the algorithm given in *How to Think Like a Computer Scientist: Learning with Python 3* by Wentworth, Elkner, Downey, and Meyers. The steps below can be used to draw a Koch fractal of order *n*:

- Draw Koch fractal of order
*n*– 1 and size*L*/3. - Turn left 60°.
- Draw Koch fractal of order
*n*– 1 and size*L*/3. - Turn right 120°.
- Draw Koch fractal of order
*n*– 1 and size*L*/3. - Turn left 60°.
- Draw Koch fractal of order
*n*– 1 and size*L*/3.

You are going to use this algorithm to write a program that uses the Finch to draw a Koch fractal given the order (greater than or equal to 0) and size. For the Finch, the length of a line is roughly proportional to the time that the wheels move, so you can assume that the “size” of the fractal is a time period in milliseconds.

#### Exercise 3:

Define a method called drawFractal().

- This method should take two parameters, the order of the fractal (
*order*) and a time period in milliseconds (*time*). - Next, add the base case to your method. If the order of the fractal is 0, the robot should move forward in a straight line for
*time*milliseconds. - Before moving on to the next exercise, test your method to make sure that it works as expected for order 0 (for this exercise, your robot doesn’t need to do anything for higher orders).

#### Exercise 4:

When the order is not 0, your method will need to call itself (recursion!). If the parameters of drawFractal() are *order* and *time*, what parameters should you use in the recursive calls to drawFractal()? Remember, you are implementing the algorithm given above Exercise 3. Fill in the blanks below.

- drawFractal( _____________ , _______________ )
- Turn left 60°
- drawFractal( _____________ , _______________ )
- Turn right 120°.
- drawFractal( _____________ , _______________ )
- Turn left 60°.
- drawFractal( _____________ , _______________ )

#### Exercise 5:

Now implement your plan from Exercise 4!

- Remember to use your turning methods from Exercise 1.
- drawFractal() should only call itself when the order is greater than 0. When the order is 0, the Finch should move in a straight line. You have already implemented that part!
- When testing your program, start by testing with order 1, and then work your way up to larger orders. This will make it easier to see if your program is working as you expect.