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:

21*2= 2
31*2*3 = 6
41*2*3*4 = 24
51*2*3*4*5 = 120

which may be stated recursively as

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

See Tom Kelliher web page at 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

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

Last Updated on 27 February 2000
By Herbert J. Bernstein