Tag Archives: recursive

Factorials For Fun

Start from the beginning. A factorial is a specific multiplication function applied to a positive integer value and all of its positive descendants. True but vague and tough to digest.

A factorial means to multiply a consecutive sequence of descending natural numbers.

Below, n is any positive integer (equal to a natural number), being multiplied:

            n! = n·(n–1)·(n–2)·…·3·2·1                                                                                             [1]

The symbol for a factorial is the exclamation point: ! . n! is pronounced ‘en’ factorial (math fans) or ‘en’ bang (programmers) or shriek out n (literalists and comedians).

Here are some examples:                      3! = 3·2·1 = 6

                                       10! = 10·9·8·7·6·5·4·3·2·1 = 3628800

{ Sudden question: In 1 second, how much would  9!  be? }

                                         1! = 1

To see the first 100 factorials, please admire the following table by N. J. A. Sloane:   First 100 Factorials

These integer results become huge as n increases. In a future post, I will write about how to determine the number of digits of n! without calculating the factorial and visually counting the digits.

Because mathematicians revere economy in writing, n! can be defined for any positive integer n by two rules:

            n! = n·(n–1)!
            and                                                                                                                              [2]
            1! = 1                                                                       

meaning, n! is the product of n and the factorial of the next lower value shown as (n – 1).

In the case of the second rule, this only works if we also have

            0! = 1                                                                                                               [3]

Since by rule 1 (and I know this may be a head-scratcher…)

           1! = 1·0! = 1                                                                                                      [4]

To find the value of n! , the first rule is applied repeatedly, as shown:

            n! = n·(n–1)! = n·(n–1)·(n-2)! = … =
            n
·(n–1)·(n-2)··3·2·1! =                                                                                  [5]
            n
·(n–1)·(n-2)··3·2·1

At this point, the original definition of n! in [1] has been recreated.

This [2] is called a recursive definition of n! . It has been said anonymously that, “in order to understand recursion, one must first understand recursion”.

In Computer Programming, n! can be determined via an iterative set of instructions, involving looping. Also, n! can be determined via a recursively called function or program, which calls itself repeatedly.

The Rosetta Code.org Wiki for factorial lists approximately 179 different programming languages with both iterative and recursive factorial code segments. It’s quite impressive – See:
Factorial Programs and Functions – Rosetta Code

Within this listing are programs that are part of the Unix/Linux facilities: awk, bash, bc, dc, JavaScript, m4, perl, php, python, R, ruby, and Unix shells (sh, ksh, zsh). These programs do not require a compiler. In future posts, these will be examined more closely.

There’s much more to factorials, which I will defer to further posts .

It has been suspected that mathematicians invented the factorial symbol (!) as a way of making mathematics look more exciting; after all, as the value of n increases, its factorial increases incredibly fast.