Creating a Factorial Function!!!!!!!!!!!!!!!

Creating factorial function is not as scary as it sounds. If you haven't heard of factorial before, here is a simple example: $$ 3! = 3 \cdot 2 \cdot 1 = 6 $$

Likewise, 4! looks like this: $$ 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24 $$

As you can imagine, the factorial of larger numbers just involves multiplying a longer list of numbers together. Factorial shows up in different parts of mathematics. The most well known place is in the permutation formula.

It is pretty easy to calculate factorial for the numbers up to about 5 or 6. But for larger than that the answers start to get crazy. For example, 10! evaluates to millions. After a certain point it becomes impractical to calculate factorial with pen and paper. In this activity we will write a code to do it so we can calculate 100! and even higher!

Step 0. Open up the code

Click here to open up the code

In the top left corner, press to run the code and the output will look like this:

Important: Create an Account or Sign In, then click Duplicate

To save your work you need to create an account by clicking Sign Up in the top right corner of the screen. If you have already created an account, click "Log In" and put in your login information

A non-profit arts group called The Processing Foundation runs this site. They are nice people and they will not send you a bunch of emails for registering.

Before moving on, in the top left click click File --> Duplicate so that the code you are working with is on your account! -->

Objectives

If the program can detect that something is wrong with your code it will show a red next to that objective.

If the program can detect that you have completed the objective it will show a green check mark next to that objective.

But the program is not very smart and if it can't tell whether you have completed the objective it will indicate a question mark like this next to that objective.

By the end of this activity your goal is to have green check marks next to all the objectives like this:

The directions below will help you meet all these goals.

Step 1. Look at the code

The code here is pretty short. Here is the entire program:

// define the factorial function here

function draw() {
  
  // question 1: calculate 5!
  answer1 = 0; // change this
  text('5! = ' + answer1, 10,50);

  // question 2: calculate 10!
  answer2 = 0; // change this
  text('10! = ' + answer2, 10,75);
  
  // question 3: calculate 100!
  answer3 = 0; // change this
  text('100! = ' + answer3, 10,100);

  // question 4: There are 121 pilots and 50 planes. How many unique flight schedules are there? Assume one pilot per plane.
  answer4 = 0; // change this
  text('A4 = ' + answer4, 10,125);
  
  checkvalues();
  exit();
  
} // end draw() DO NOT ADD ANY CODE AFTER THIS LINE!!!

Similar to other coding activities, we will add code to the program until it can do something new (calculate the factorial) but then this activity is a little different from the others because we then need to answer four different questions. There is also a checkvalues(); command that checks if your answers are correct or not.

There are a couple of things to note at this point:

1. We are going to add a factorial function so that factorial(n) gives us the result of $n!$

As discussed later, you will need to name this function factorial because the milestone for "Define factorial function" is expecting the function to be named that.

2. You must use the factorial function that you will add to the code to answer the questions

The milestones are smart enough to figure out if you just copied the number from another program. If you just calculate 5! on paper for example and set answer1 in the code to be equal to that result you will still get a red because you didn't use the factorial function

3. The last question

The last question is "There are 121 pilots and 50 planes. How many unique flight schedules are there? Assume 1 pilot per plane"

The idea behind this question is that every day there is a flight schedule where 50 of the 121 pilots are assigned to a plane to fly for that day. Each plane is assigned to a different route (that is the same every day). The question "How many unique flight schedules are there?" is asking how many combinations of pilot and plane are possible. We will come back to this question later and give you some advice. The only hint we can give right now is that the answer is NOT something you can easily compute by hand.

Step 2. Try out n! in the code and watch it fail

The bad news first: if you try to use ! in the code to calculate factorial it is not going to work.

Modify the code so that it looks like this:

  
  // question 1: calculate 5!
  answer1 = 5!;
  text('5! = ' + answer1, 10,50);

  // question 2: calculate 10!
  answer2 = 10!;
  text('10! = ' + answer2, 10,75);
  
  // question 3: calculate 100!
  answer3 = 100!;
  text('100! = ' + answer3, 10,100);  

Now run the code. Notice that something bad happens! Exactly what bad thing happens may depend on your browser and operating system. Maybe nothing happens.

Write down what happens when you add things like 5! in your code

Clearly this is not going to work. It turns out that the people who developed the JavaScript programming language wanted to use ! for something different than factorial. Instead we will need to add a function to the program to calculate factorial.

