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 (n1)\times n$ (with the same assignment for zero factorial). Either of these suggests implementation with some kind of FOR
loop.
The recurrence relation $n!=(n1)!n$ with $n>1$ and $1!=1$ suggests a recursive implementation.

1.
Test if
N <= 0
. If so, return 1. 
2.
If not, then call the recursive factorial algorithm with
N  1
, multiply the result byN
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 $n1$ would be pushed on to the stack. The next time $n2$ 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 nexttolast instance pops a 1 off the stack and multiplies it by 2, the nexttonexttolast 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 $(n1)!$ 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 32bit 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 32bit unsigned integer variable. Therefore input sizes should be limited to fit within the bounds of memory and integer capacity.
References
 1 B. Allan, Introducing Pascal. London: Granada (1984): 56  57
 2 J. G. P. Barnes, Programming in ADA. Wokingham: AddisonWesley (1989): 117
 3 A. I. Hollub, The C Companion. Englewood Cliffs: PrenticeHall, Inc. (1987): 190  195
 4 R. Kemp, PASCAL for Students. London: Edward Arnold (1987): 106
 5 E. Koffman, Problem Solving and Structured Programming in PASCAL. Reading: AddisonWesley Publishing Company (1981): 317
Title  recursive algorithm for factorial function 

Canonical name  RecursiveAlgorithmForFactorialFunction 
Date of creation  20130322 17:26:35 
Last modified on  20130322 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 