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:

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.