Week 3

[github-learning-lab[bot]]

Introduction to Recursion

This assignment will demonstrate the basics of recursion, and ask you to create a recursive function of your own. If at any moment you need help, feel free to contact your TAs.

In English, the term "recursive" means something is "characterized by recurrence or repetition." Many natural processes in the world are recursive. As an example, start with an equilateral triangle, and replace the middle 1/3rd of each side by another equilateral triangle. Continue this process over and over until you begin to see something like a snowflake. This is called a Koch snowflake.

Recursion is the process in which a function calls itself directly or indirectly. A function is said to be recursive if it calls itself. Let's look at an example.

function HelloWorld(count) {
   if (count < 1) return
   print("Hello World!")
   HelloWorld(count - 1)
}

Let's trace through an example of calling this function. We'll call HelloWorld(5).

HelloWorld(5)
// count of 5 is not less than 1. Print Hello World. Call HelloWorld(4).
// count of 4 is not less than 1. Print Hello World. Call HelloWorld(3).
// count of 3 is not less than 1. Print Hello World. Call HelloWorld(2).
// count of 2 is not less than 1. Print Hello World. Call HelloWorld(1).
// count of 1 is not less than 1. Print Hello World. Call HelloWorld(0).
// count of 0 IS less than 1. Return.

Notice how the command print("Hello World!") is run 5 times in total throughout this recursive call. Thus, our output should look something like this:

Hello World!
Hello World!
Hello World!
Hello World!
Hello World!

You may wonder why we don't simply use a for loop, in which case your argument would be completely valid! However, in this case, we used a relatively simple function in order to demonstrate how recursion works. Where recursion truly shines is in the more complex problems.

Let's take a look at the Fibonacci numbers. In mathematics, the Fibonacci numbers form a sequence called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. What's cool is that the Fibonacci sequence uses zero-based indexing, which lends itself very well to most programming languages. Here is the beginning of the Fibonacci sequence:

How can we use code to find the nth Fibonacci number? For example, we would input the number 3 and the program should output 2, the 3rd Fibonacci number (remember that the Fibonacci sequence uses zero-based indexing!). It turns out that recursion lends itself very well to this particular problem.

function findFibonacci(n) {
    if (n < 2) return n
    return findFibonacci(n-1) + findFibonacci(n-2)
}

Let's trace through the code using an example of findFibonacci(3).

findFibonacci(3)
// n of 3 is not less than 2. return findFibonacci(2) + findFibonacci(1)
  // findFibonacci(2): n of 2 is not less than 2. return findFibonacci(1) + findFibonacci(0)
    // findFibonacci(1): n of 1 IS less than 2. return n (which is 1)
    // findFibonacci(0): n of 0 IS less than 2. return n (which is 0)
    // Thus, findFibonacci(1) + findFibonacci(0) = 1 + 0 = 1 
  // findFibonacci(1): n of 1 IS less than 2. return n (which is 1)
  // Thus, findFibonacci(2) + findFibonacci(1) = 1 + 1 = 2
Output: 2

Take some time to run through the process above and make sure it makes sense. There is something we should take care to note: notice how we run the function findFibonacci(1) twice! This actually becomes incredibly burdensome once we use larger numbers, and we can end up running the same functions hundreds, even thousands of times - and there is most definitely a faster way to compute the Fibonacci numbers. However, this is beyond the scope of the course, and we utilized this function just to show an example of what recursion can look like.

Pay attention to how our recursive functions have been structured so far. We first always identify a base case such that our recursive calls will always be stopped at some point. In findFibonacci(n), our base case was any n less than 2, to mark the first two numbers of the Fibonacci sequence: 0 and 1. In Hello World, our base case was count < 1 i.e. whenever our count got down to 0. This makes sense because once our count comes down to zero, we don't want to print any more Hello World!s. Thus, our first recommendation for writing recursive functions is to always identify the base case first!

Your next step should then to make the recursive calls. This skill can only be polished with more practice, so don't worry if you don't get it the first time. Our best advice here is to trust that your code works.

Hopefully you now have a sense of what recursion is, and a vague idea of how to construct a recursive function. Don't worry if you're struggling a little bit with thinking recursively - it will start coming naturally with more and more practice. If you're looking to try out a few more problems by yourself, this is a great website with a list of incrementally harder recursion problems to solve! Although it only compiles Java (not JavaScript), you can use Node to run your code locally on your machine instead. Moreover, in the website, you can type a return statement in the given code box and click the Go button to find many more test cases to ensure your program runs correctly.

🚗 Challenge