Step 3. Computer functions and mathematical functions

Computer functions and mathematical functions are similar but different.

Step 3a. Similarities between mathematical and computer functions

Similarity #1: Mathematical functions and computer functions both take in "arguments"

The function $f(x) = x^2$ for example takes $x$ as its "argument". Similarly in a computer program the number or variable within the parentheses is the "argument" to the function.

Similarity #2: Evaluating to a number

Mathematical functions always evaluate to some kind of number. The function $f(x) = x^2$ for example takes the value of $x$ and squares it and $f(x)$ is equal to that result. For example $f(2)$ is equal to 4.

Computer functions can be written to "return" a number. For example, to write $f(x) = x^2$ in javascript (which is the language we are using) would look like this:

function f (x) {
   return x*x;
}

In the computer program we can now use f(x) wherever we want to calculate the square. For example f(2) would "return" the value 4. We are not actually going to need to calculate the square in our program but that is how you could do it if you wanted to.

Step 3b. Differences between mathematical and computer functions

Here are some differences between mathematical and computer functions:

Difference #1: Computer functions do NOT have to evaluate to a number

Computer functions can do all kinds of things and perform various calculations without "returning" a number.

For example, in the Half Checkerboard Challenge (Part 2. The Optimal Strategy) there is a computer function that plots a circle but it does not return a number. A function that does not return a number is sometimes called a "void function". If a computer function does not include return in its definition somewhere then it is a void function.

In the program we are working with there are functions like checkvalues(); and exit(); Notice that when we use these functions in the code there is no variable that the result is saved to.

Difference #2: Computer functions do NOT have to take an argument

Computer functions can be constructed so that they do NOT take an argument.

Difference #2: Computer functions can call themselves

It is possible to define a computer function that can call itself. In other words you can define a computer function and include in the definition of that function a command to run that function.

Why would you ever want to do this? To calculate the factorial function of course!

Step 4. Think about the fastest and easiest way to calculate the factorial

Sometimes calculating things by hand can help you see how to make it easier for the computer to calculate something. BEFORE YOU FILL IN THE TABLE BELOW think about how you could fill in the missing values in the fastest possible way.

What is the trick to calculating factorials up to ten as quickly as possible?

Related question: If you knew the value of 50! what would be the easiest way to calculate 53!

Step 5. Define a function with the name factorial

The first thing we are going to do as we work towards having a function to compute factorials is to define a function with the name factorial and an argument n like this:

function factorial (n) {
    return n; //change this
}

Paste this code into your program where it says // define factorial function here

This code will not calculate factorial correctly, but it will give you the green check mark for "Define factorial function"

Step 6. Use factorial(n) to answer question 1

Use factorial(5) to answer question 1 (calculate 5!). Replace this:

answer1 = 0; // change this

with this:

answer1 = factorial(5);

At this point factorial(5) will give the wrong answer for 5! but what answer will it give? Why?

Step 7. Learn about Iteration and Recursion

Now we need to modify the definition of factorial(n) so that it actually calculates the factorial.

There are at least two ways to do this correctly. One way is using "iteration" and the other way is using "recursion". If you have completed other coding activities you have probably already used iteration.

Step 7a. Iteration

Iteration involves running the same code over and over. For example, in most of the other coding activities the draw() function is run over and over which means everything inside the curly brackets {} are run about 60times per second.

Note: Our factorial program is not running at 60 times a second because there is an exit(); function inside the curly brackets which means that the code in the curly brackets only gets run once.

Another example of iteration is a for loop. Everything inside the {} of the foor loop is run over and over until some criteria is met.

What is a code we can run over and over to calculate the factorial and what would we want to do over and over again?

Well, there is a lot of multiplying when you calculate the factorial. Something that might help is *= which means take the variable and multiply it by the value on the right. This bit of code is like the multiplicative version of += which adds and -= which subtracts.

Here is some code that is part of what we need to add to our factorial(n) definition:

function factorial (n) {    
  thefactorial = ???;
  for (i = n; ??? > ???; i -= 1) {
     thefactorial *= i;
  }
  return thefactorial;
}

Your job is to replace the ??? with numbers or variable names so that factorial(n) returns the correct values.

Note: Feel free to ask other students for help. But if you can't figure it out there is also a way to do it with recursion!

Step 7b. Recursion

Another correct way to get your program to calculate the factorial is using recursion.

