Derekursywacja

Derekursywacja – przekształcenie algorytmu rekursyjnego w odpowiadający mu funkcjonalnie algorytm iteracyjny. Choć algorytmy rekurencyjne bywają prostsze do zrozumienia, to obarczone są jednak zwykle dużą złożonością obliczeniową lub pamięciową (zob. asymptotyczne tempo wzrostu): algorytmy iteracyjne bliższe są zwykle architekturze procesorów (a dokładniej ich modelom programowym), przez co zwykle są szybsze i zużywają mniej pamięci (największym obciążeniem jest przeważnie kosztowna obsługa stosu wywołań).

Przykład

Następujący rekurencyjny algorytm obliczania n-tej liczby ciągu Fibonacciego naśladuje indukcyjną definicję matematyczną:

podprogram fibonacci(n):
    jeżeli n < 2, to zwróć n.
    zwróć fibonacci(n - 1) + fibonacci(n - 2).

Nie jest on wydajny ze względu na wykładniczą (względem wartości argumentu n) złożoność czasową i liniową złożoność pamięciową. Jego derekursywacja daje algorytm iteracyjny o liniowej złożoności czasowej i stałej − pamięciowej:

podprogram fibonacci(n):
    jeżeli n < 2, to zwróć n
    niech przedostatnia = 0
    niech      ostatnia = 1
    wykonaj n - 1 razy:
        niech      ostatnia = ostatnia + przedostatnia
        niech przedostatnia = ostatnia - przedostatnia
    zwróć ostatnia

Na marginesie dodać należy, że przedstawiony powyżej algorytm nie jest jeszcze najszybszym sposobem obliczania liczb Fibonacciego, jest jednak czytelnym przykładem zysków płynących z derekursywacji.