Factorials

 Let me return now to the basics of recursion to bring up another simple, classic problem: the calculation of the factorial. You may have heard some urban legend about Gauss, who was in class, and someone misbehaved, so the teacher said “You can’t go to recess until you find the sum of 1+2+3+…+100,” thinking this would keep the students busy a long while.

Gauss, the legendary mathematician he was, found the answer in seconds: 1+100 is a pari that sums to 101; and so is 2+99; and so is 3+98; and so is 4+97; and so on. We’re going from 1 to 100, so we have 100/2 = 50 pairs. The sum of the pair is 101, and we have 50 pairs, so the sum of 1+2+3+…+100 is 50*101 = 5050. (And indeed this generalizes for any upper bound: for some bound n, the sum ofthe first n numbers is n*(n+1)/2.)

That sequence grows quickly—1, 3, 6, 10, 15, 21, 28, and so on. But we are after a sequence that grows much, much more quickly.

In fact, let’s call the additive version of 1[operator]2[operator]3[operator]4… Gauss(n). Now let’s look at what happens when the operation is not addition, but multiplication: 1, 2, 6, 4, 120, 720, … etc. For now, let’s call this Mystery(n). It has a proper name and a real definition, but let’s just keep it vague for now as we appreciate how insanely quickly this number is growing.

 I claim—and by the end of this article, you’ll be able to prove me right—that Gauss(10) is 55, but Mystery(10) is more than 3 million; Gauss(20) is 210, but Mystery(20) is 2.4 billion billion. Put another way, Mystery() grows much, much faster than Gauss(). No, that isn’t a typo: Mystery(20) is somewhere in the ballpark of 2,400,000,000,000,000,000.  You can count to Gauss(20) in about 3 and a half minutes, at one number per second. You would need about 6 times the age of the universe to count to Mystery(20) at one number per second.

Mystery(), in fact, is the factorial function—what you get when you replace every + in the Gauss sequence with a *.

Imagine you’re a teacher, and you want to line up your students. You have Alice, Bob, and Charlie in your class. How many ways are there to arrange them?

Alice can come first. Then either Bob or Charlie. Then whoever wasn’t second must come third.

Bob can come first. Alice or Charlie can follow. Whoever wasn’t picked completes the triple.

Charlie can lead. Alice or Bob can be next. Whoever is left necessarily must come here.

Expressed as a set, we have ABC, ACB, BAC, BCA, CAB, CBA: six choices.

Now, let’s remove Charlie. {Alice, Bob} is possible; and so is {Bob, Alice}.

Now, let’s remove Bob. {Alice} is the only ordering.

Now, let’s do something strange: remove Alice. {} is the only ordering.

We can express this function in one of two ways: in a loop, like what the students might have done if the punishment problem had been to multiply: 1*2, 1*2*3, 1*2*3*4, and so on…

and the pseudocode looks like:

FUNCTION factorial(n)

    result ← 1

    FOR i FROM 2 TO n

        result ← result * i

    END FOR

    RETURN result

END FUNCTION

This correctly computes the value, but there’s a better, more classic, more elegant way.

Notice that 6! (“six factorial,” not “SIX!!!!!!!!”) is 6 times 5!; 5! Is 5 * 4!; and so on.

This allows us to very neatly, recursively define factorial().

 

Recall from our student-ordering experiment that, after we get rid of Alice, there is still one way to put no students in order: {}. Do nothing. That actually matters here because it gives us a defined value at 0.

Factorials are used to count the number of ways to arrange some number of objects, so, naturally, there is one way to arrange 0 objects: do nothing. That is one intuitive way to get to the fact that 0! Is 1, but we’ll see another by the end of this article.

To define something recursively, we need a base case—we have it, that 0!=1—and a rule, that the factorial of some number is the factorial of the previous number, times the number (5! = 5 * 4!; 100!  = 100 * 99!; and so on).

Armed with these two pieces of information, we can arrive at the following recursive definition:

FUNCTION factorial(n)

    IF n = 0 OR n = 1 THEN

        RETURN 1

    ELSE

        RETURN n × factorial(n - 1)

    END IF

END FUNCTION


The other way to get to the fact that 0! Is 1 is the following:

·       10! is 3628800

·       9!  Is 10!/10, or 362880

·       8! Is 9!/9, or 40320

·       7! Is 8!/8, or 5040

·       6! Is 7!/7, or 720

·       5! Is 6!/6, or 120

·       4! Is 5!/5, or 24

·       3! Is 4!/4, or 6

·       2! Is 3!/3, or 2

·       1! Is 2!/2, or 1—and up to this point, there should be no argument, since I am just applying the pattern that n! = n * (n-1)! In reverse

·       So naturally, 0! Is 1!/1, which is 1.