Next: Analysis of correctness and Up: A functional model of Previous: Functions as inductively defined   Contents

Recursive processes

Recursive computational processes are characterized by a chain of deferred operations. As an example, we will consider an algorithm for computing the factorial of an integer ().

Example 3.8   Factorial Computation: Given , compute factorial of ()3.1.
rfactorial.nw0Recall the inductive definition of given inExample 2.1. On the basis of the inductive definition, we can define a functional algorithm for computing , which is of the type as

Here is the function name'' and the description after the sign is the body'' of the function. A ML program for the above algorithm looks as follows: 1Factorial fun factorial (n) = if n = 0 then 1 else n * factorial (n-1); It is instructive to examine the computational process underlying the above definition. The computational process, in the special case of , looks as follows

A computation such as this is characterized by a growing and shrinking process. In the growing phase each call'' to the function is replaced by its body'' which in turn contains a call'' to the function with different arguments. In order to compute according to the inductive definition, the actual multiplications will have to be postponed till the base case of can be evaluated. This results in a growing process. Once the base value is available, the actual multiplications can be carried out resulting in a shrinking process. Computational processes which are characterized by such deferred'' computations are called recursive. This is not to be confused with the notion of a recursive procedure which just refers to the syntactic fact that the procedure is described in terms of itself.

Note that by a computational process we require that a machine, which has only the capabilities provided by the computational model, be able to perform the computation. A human normally realizes that multiplication is commutative and associative and may exploit it so that he does not have to defer performing the multiplications. However if the multiplication operation were to be replaced by a non-associative operation then even the human would have to defer the operation. Thus it becomes necessary to perform all recursive computations through deferred operations.

Exercise 3.1   Consider the following example of a function defined just like factorial except that multiplication is replaced by subtraction which is not associative.

1. Unfold the computation, as in the example of above, to show that .
2. What properties will you use as a human computer in order to avoid deferred computations?

Next: Analysis of correctness and Up: A functional model of Previous: Functions as inductively defined   Contents
Subhashis Banerjee 2003-08-02