JavaScript Algorithms: Factorial

During a recent job interview, I was asked to write on a white board the necessary procedures to get the factorial of a number. My first question was, “What’s a factorial?”

What’s a factorial?

According to Wikipedia:

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n.

Huh!?

Exactly! Yeah, it doesn’t make sense when you try to explain it using words. An example is needed:

So say we provide the number 4. This is what would happen:

4 * (4 - 1) = 12
12 * (3 - 1) = 24
24 * (2 - 1) = 24

So as you can see, you’re just taking the number and multiplying it by itself minus one then multiplying the result by the next lowest number until the original number finally becomes one. The last multiplication isn’t actually needed because we know anything multiplied by one is always one. I only included it to make it more clear what’s going on.

As you can see, as the input number gets larger, the result grows exponentially:

5 * (5 - 1) = 20
20 * (4 - 1) = 60
60 * (3 - 1) = 120
120 * (2 - 1) = 120

Once you get to the double digits the result balloons to over three million!

10 * (10 - 1) = 90
90 * (9 - 1) = 720
720 * (8 - 1) = 5,040
5,040 * (7 - 1) = 30,240
30,240 * (6 - 1) = 151,200
151,200 * (5 - 1) = 604,800
604,800 * (4 - 1) = 1,814,400
1,814,400 * (3 - 1) = 3,628,800
3,628,800 * (2 - 1) = 3,628,800

Putting it all together

Here’s what needs to happen to solve this:

1. Make sure the input is a number.
2. If it’s zero, return 1 (since apparently the factorial of 0 is always 1).
3. Define a working variable and seed it with the input number.
4. Iterate while decrement the number until we get to 1 (we can exit early when we get to 1 because 1 multiplied by anything is always 1)

Solution

Unfortunately, in JavaScript you can’t reliably get the factorial of anything larger than 18 because JavaScript number type specification only work between -9,007,199,254,740,991 and 9,007,199,254,740,991.

Extra credit! Do it with recursion!

In my post about permutations, I talked a lot about recursion because recursion is probably the best way to create a list of all possible orderings of a list. Often recursion can be used in place of a loop because instead of looping you just have the function call itself again using the result.

So here’s how you do factorial recursively!

const factorial = (num) => {
  if (num === 0) return 1;
  return num * factorial(num - 1);
}

Yep! That’s all there is to it. But how can this be, you ask? Well, that is a very good question. Recursion is difficult to intuit so we’ll need to break it down a bit.

So say we’re trying to get the factorial of 10. This is what’s happening in practice:

const factorialTEN = () => {
  const ten = 10;
  const nineFunc = (nine) => {
    const eightFunc = (eight) => {
      const sevenFunc = (seven) => {
        const sixFunc = (six) => {
          const fiveFunc = (five) => {
            const fourFunc = (four) => {
              const threeFunc = (three) => {
                const twoFunc = (two) => {
                  const oneFunc = (one) => {
                    return one;
                  }
                  return two * oneFunc(two - 1);
                }
                return three * twoFunc(three - 1);
              }
              return four * threeFunc(four - 1);
            }
            return five * fourFunc(five - 1);
          }
          return six * fiveFunc(six - 1);
        }
        return seven * sixFunc(seven - 1);
      }
      return eight * sevenFunc(eight - 1);
    }
    return nine * eightFunc(nine - 1);
  }
  return ten * nineFunc(ten - 1);
}

factorialTEN calls nineFunc which calls eightFunc which calls sevenFunc which calls sixFunc which calls fiveFunc which calls fourFunc which calls threeFunc which calls twoFunc which calls oneFunc. And rather than calling another function, oneFunc returns 1 which triggers everything to multiply like so:

10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

Cascading function calls

Why doesn’t the multiplication happen before all the cascading function calls? Well, the reason has to do with order of operations. The way code works is what’s inside the parentheses gets executed first. So in the case of factorialTEN we have ten sets of nested parentheses to bubble through before any multiplication can happen.

So there you have it. I did factorial recursively and I showed you what was going on.