Recursion happens when the definition of a computer function also contains a command to run that same computer function

Here is a metaphor for why this might be helpful. Imagine that you live in a huge house like a mansion and you want to write an algorithm for cleaning up the house. Let's call it the "clean up" function.

There are a lot of different ways you could write a clean up function. One way to write that algorithm would be like this:

function cleanup(area) {
      if (area is clean) {
         return; // exit the function
      } else if (area contains only one piece of trash) {
         pick_up_trash();
         return; // exit the function
      } else {
        area1 = split_area_into_two(area,1);
        area2 = split_area_into_two(area,2);
        cleanup(area1);
        cleanup(area2);  
      }
}

Notice that the definition of the cleanup function includes a command to run the cleanup function!

Explain how the algorithm above would be able to clean up an entire house. Draw a flowchart if you need to.

Step 7c. Recursion in the factorial function

Here is a definition of the factorial function that is another way to do the calculation.

function factorial ( n ) {
   if ( n ><=?  ???) {
     return n*factorial(n-1);
   } else {
     return ???;
   }
}

Your job is to replace the ??? with numbers or variables and to replace the ><=? with one of these comparison operators:

Note: Feel free to ask other students for help. But if you can't figure it out you can also go back and try the iteration approach described in Step 7a.

Step 8. Answer the questions

When you are developing new code it is always important to test it. Sometimes this is called a "unit test" because the new code is like a unit and we are testing it. It is important to check a couple of different values of n to make sure the code is working.

Why is it important to check a few different values of n?

The four questions are:

1. Calculate 5!

Test this by setting:

answer1 = factorial(5);

2. Calculate 10!

Test this by setting:

answer2 = factorial(10);

3. Calculate 100!

Test this by setting:

answer3 = factorial(100);

If your factorial function is working correctly you should get all green checks for questions 1 - 3.

Step 9. Question 4

Question 4 is a word problem:

"There are 121 pilots and 50 planes. How many unique flight schedules are there? Assume 1 pilot per plane"

Let's say all the pilots work at the same airport. When a pilot is assigned to fly a particular plane for the day they will fly that plane to its destination (for example Columbus to Orlando, Florida) and then they will fly that plane back on the return journey (Orlando back to Columbus). The flight schedule assigns each pilot to a particular destination for that day, or the pilot is given the day off.

The question of "how many unique flight schedules are there?" is really asking how many different combinations of pilot and destination are possible.

Hint #1: this is not something you can easily compute with pencil and paper. The answer is a very large number.

Hint #2: You will need to use one or more factorial(n) commands to compute the answer.

Hint #3: This video on permutations can help you figure it out.

If you get the answer correct you will get a green for question 4.

At this point you should have all green checks! Yay!

Challenges:

Challenge #1. Make sure factorial(0) equals one

Test out your code and see what you get for factorial(0). In math 0! is supposed to evaluate to 1. Does this work for your code? If it doesn't, modify your definition of factorial(n) so factorial(0) so it gives 1 but be sure to check that your answer for 5! 10! 100! etcetera work out to be the same.

Challenge #2. For what n does factorial(n) give Infinity?

As you have probably noticed, factorial(100) evaluates to a very large number. It turns out that if n is too large then the program is overwhelmed at it just says the answer is infinity

For example, try factorial(1000) and notice that it returns Infinity. To be clear, this is not correct. Any non-infinte value of n should give a non-infinite value of factorial(n) but this is not what happens.

What is the largest value of n that gives a non-infinite result from factorial(n)?

Bonus challenge: If you can, try your program on another computer, smartphone or tablet (or xbox!), or try a different browser. Do you get the same result for the largest value of n that gives a non-infinite result?

For more information: The type of error that occurs when we increase n too much is referred to as an "overflow" error. In this particular case it is a floating point overflow. Another type of overflow error is integer overflow.

Challenge #3. Double factorial

In math there is also a double factorial that is represented like this: $n!!$

So for example: $$ 6!! = 6 \cdot 4 \cdot 2 = 48 $$

and $$ 7!! = 7 \cdot 5 \cdot 3 \cdot 1 = 105 $$

Create a doublefactorial(n) function in your code. Test it out (a.k.a. "unit test") so that it matches up with this table:

Note: It doesn't matter whether you use iteration or recursion to compute the double factorial. Just make sure the values your code produces for different n agrees with the table!