# Lab Week 14

### Learning Objectives

• Implement a recursive mathematical function to draw a set of circles on the canvas.
• Draw a recursive tree.
• Draw a Sierpinski triangle.

### Participation

In this lab/recitation, you will write some p5.js programs that use the techniques you’ve learned in class so far. The goal here is not just to get the programs done as quickly as possible, but also to help your peers if they get stuck and to discuss alternate ways to solve the same problems. You will be put into breakout rooms in Zoom to work on your code and then discuss your answers with each other, or to help each other if you get stuck. Then we will return to discuss the results together as a group.

For each problem, you will start with a copy of the uncompressed template-p5only.zip  in a folder named lab-14. Rename the folder as andrewID-14-AandrewID-14-B, etc. as appropriate.

### A. Fibonacci Numbers

The Fibonacci sequence is the following sequence of numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

These numbers occur in nature, architecture, music, and art. We will implement a version of the program completed in class that will display a set of circles where the number of circles is given by a Fibonacci number. The program will advance through the numbers, drawing more circles each time.

If you look at the sequence carefully, you will see that any Fibonacci number in the sequence is the sum of the previous two Fibonacci numbers. (Does that sound recursive to you?) Of course, two of the numbers don’t follow this rule; which ones?

We say the 0th Fibonacci number is 1, the 1st Fibonacci number is 1, the 2nd Fibonacci number is 2, the 3rd Fibonacci number is 3, the 4th Fibonacci number is 5, the 5th Fibonacci number is 8, etc.

```n              0   1   2   3   4   5   6   7   8   9   ...
fibonacci(n)   1   1   2   3   5   8  13  21  34  55   ...```

Complete the fibonacci function below so that the program computes and returns the nth Fibonacci number recursively.

```var n = 0;

function setup() {
createCanvas(400, 400);
frameRate(1);
}

function draw() {
background(220);
var numCircles = fibonacci(n);
drawCircles(numCircles);
fill(0);
text(n.toString(), 10, 10);
text(numCircles.toString(), 10, 30);
n += 1;
}

function fibonacci(n) {
// replace the question marks with the required expressions:
if ( ??????????????? ) return 1;
else return ( ??????????????? );
}

function drawCircles(numCircles) {
for (var i = 0; i < numCircles; i++) {
fill(color(random(0,256), random(0, 256), random(0, 256)));
circle(random(0, width), random(0, height), random(10, 30));
}
}
```

### B. Recursive Tree

We wish to draw the tree above. If you look at it recursively, a tree consists of a trunk, along with two trees on top of it, one at an angle 10 degrees to the left and one at an angle 10 degrees to the right. Each pair of trees is one level shorter than the whole tree.

Complete the recursive function drawTree so that it draws this recursive tree. Look at the comments to guide you along.

```var numLevels = 8;
var branchLength = 40;

function setup() {
createCanvas(400, 400);
frameRate(10);
}

function draw() {
background(240);
push();
translate(200, 350);            // location of base of tree
drawTree(numLevels, branchLength);
pop();
}

function drawTree(levels, length) {
// base case: if there are no more levels, just return:

line(0, 0, 0, -length);        // draw the trunk of the current tree
push();

// move the origin to the top of the trunk of the current tree:

// rotate to the left 10 degrees of the initial trunk:

// draw a tree with one less level with the same trunk length:

// rotate to the right 10 degrees from the initial trunk:

// draw a tree with one less level with the same trunk length:

pop();
return;
}
```

### C. Sierpinski Triangle

This is an example of a fractal, an image that is self-similar. When you look at parts of the image, you see the original image.

One of the most famous fractals is the Sierpinski Triangle which is a triangle that is divided up into three triangles which are divided up into three triangles each, which are divided up into… you get the idea.

To draw this sketch, we start with a large triangle of blue. We then find the midpoints of each of the three sides and draw a triangle between these points in the background color. Finally, we repeat the midpoint process with each of the three remaining blue triangles that are formed when we draw the triangle in the background color. Each of these triangles is “split” into three smaller triangles. This repeats until we reach the number of levels of repetition.

Complete the function splitIntoThree based on the comments to guide you.

```var numLevels = 4;

function setup() {
createCanvas(400, 400);
frameRate(10);
noStroke();
}

function draw() {
background(220);
fill(0, 0, 255);
triangle(200, 50, 350, 350, 50, 350);
splitIntoThree(numLevels, 200, 50, 350, 350, 50, 350);
noLoop();
}

function splitIntoThree(levels, x0, y0, x1, y1, x2, y2) {
// base case: if there are no more levels left to draw, we're done:

fill(220);   // background color
var x01 = midpt(x0, x1);   // midpoint of x between x0 and x1
var y01 = midpt(y0, y1);   // etc.
var x12 = midpt(x1, x2);
var y12 = midpt(y1, y2);
var x20 = midpt(x2, x0);
var y20 = midpt(y2, y0);

// draw a triangle using the midpoints:

// split each of the remaining blue triangles with one less level
// (hint: you should have three recursive calls here,
//  each call will have a list of x and y points for one of the
//  remaining blue triangles):

}

function midpt(a, b) {
return (a + b)/2;
}

```

### Handin

At the end of the lab, zip the lab-14 folder (whatever you got done) and submit it to Autolab. Do not worry if you did not complete all of the programming problems but you should have made it through problems A and B, and you should have some attempt at problem C.