Creating a Factorial Function!!! (Part 2. Recursion Method)

In Creating a Factorial Function !!! Part 1 we used a for loop to calculate the factorial. And it worked!

In this activity we consider a different way to calculate the factorial. The method we used in Part 1 can be called iteration. Iteration is when a computer runs the same code over and over. A for loop is an example of iteration.

A different way to calculate the factorial is with recursion. Recursion is more abstract than iteration. It involves a special feature of most programming languages where you can call a function from within the definition of that function. If that seems hard to picture, right now just consider the goal of this activity is to calculate the factorial without a for loop.

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

Here is the entire program:

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

function draw() {
  
  text('3! = ' + factorial(3),10,50);
  text('4! = ' + factorial(4),10,75);
  text('5! = ' + factorial(5),10,100);
  text('6! = ' + factorial(6),10,125);  
  text('7! = ' + factorial(7),10,150);
  text('8! = ' + factorial(8),10,175);
  text('9! = ' + factorial(9),10,200);
  text('10! = ' + factorial(10),10,225);
  text('20! = ' + factorial(20),10,250);
  text('50! = ' + factorial(50),10,275);
  text('100! = ' + factorial(100),10,300);
  
  text('Challenge: 0! = ' + factorial(0),10,350);
  
  checkvalues();
  exit();
  
} // DO NOT ADD ANY CODE AFTER THIS LINE!!!

Similar to Part 1 we will need to define a function called factorial that we will use to answer these questions.

Step 2. Learn about computer functions and mathematical functions

Computer functions and mathematical functions are similar but different.

Step 2a. 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 2b. 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. For example in our program checkvalues(); and exit(); are computer functions that do not have any numbers or variables inside the parentheses.

Difference #3: 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? The next step has an example

Step 3. Learn about 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 4. Recursion in the factorial function

Step 4a. Remove the old factorial function

Remove this code from your program:

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

Step 4b. Replace the old factorial function with a new factorial function

Here is a definition of the factorial function that does not use a for loop

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:

If you make a guess for the ??? and run the program it will automatically check the values for 3! 4! 5! 6! 7! 8! 9! 10! 20! 50! and 100!. Software engineers and computer programmers refer to these kinds of checks as a "unit test".

For now don't worry too much about whether you can get 0! correct.

Step 5. Large values of n

One of the challenges in Part 1 was to increase the value of $n$ in factoial(n) until the program gives infinity which is incorrect. Unless $n$ is infinity, we should get a finite number from $n!$. The finite number may be gigantic but it will still be finite. In one of the challenges for Part 1, you try to figure out the largest value of n for which the output of the program is still finite.

We now have a new method (i.e. recursion) to calculate $n!$ which is totally different from the method in Part 1 (i.e. for loop). Perhaps the program will have a different value of $n$ where it gives infinity instead of a very large but finite result.

Test your code to find the largest n for which the program returns a non-infinite result

How does this compare with the largest value of n from Part 1 (i.e. the for loop method)?

Advice: Try factorial(1000) and decrease n to be less than 1000 if factorial(1000); is infinity, or increase n to be larger than 1000 if factorial(1000); is finite

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.

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 yes, that's great! 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. 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!