By Herbert J. Bernstein

© Copyright 2000 Herbert J. Bernstein

The "natural" way to use a computer is by executing a program of instructions in sequence. We improve the readability of code and allow portions of it to be reused by making some sequences of code into sub-routines (or procedures). In a sense, every procedure returns a value -- the new state of the machine, but, when we clearly identify the returned value, we call the procedure a function.

If the steps in evaluation of a function require evaluation of the same function, we have "recursion". For example, we might view the definition of a language as a function which returns the strings which may appear in the language. If we wish to generate all the strings which contain one or more letters, we might do so iteratively:

<lstring> := <letter> { <letter> }*

or recursively with the recursive element first:

<lstring> := <letter> | <lstring> <letter>

or recursively with the recursive element last:

<lstring> := <letter> | <letter> <lstring>

Great care is needed in handling recursive definitions to ensure that we will complete evaluation in finite time.

Many mathematical functions are naturally defined recursively. For eaxmple, the factiorial of n (written "n!") is the product of all the strictly positive integers less than or equal to n, so that:

which may be stated recursively as

n! = n*(n-1)!
1! = 1

See Tom Kelliher web page at http://keystone.westminster.edu/~kelliher/cs18/feb23.html for more examples of recursion.

The major tool used to work with recursion is "mathematical induction" which may be stated as follows for any proposition P(n):

(P(0) & (for all n > 0, P(n-1) implies P(n))) implies (for all n > 0, P(n))

When a recursive call to the same function is the last step of a procedure, we have tail recursion, which can be implemented by looping back into the same code. See Paul Black's web page http://hissa.ncsl.nist.gov/~black/CRCDict/HTML/tailrecursn.html

In general iterations may be restated recursively, but not all recursions can be stated iteratively with bounds fixed on entry. The so-called primitive recursive functions can be computed iteratively, but, for example, Ackermann's function:

A(0,y) = y+1
A(x,0) = A(x-1,1)
A(x,y) = A(x-1,A(x,y-1))

cannot be computed using a loop with precomputed bounds, though it can be computed with a while loop. See Günter Dotzel's web page http://www.modulaware.com/mdlt08.htm