Różnice między algorytmami iteracyjnymi a rekurencyjnymi

Zarówno iteracja, jak i rekurencja są oparte na strukturze kontrolnej: iteracja używa struktury powtarzania; rekurencja używa struktury wyboru. Algorytm iteracyjny użyje instrukcji pętli, takich jak pętla for, pętla lub pętla do-while, aby powtórzyć te same kroki, podczas gdy algorytm rekurencyjny, moduł (funkcja) wywołuje się ponownie, dopóki warunek podstawowy (warunek zatrzymania) nie zostanie spełniony.

Algorytm iteracyjny będzie szybszy niż algorytm rekurencyjny z powodu narzutów, takich jak funkcje wywołujące i wielokrotne rejestrowanie stosów. Często algorytmy rekurencyjne nie są wydajne, ponieważ zabierają więcej miejsca i czasu.

Algorytmy rekurencyjne są najczęściej używane do rozwiązywania skomplikowanych problemów, gdy ich aplikacja jest łatwa i skuteczna. Na przykład algorytm Wieże Hanoi jest łatwy dzięki rekurencji, podczas gdy iteracje są szeroko stosowane, wydajne i popularne.

Algorytmy rekurencyjne a iteracyjne:

  • Podejście: w podejściu rekurencyjnym funkcja wywołuje się, dopóki warunek nie zostanie spełniony, natomiast w podejściu iteracyjnym funkcja powtarza się, dopóki warunek nie powiedzie się (tj. nie jest już spełniony).
  • Programowanie: Algorytm rekurencyjny wykorzystuje strukturę rozgałęzień, a algorytm iteracyjny wykorzystuje konstrukcję pętli.
  • Czas i przestrzeń: rozwiązania rekurencyjne są często mniej wydajne pod względem czasu i przestrzeni w porównaniu z rozwiązaniami iteracyjnymi.
  • Test zakończenia: Iteracja kończy się, gdy warunek kontynuacji pętli kończy się niepowodzeniem; rekurencja kończy się, gdy rozpoznany zostanie podstawowy przypadek. Przypomnijmy, że algorytm jest rekurencyjny, jeśli sam się wywołuje. W algorytmie, który sam siebie wywołuje, warunek zakończenia musi być poprawny, aby algorytm ostatecznie się zakończył. Aby upewnić się, że algorytm się zakończy, dane wejściowe do kolejnego wykonania zmniejszają się za każdym razem o pewną liczbę, tak że w pewnym momencie w końcu dojdzie do zera i algorytm się zakończy. Wykonanie, które prowadzi do zera, jest przypadkiem podstawowym.
  • Nieskończone wywołanie: nieskończona pętla występuje z iteracją, jeśli test kontynuacji pętli nigdy nie staje się fałszywy; nieskończona rekurencja występuje, jeśli krok rekurencji nie zmniejsza problemu w sposób zbieżny w przypadku podstawowym.

Praktyczny problem: solenizant tnie tort urodzinowy i musi upewnić się, że wszyscy w pokoju dostają kawałek.

Rozwiązanie 1 – iteracyjne: Solenizant z okazji urodzin używa tacy i idzie nią, dając każdemu kawałek. Przyjmijmy algorytm iteracyjny pod nazwą daj_kawałek, który będzie wykonywany tyle razy, ile jest osób do obsłużenia lub tyle razy, ile jest kawałków do podania, niezależnie od tego, który warunek zostanie osiągnięty jako pierwszy.

daj_kawałek (podczas gdy istnieją ludzie do podania lub pozostały kawałki, daj kawałek)

Rozwiązanie 2 – Rekurencyjne: Weź kawałek ciasta z tacy i podaj tacę kolejnej osobie, która bierze plasterek z tacy i przekazuje tacę kolejnej osobie, która bierze plasterek z tacki i przekazuje tacę do następnej osoby…

Zauważ, że za każdym razem wykonywana jest ta sama funkcja.

weźkawałek(taca)
jeśli są osoby do obsłużenia albo zostały plasterki
weź kawałek i wykonaj weźkawałek(taca)
else return