Factorial function

Got it! This site "www.robinsnyder.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.

The factorial function can be used to calculate the number of permutations of n objects. The mathematical definition is as follows, using "*" for multiplication.

fact(0) = 1 fact(n) = n * fact(n-1) , n > 0

Do you see a way to program the factorial function (top-down) using this definition?

Note that this definition is recursive in that it refers to itself. The factorial function grows quickly.

n! = n * (n-1) * (n-2) * ... * 1 0! = 1 1! = 1 2! = 2 * 1 = 2 3! = 3 * 2 * 1 = 6 4! = 4 * 3 * 2 * 1 = 24 5! = 5 * 4 * 3 * 2 * 1 = 120 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720 7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5,040 ... 10! is more than 3,600,000

Do you see a way to program the factorial function bottom-up using the above pattern? 7 factorial

The factorial function grows rapidly. Here is a graphical depiction of 7! = 5,040.

59! is about 1080

10⁸⁰is the number of baryons (electrons, protons, neutrons, etc.) in the known universe.

The main program code is the same for both versions of the code.

int f1;
printf("Factorials:\n");
for (int i1=0; i1 <= 10; i1++) {
	f1 = fact(i1);
	printf("\t%d! is %d\n",i1,f1);
	}

Here is an iterative factorial function (bottom up version).

int fact(int n1) {
	int f1 = 1;
	while (n1 != 0) {
		f1 *= n1;
		n1--;
		}
	return f1;
	}

It is called "iterative" because it has a loop. Pure recursive functions use recursion instead of loops, using recursion to do iteration.

Here is the C code [#3]

#include <stdio.h>
// iterative factorial function
int fact(int n1) {
	int f1 = 1;
	while (n1 != 0) {
		f1 *= n1;
		n1--;
		}
	return f1;
	}
int main() {
	int f1;
	printf("Factorials:\n");
	for (int i1=0; i1 <= 10; i1++) {
		f1 = fact(i1);
		printf("\t%d! is %d\n",i1,f1);
		}
	return 0;
	}

Here is the output of the C code.

Factorials:
	0! is 1
	1! is 1
	2! is 2
	3! is 6
	4! is 24
	5! is 120
	6! is 720
	7! is 5040
	8! is 40320
	9! is 362880
	10! is 3628800

Here is the recursive factorial function.

int fact(int n) {
	if (n == 0) {
		return 1;
		}
	else {
		return n * fact(n-1);
		}
	}

Here is the math definition, using "*" for multiplication.

fact(0) = 1 fact(n) = n * fact(n-1) , n ≠ 0

Here is the same recursive factorial function written slightly differently.

int fact(int n) {
	int f1 = 1;
	if (n == 0) {
		f1 = 0;
		}
	else {
		f1 = n * fact(n-1);
		}
	return f1;
	}

The return is done at the end of the function. Here is the same program using a recursive function (the first one).

Here is the C code [#6]

#include <stdio.h>
// recursive factorial function
int fact(int n) {
	if (n == 0) {
		return 1;
		}
	else {
		return n * fact(n-1);
		}
	}
int main() {
	int f1;
	printf("Factorials:\n");
	for (int i1=0; i1 <= 10; i1++) {
		f1 = fact(i1);
		printf("\t%d! is %d\n",i1,f1);
		}
	return 0;
	}

Here is the output of the C code.

Factorials:
	0! is 1
	1! is 1
	2! is 2
	3! is 6
	4! is 24
	5! is 120
	6! is 720
	7! is 5040
	8! is 40320
	9! is 362880
	10! is 3628800

Technical note: Tail recursion in the recursive version makes it easy to convert to iteration.

This improvement can be used in functional language, logic languages, and imperative languages.

This saves time and space since it avoids extra push and pops of the stack.

Problem: Redundant calculations are done.

Solution: Use memoization (behind the scenes) by trading more memory space for less computation time. Memoization is from the Latin word "memorandum" which comes from the Greek «μνεμονικόυς» from the PIE (Proto Indo-European) for "men" or "think" (comment, amnesia, mental, memento, etc.).

Memoization is often done for compiled regular expressions, SQL queries, etc. Space can be traded for time by using the hash of the text and not the text itself.

The browser cache is a form of memoization.