|
Note that this HTML page was
generated from Word 2000. Some
of the code cannot be pasted into Qi. You are advised to download the program
files through the above link. 3 Recursion 3.1 Recursion and Infinity___________________ Programmers using procedural languages are familiar with the idea of creating procedures
that call themselves. If we wish to count the number of words in a file, then
we could set up a procedure which reads the words one at a time, incrementing
a counter, until the file is empty.
At this point the value in counter is returned as a result. A procedure of this
kind has to be set up to call itself as many times as is necessary for all
the words in the file to be counted up. In functional programming there is
an elegant mechanism called recursion that
enables functions to call themselves. Recursion can be illustrated through
equational approach of the previous chapter; our example is the problem of
defining the factorial function.
The factorial of an integer is the result of multiplying that integer
by the integers less than it down to 1. By convention factorial(0) = 1. We
start writing a series of equations to define the factorial function (figure 3.1). factorial(0) = 1 factorial(1) = 1 ´ 1 = 1 factorial(2) = 2 ´ 1 = 2 factorial(3) = 3 ´ 2 ´ 1 = 6 factorial(4) = 4 ´ 3 ´ 2 ´ 1 = 24 factorial(5) = 5 ´ 4 ´ 3 ´ 2 ´ 1 = 120 factorial(6) = 6 ´ 5 ´ 4 ´ 3 ´ 2 ´ 1 = 720 Figure 3.1 Part of an infinite series of equations for the factorial function The problem is that there are an
infinite number of such equations. Can we somehow reduce this infinite set of equations to
something finite and of a manageable size? Yes, we can, through the device of
recursion. If we examine these equations, they all fit a common
pattern. Above 0, the factorial of any integer is the result of multiplying that integer by
the factorial of the integer one less than it. factorial(0) = 1 factorial(1) = 1 ´ factorial(0) = 1 ´ 1 = 1 factorial(2) = 2 ´ factorial(1) = 2 ´ 1 = 2 factorial(3) = 3 ´ factorial(2) = 3 ´ 2 = 6 factorial(4) = 4 ´ factorial(3) = 4 ´ 6 = 24 factorial(5) = 5 ´ factorial(4) = 5 ´ 24 = 120 factorial(6) = 6 ´ factorial(5) = 6 ´ 120 = 720 Figure 3.2
Isolating the pattern within the equations in 3.1 This allows us to use two equations in place of the infinite list we started with (figure 3.3). factorial(0) = 1 where X > 0, factorial(X) = X ´ factorial(X - 1) Figure 3.3
The equations that define the factorial function The second equation includes the
proviso that X > 0. In representing these equations in Qi, we can take advantage of the fact that Qi tries
rewrite rules in the order in which they appear in a function definition. If
the first and second equations become the first and second rewrite rules in
the definition of factorial, the ordering guarantees that Qi
tries the second rule (supposing the input to be a natural number), only when
the input is greater than 0. In that case the two equations can be combined
into one Qi definition without having to explicitly say that X > 0 (figure
3.4). (define factorial
0 -> 1 X -> (* X (factorial (- X 1)))) Figure 3.4
The factorial function in Qi Entering this function to Qi shows
it to work. (59-) (factorial 6) 720 The calculation of the factorial of any integer > 0 depends on calculating the factorial of
the integer one less than it. Thus, the Qi factorial function calls itself n+1
times for any natural number n and having reached zero, executes all
the deferred multiplications. 3.2 Tail and Linear Recursion________________ The equational definition
of factorial in figure 3.4 shows the typical anatomy of a recursive function. The first equation factorial(0) = 1 gives the base
case of the
recursive definition; this provides a point where the function ceases to call
itself. The base case corresponds to a condition within a procedural loop that causes the loop to be exited. The second equation, (where X > 0,
factorial(X) = X ´ factorial(X
- 1)), corresponds to the recursive case where the
function calls itself. The
recursive case corresponds to the condition within a loop that causes the
loop to be repeated. In the
example there is one base case and one recursive case, though in other
definitions there can be several of each. Once the base case zero is reached, the computation does not cease since the
recursive outputs of factorial have to be multiplied
to give the answer. We can rewrite our definition of factorial so that
the answer is returned on reaching the base case (figure 3.5). (define factorial X -> (factorial1 X 1)) (define factorial1 0 Accum -> Accum X Accum -> (factorial1 (- X 1) (* X Accum))) Figure 3.5 A
tail recursive definition of factorial Our new definition of factorial passes its
input X to an auxiliary or help function called factorial1
that helps to define factorial.
The definition of factorial1 contains an extra input (an accumulator)
Accum, which totals the value calculated for factorial. When the base case 0 is reached, returning the accumulator gives the
correct answer. The two different versions of factorial are
almost identical, and yet they display different patterns of computation. In the first version, the necessary multiplications are
postponed till the end of the recursion. Carrying out this process requires that the computer
remember the multiplications to be performed later. The length of the chain
of operations, and hence the amount of information needed to keep account of
the computation, grows in linear proportion to the value of X. Such a recursion is called linear recursion.
In the second case, the necessary multiplications are performed during
the recursion, and the memory used to keep track of the computation is
virtually constant. This recursion, tail recursion, is the more efficient form of recursion. Addition is another example of a
recursive arithmetic function. The problem is to recursively define
an addition function called “plus” over natural numbers, using only
operations which add 1 to or subtract 1 from a number. To begin we write a
series of equations giving specific inputs to plus and the corresponding
results. plus(X,0) = X plus(X,1) = 1 + (plus(X,0)) plus(X,2) = 1 + (plus(X,1)) plus(X,3) = 1 + (plus(X,2)) Figure 3.6
Part of an infinite series of equations for addition Apart from the first equation (the model |