To complete this assignment, create a recursive function that returns the factorial of an integer n (without using a for loop!). Recall that the factorial of a number n is denoted by n!, where:

For example, 5! = 5 x 4 x 3 x 2 x 1 = 120.

Hint: Identify a base case first! Then move onto the recursive call. Please contact your TA if you need any help at all!

✏️ Testing

Once you have your function set up, it's time to test it out! Here are a few test cases:

Function Call	Output
factorial(1)	1
factorial(2)	2
factorial(3)	6
factorial(4)	24
factorial(5)	120
factorial(6)	720
factorial(7)	5040
factorial(8)	40320
factorial(12)	479001600

Here is a list of 100 factorials in case you'd like to check more.

✅ Submit

Commit a file called factorial.js with your recursive factorial function!

[tanjinprity4]

Done!

[github-learning-lab[bot]]

Recursive Art

For this assignment, you will follow the instructions and complete a task showing your knowledge of the subject at the end. If at any moment you need help, feel free to contact your TAs.

You've received some signals from aliens that decode to result in intricate graphics. These images have patterns that seem to repeat themselves and represent mathematical concepts which appear all around earth in nature. You have decided to recreate these messages in order to resume communication with the extraterrestrials.

:airplane: Phase 2

Create a new file named drawing.js

Learning how to draw in JavaScript

In your project for this week, you will mainly focus on creating a function that will draw one shape continuously, so keep these handy!

Shapes:

• Rectangle: rect(x, y, w, h)
• Ellipse: ellipse(x, y, w, h)
• Triangle: triangle(x1, y1, x2, y2, x3, y3)
• Line: line(x1, y1, x2, y2)
• Point: point(x, y)
• Arc: arc(x, y, w, h, start, stop)
• Bezier: bezier(x1, y1, cx1, cy1, cx2, cy2, x2, y2)
• Quadrilateral: quad(x1, y1, x2, y2, x3, y3, x4, y4)
• Image: image(image, x, y, width*, height*)

For more complex shapes and examples, visit here (Thank you Khan!)

Want to be :sparkles:fancy:sparkles:? Try changing the colors:

• background(r, g, b) (Set background color)
• fill(r, g, b) (Set fill color)
• noFill() (Stop filling in shapes)
• stroke(r, g, b) (Set the outline color for shapes)
• strokeWeight(thickness) (Alter thickness of strokes)
• noStroke() (Stop outlining for shapes)
• color(r, g, b) (Store a color in a variable)
• blendColor(c1, c2, MODE) (Blend two colors)
• lerpColor(c1, c2, amount) (Using 2 colors, find one in between)

Randomizing Your Drawing

• Using Math.random()*n gives you a random number in the range of 0 and n.

  Tip: Try manipulating the number in some way to incorporate it into the parameter of a shape or color

Challenge

