Technique: Recursion elimination

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

F₀=0; F₁=1; F_N=F_N-1+F_N-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
Diophantine linear equation
Minimum and Maximum at the same time

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