Technique: Recursion elimination

Many algorithms from a variety of applications can be expressed most clearly and succintly in a recursive manner. One such unadvisable example of a recursive program is the computation of the Fibonacci Numbers, which are defined by the recurrence relation

F0=0; F1=1; FN=FN-1+FN-2

The recursive function closely follows the definition, where F we consider as the calling of the function

 FIB: procedure parse arg N if N <= 0 then return 0   else if N = 1 then return 1     else return FIB(N - 1) + FIB(N - 2)

This recursive function needlessly repeats the same calculations over and over and the amount of time used by the FIB function grows exponentially!
When we will consider F in the definition as an array then we can write a fast straightforward iterative program

 FIB: procedure parse arg N F.0 = 0; F.1 = 1 do J = 2 to N   Jm1 = J - 1; Jm2 = J - 2   F.J = F.Jm1 + F.Jm2 end return F.N

We can produce a simpler iterative program by noting that we can start at 0 and keep only two variables and not the whole array.

 FIB: procedure parse arg N if N = 0 | N = 1 then return N A = 0; B = 1 do N - 1   parse value(B (B + A)) with A B end return B

And there is Euclid's algorithm for computation of the greatest common divisor (GCD) of two positive integers. It is based on the following recursion theorem:

GCD(A, B) = GCD(B, A mod B)

 GCD: procedure parse arg A, B if B = 0 then return A   else return GCD(B, A // B)

The very last action of the function is to make a recursive call to itself. That program use "tail recursion". It can always be transformed to iteration by replacing function calls by assignment and do while loop statements. The iterative version of GCD is shown:

 GCD: procedure parse arg A, B do while B > 0   parse value(B A//B) with A B end return A

Recursion is a valuable programming tool to allow programmer to concentrate on the key step of an algorithm, without having initially to worry about coupling that step with all the others ("... reapply the action to a smaller part of the problem!"). The wonderful example is the original version of the famous QUICKSORT algorithm.

 QUICKSORT_RECURSIVE: procedure expose A. parse arg L, R if L < R then do   Q = PARTITION(L, R)   call QUICKSORT_RECURSIVE L, Q   call QUICKSORT_RECURSIVE Q + 1, R end return   PARTITION: procedure expose A. parse arg L, R X = A.L; I = L - 1; J = R + 1; do forever   do until A.J <= X; J = J - 1; end   do until A.I >= X; I = I + 1; end   if I < J     then do; W = A.I; A.I = A.J; A.J = W; end     else return J end

The recursive call can be eliminated by using a stack. I used the External Data Queue as the stack.

 QUICKSORT_ITERATIVE: procedure expose A. parse arg L, R push L R do while QUEUED() > 0   pull L R   if L < R     then do       Q = PARTITION(L, R)       push L Q; push Q + 1 R     end end return

The average time over 10 trials required by iterative and recursive version of QUICKSORT and sophisticated version of QUICKSORT for N=100,1000,10000 was found experimentally

Comparisons of Algorithms
Algorithms N=100 N=1000 N=10000
Recursive 0.060 0.489 7.410
Iterative 0.043 0.386 6.904
Sophisticated 0.034 0.323 5.997

ANOTHER EXAMPLES

Literature
Kruse R. L. Data Structures and Program Design
Prentice Hall International Editions, ISBN 0-13-196049-0.
Bird R. S. Notes on Recursion Elimination
CACM, June 1977, vol. 20, No. 6, pp. 434-439.
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990

 cover contents index main page