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. Kategoria:Rekurencja