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 $n$ ($n!$).

Example 3.8   Factorial Computation: Given $n \geq 0$, compute factorial of $n$ ($n!$)^3.1.
rfactorial.nw0Recall the inductive definition of $n!$ given inExample 2.1. On the basis of the inductive definition, we can define a functional algorithm for computing $factorial(n)$, which is of the type $factorial: \mathbb{N}\rightarrow \mathbb{N}$ as

$$factorial(n) = \left\{ \begin{array}... ...{if $n = 0$} \\ n \times factorial(n-1) & \mbox{otherwise} \end{array}\right.$$

Here $factorial(n)$ 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 $n = 5$, looks as follows

$${factorial(5)}$$

$$= (5 \times factorial(4))$$

$$= (5 \times (4 \times factorial(3)))$$

$$= (5 \times (4 \times (3 \times factorial(2))))$$

$$= (5 \times (4 \times (3 \times (2 \times factorial(1)))))$$

$$= (5 \times (4 \times (3 \times (2 \times (1 \times factorial(0))))))$$

$$= (5 \times (4 \times (3 \times (2 \times (1 \times 1)))))$$

$$= (5 \times (4 \times (3 \times (2 \times 1))))$$

$$= (5 \times (4 \times (3 \times 2)))$$

$$= (5 \times (4 \times 6))$$

$$= (5 \times 24)$$

$$= 120$$

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 $factorial(0)$ 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 $f: \mathbb{N}\rightarrow \mathbb{Z}$ defined just like factorial except that multiplication is replaced by subtraction which is not associative.

$$f(n) = \left\{ \begin{array}{ll} 1 & \mbox{if $n = 0$} \\ n - f(n-1) & \mbox{otherwise} \end{array}\right.$$

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