recursive algorithm for factorial function

When it came to teaching recursion in programming languages in the 1980s and 1990s, the factorial function $n!$ was the classic example to explain the concept.

Usually left unexplained, in a mathematical paper or book one might encounter an explanation for the $n!$ shorthand for this function along the lines of

$$n!=\prod _{i=1}^{n}i,$$

(with $0!=1$) while a computer programming book might say something like $n!=1\times 2\times \mathrm{\dots }\times (n-1)\times n$ (with the same assignment for zero factorial). Either of these suggests implementation with some kind of FOR loop.

The recurrence relation $n!=(n-1)!n$ with $n>1$ and $1!=1$ suggests a recursive implementation.

Call the recursive factorial algorithm with an integer N.

1. Test if N <= 0. If so, return 1.

2. If not, then call the recursive factorial algorithm with N - 1, multiply the result by N and return that value.

The algorithm calls itself and some mechanism is necessary for keeping track of the state of the computation. Here’s an implementation in the PASCAL programming language from Koffman’s 1981 book:

FUNCTION FACTORIAL (N: INTEGER): INTEGER
(* RECURSIVE COMPUTATION OF N FACTORIAL *)

BEGIN
  (* TEST FOR STOPPING STATE *)
  IF N <= 0 THEN
    FACTORIAL := 1
  ELSE
    FACTORIAL := N * FACTORIAL(N - 1)
END; (* FACTORIAL *)

Depending on the implementation, what would happen the first time FACTORIAL(N) calls itself is that the memory address of the function together with $n-1$ would be pushed on to the stack. The next time $n-2$ would be pushed on the stack, and so on and so forth until 0 is reached. At this point, the last instance of the function returns, the next-to-last instance pops a 1 off the stack and multiplies it by 2, the next-to-next-to-last instance pops a 2 off the stack and multiplies it by 3, pushes a 6, and so on and so forth until the first instance pops $(n-1)!$ off the stack and multiplies it by $n$.

The following table illustrates a sample run starting with N = 7:

Action	N	Return value
Call factorial function with value	7	Undefined
Call factorial function with value	6	Undefined
Call factorial function with value	5	Undefined
Call factorial function with value	4	Undefined
Call factorial function with value	3	Undefined
Call factorial function with value	2	Undefined
Call factorial function with value	1	Undefined
Call factorial function with value	0
Return a 1		1
Multiply returned value by N and return that	1	1
Multiply returned value by N and return that	2	2
Multiply returned value by N and return that	3	6
Multiply returned value by N and return that	4	24
Multiply returned value by N and return that	5	120
Multiply returned value by N and return that	6	720
Multiply returned value by N and return that	7	5040

This kind of recursion can exhaust memory (for stack space) well before any computations are performed. However, in this specific application, because factorials grow super exponetially, the bounding for integer capacity is usually far more restricting than the memory capacity. For example, using 32-bit unsigned integers and guesstimating each function call requires 16 bytes, the computation of 13! would require just 208 bytes on the stack, but the result would require 33 bits, overflowing a 32-bit unsigned integer variable. Therefore input sizes should be limited to fit within the bounds of memory and integer capacity.

Title	recursive algorithm for factorial function
Canonical name	RecursiveAlgorithmForFactorialFunction
Date of creation	2013-03-22 17:26:35
Last modified on	2013-03-22 17:26:35
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	5
Author	PrimeFan (13766)
Entry type	Algorithm
Classification	msc 11B65
Classification	msc 05A10