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

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.

mail