To practice implementing the concept of recursion in JavaScript art, start by creating a drawing of an alien (doesn't have to be perfect!). This drawing will be unique each separate time you run the program.

:red_car: Running your Code

Since we are focusing on pure JavaScript and this task requires HTML to run, we are going to be borrowing Khan's website to display our artwork.

1. Go to this website
2. Write your code in the provided area
3. If your code doesn't have output that will be different everytime, the drawing will update whenever you change the code
4. If you implement something like randomization, a "restart" button will appear to run it multiple times

:pencil2: Testing

Time to check if you are able to create a unique :alien: everytime, press "restart" and see the face change!

✅ Submit

Phase 2: Complete a program that draws a unique alien

Commit a file called drawing.js

[tanjinprity4]

Done!

[github-learning-lab[bot]]

Recursive Art

For this assignment, you will follow the instructions and complete a task showing your knowledge of the subject at the end. If at any moment you need help, feel free to contact your TAs.

You've received some signals from aliens that decode to result in intricate graphics. These images have patterns that seem to repeat themselves and represent mathematical concepts which appear all around earth in nature. You have decided to recreate these messages in order to resume communication with the extraterrestrials.

:airplane: Phase 3

For this lesson, we're just going to be taking a look at an example of recursive art to get your gears running.

:eyes: Taking a peek at an example

See what our shell looks like

:question: What's happening?

The key to recursion is drawShape() in this program

Before we get into how this drawing is done with the concept, we'll go over what's happening.

• The very first time the function is called, x = 200, y = 200, size = 360, and orientation = false.

  drawShape(200, 200, 360, false);

• In the function, the parameter orientation determines which way the arc should face (up or down). In this case, it's false, so we are drawing an arc face down.

  // start and stop degrees of arc
  var start = 0;
  var stop = 180;
  
  // if arc is right side up, switch start and stop so arc becomes right side up
  if (orientation) {
      start = 180;
      stop = 360;
  }

• We then draw our first arc with the parameters called with the function (x = 200, y = 200, size = 360, and orientation = false)

  // draw arc
  arc(x, y, size, size, start, stop);

• The variable orientation also dictates where the arc should begin to draw:

  if (orientation) {
      x = x + scale * size;
  } else {
      x = x - scale * size;
  }

• Next we see var scale = 0.085;, which is a key component in the recursion calculation. This is what causes the arcs to get smaller as we go deeper and deeper.

• And that leads into our the key calculation! For the arcs to become spirals, if orientation is true (or the arc is facing up) it will move the pen to the right. If orientation is false (or the arc is facing down) the pen will start further to the left instead. This allows the shell to spiral and get smaller.

  Keep in mind, these new calculated values will be applied the next time the function is called. In additional to different x values, we will also make the radius smaller by assigning a new value to size

  // adjust x coordinate of next arc depending on orientation of arc
  if (orientation) {
  x = x + scale * size;
  } else {
  x = x - scale * size;
  }

• In order for the arc to stay centered and decrease in size, we also need to calculate a newSize value. var newSize = size/1.2;

• Lastly, to continue the recursion we need to call our drawShape() function again, but with some catches.

  if (newSize >= 4) {
      drawShape(x, y, newSize, !orientation);
  }

  1. Since recursion is not an infinite loop, we want the function to stop being called once the size is less than 4
  2. We want to flip the boolean of orientation so that if it previously drew an arc facing down, we will now draw one facing up.

And that's it! drawShape() will continue to be called, arcs will continue to be drawn, and new values will be calculated until the size becomes less than 4.

:pencil2: Requirements

In the next part, you're going to be creating your own recursive art, but we'll be adding some requirements: 1) Have a base case (This is the "endpoint" where the calculation terminates or stops)

• Remember: Recursion is not an infinite loop! 2) Have a rule that causes the calculation continue or go deeper and deeper (continues the recursion) 3) For fun and not demonstrated in the example: the artwork must be randomized, meaning that a characteristic (can be size, color, length, or shape) is changed everytime the code is run

These requirements are exemplified in the example above, so let's talk a little about how the code incorporates them

1) The base case in the example is when the size is divided by 1.2 so many times that it becomes less than 4. This is when the calculation terminates and the function is not called anymore 2) The rule that causes the calculation to go deeper is the fact that function will need to be continuously called within eachother until size is less than 4.

✅ Submit

Time to do some research: Find one example of recursion in nature and explain how one of the requirements applies.

Comment your findings to move on and start on your artwork! :mag:

[tanjinprity4]

We see recursion in plant leaves. They keep growing on cylindrical stems from the bottom until they reach the tip. In some plants, the leaves keep getting smaller towards the tip of the stems. It can be perceived as the base case: "When reach the tip , no more leaves will grow."

[github-learning-lab[bot]]

Recursive Art

For this assignment, you will follow the instructions and complete a task showing your knowledge of the subject at the end. If at any moment you need help, feel free to contact your TAs.

You've received some signals from aliens that decode to result in intricate graphics. These images have patterns that seem to repeat themselves and represent mathematical concepts which appear all around earth in nature. You have decided to recreate these messages in order to resume communication with the extraterrestrials.

:airplane: Phase 4

Create a new file named artproject.js

Creating your own Recursive Art

It's finally time to send the aliens your own personalized art for them to decipher... We just have the 3 requirements in order to make communication go smoothly.

Here are some examples that you can take inspiration from, but try to keep yours original!

• Ferns
• Colorful Tree
• Geometric

Find more here under "Spinoffs"

Challenge

Draw anything (with common sense) utilizing recursion. Meet these 3 requirements: 1) Have a base case (This is the "endpoint" where the calculation terminates or stops)

• Remember: Recursion is not an infinite loop! 2) Have a rule that causes the calculation continue or go deeper and deeper (continues the recursion) 3) For fun: the artwork must be randomized, meaning that a characteristic (can be size, color, length, or shape) is changed everytime the code is run

:red_car: Running your Code

Since we are focusing on pure JavaScript and this task requires HTML to run, we are going to be borrowing Khan's website to display our artwork.

1. Go to this website
2. Write your code in the provided area
3. With randomization, a "restart" button will appear to run it multiple times

:pencil2: Testing

Go ahead and press "restart" as many times as you wish to view your recursive art. Make sure it meets those 3 requirements!

✅ Submit

Phase 2: Complete a program that creates a randomized piece of art with recursion!

Commit a file called artproject.js