Derekursywacja
Derekursywacja to proces przekształcania algorytmu rekurencyjnego w odpowiadający mu algorytm iteracyjny. Algorytmy rekurencyjne są często łatwiejsze do zrozumienia, jednak mogą być obciążone wysoką złożonością obliczeniową i pamięciową, co wpływa na ich wydajność. W przeciwieństwie do nich, algorytmy iteracyjne są zazwyczaj bardziej zgodne z architekturą procesorów, co przekłada się na szybsze działanie i mniejsze zużycie pamięci, eliminując kosztowną obsługę stosu wywołań.
Przykład obliczania liczb Fibonacciego
Rozważmy rekurencyjny algorytm obliczania n-tej liczby ciągu Fibonacciego, który ilustruje indukcyjną definicję matematyczną:
podprogram fibonacci(n):
jeżeli n < 2, to zwróć n.
zwróć fibonacci(n - 1) + fibonacci(n - 2).
Ten algorytm charakteryzuje się wykładniczą złożonością czasową oraz liniową złożonością pamięciową. Po derekursywacji uzyskujemy algorytm iteracyjny:
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
Choć zaprezentowany algorytm nie jest najszybszym sposobem obliczania liczb Fibonacciego, ilustruje korzyści płynące z derekursywacji.
Podsumowanie
- Derekursywacja przekształca algorytmy rekurencyjne w iteracyjne.
- Algorytmy iteracyjne są bardziej wydajne pod względem czasu i pamięci.
- Przykład algorytmu Fibonacciego pokazuje różnice w złożoności.
