Odstraneni rekurze

TECHNIKA: ODSTRANĚNÍ REKURZE

Mnoho algoritmů z různých aplikačních oblastí může být zapsáno stručněji a jasněji v rekurzívní formě. Uveďme si naopak příklad programu, který by nikdy v rekurzívní formě neměl být používán. Jde o výpočet Fibonacciho čísel, přičemž program přímo vychází z jejich definice:

F₀=0; F₁=1; F_N=F_N-1+F_N-2

Budeme-li F chápat jako funkci dostaneme se k programu

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)

Tento program ale úplně zbytečně opakuje znovu a znovu tytéž výpočty a jeho složitost proto roste exponenciálně!
Budeme-li F v definici chápat jako pole, dostaneme se přímo k iterativnímu programu:

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

Ve skutečnosti není nutné používat celé pole; potřebujeme jen dvě proměnné, které by uchovaly hodnoty potřebné pro výpočet dalšího Fibonacciho čísla. Ten správný, jednoduchý a rychlý program vypadá takto:

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

Dalším adeptem na rekurzívní program je Euklidův algoritmus na výpočet největšího společného dělitele. Rekurzívní definice

NSD(A, B) = NSD(B, A mod B)

nás přivede k rekurzívní funkci

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

Poslední akcí funkce je rekurzívní volání sebe sama. Tento typ rekurze může být snadno transformován na iteraci, zaměníme-li rekurzívní volání příkazy přiřazení a cyklem do while:

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

Rekurze je cenný nástroj, který umožňuje programátorovi soustředit se na klíčové prvky algoritmu a nezabývat se podrobnostmi (... aplikuj tutéž akci na podroblém menšího rozsahu!). Nádherným příkladem je slavný QUICKSORT.

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

Rekurzívní volání může být obecně eliminováno pomocí zásobníku. V následujícím programu jsem v roli zásobníku použil externí datovou frontu.

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

Průměrnou dobu výpočtu po deseti pokusech porovnávající rekurzívní, iterativní a sofistikovanou verzi QUICKSORTu pro N=100,1000,10000 uvádí následující tabulka

Porovnání algoritmů
Algoritmus N=100 N=1000 N=10000

Rekurzívní 0.060 0.489 7.410

Iterativní 0.043 0.386 6.904

Sofistikovaný 0.034 0.323 5.997

DALŠÍ PŘÍKLADY
Diofantova rovnice
Minimum a maximum současně

Literatura
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