Różnica między rekurencją a iteracją
Zawartość
Zarówno rekurencja, jak i iteracja wielokrotnie wykonują zestaw instrukcji. Rekurencja występuje, gdy instrukcja w funkcji wywołuje się wielokrotnie. Iteracja ma miejsce, gdy pętla jest wykonywana wielokrotnie, aż warunek kontrolny stanie się fałszywy. Podstawową różnicą między rekurencją a iteracją jest to, że rekurencja jest procesem, zawsze stosowanym do funkcji. The iteracja jest stosowany do zestawu instrukcji, które chcemy wielokrotnie wykonywać.
- Wykres porównania
- Definicja
- Kluczowe różnice
- Wniosek
Wykres porównania
Podstawa do porównania | Rekurencja | Iteracja |
---|---|---|
Podstawowy | Instrukcja w treści funkcji wywołuje samą funkcję. | Umożliwia wielokrotne wykonywanie zestawu instrukcji. |
Format | W funkcji rekurencyjnej określony jest tylko warunek zakończenia (przypadek podstawowy). | Iteracja obejmuje inicjalizację, warunek, wykonanie instrukcji w pętli oraz aktualizację (inkrementację i dekrementację) zmiennej kontrolnej. |
Zakończenie | W treści funkcji zawarta jest instrukcja warunkowa, aby zmusić funkcję do powrotu bez wykonywania wywołania rekurencyjnego. | Instrukcja iteracji jest wykonywana wielokrotnie, dopóki nie zostanie spełniony określony warunek. |
Stan | Jeśli funkcja nie jest zbieżna z jakimś warunkiem zwanym (przypadek podstawowy), prowadzi to do nieskończonej rekurencji. | Jeśli warunek kontrolny w instrukcji iteracji nigdy nie stanie się fałszywy, prowadzi to do nieskończonej iteracji. |
Nieskończone powtarzanie | Nieskończona rekurencja może spowodować awarię systemu. | Pętla nieskończona wielokrotnie wykorzystuje cykle procesora. |
Stosowany | Rekurencja jest zawsze stosowana do funkcji. | Iteracja jest stosowana do instrukcji iteracji lub „pętli”. |
Stos | Stos służy do przechowywania zestawu nowych zmiennych lokalnych i parametrów przy każdym wywołaniu funkcji. | Nie używa stosu. |
Nad głową | Rekurencja ma narzut związany z powtarzanymi wywołaniami funkcji. | Bez kosztów powtarzalnych wywołań funkcji. |
Prędkość | Powolny w realizacji. | Szybka realizacja. |
Rozmiar kodu | Rekurencja zmniejsza rozmiar kodu. | Iteracja powoduje, że kod jest dłuższy. |
Definicja rekurencji
C ++ pozwala funkcji wywoływać się w swoim kodzie. Oznacza to, że definicja funkcji zawiera wywołanie funkcji. Czasami nazywa się to również „okrągła definicja„. Zestaw zmiennych lokalnych i parametrów używanych przez funkcję jest nowo tworzony za każdym razem, gdy funkcja się wywołuje, i są przechowywane na górze stosu. Ale za każdym razem, gdy funkcja się wywołuje, nie tworzy nowej kopii tej funkcji. Funkcja rekurencyjna nie zmniejsza znacząco rozmiaru kodu i nawet nie poprawia wykorzystania pamięci, ale robi to w porównaniu z iteracją.
Aby zakończyć rekurencję, musisz uwzględnić instrukcję select w definicji funkcji, aby zmusić funkcję do powrotu bez wywoływania rekurencyjnego dla siebie. Brak instrukcji select w definicji funkcji rekurencyjnej pozwoli na wywołanie funkcji w nieskończonej rekurencji.
Zrozummy rekurencję z funkcją, która zwróci silnię liczby.
int silnia (int num) {int odpowiedź; if (num == 1) {return 1; } else {answer = silnia (num-1) * num; // wywołanie rekurencyjne} return (answer); }
W powyższym kodzie instrukcja w else else pokazuje rekurencję, ponieważ instrukcja wywołuje funkcję silnią (), w której się znajduje.
Definicja iteracji
Iteracja to proces wielokrotnego wykonywania zestawu instrukcji, aż warunek w instrukcji iteracji stanie się fałszywy. Instrukcja iteracji obejmuje inicjalizację, porównanie, wykonanie instrukcji wewnątrz instrukcji iteracji i wreszcie aktualizację zmiennej kontrolnej. Po aktualizacji zmiennej kontrolnej jest ona ponownie porównywana, a proces powtarza się, aż warunek w instrukcji iteracji okaże się fałszywy. Instrukcje iteracyjne to pętla „for”, „while”, „do-while”.
Instrukcja iteracji nie używa stosu do przechowywania zmiennych. Dlatego wykonanie instrukcji iteracji jest szybsze w porównaniu do funkcji rekurencyjnej. Nawet funkcja iteracji nie ma narzutu powtarzających się wywołań funkcji, które sprawiają, że jej wykonywanie jest szybsze niż funkcja rekurencyjna. Iteracja zostaje zakończona, gdy warunek kontroli stanie się fałszywy. Brak warunku kontrolnego w instrukcji iteracji może spowodować nieskończoną pętlę lub błąd kompilacji.
Przyjrzyjmy się iteracji dotyczącej powyższego przykładu.
int silnia (int num) {int answer = 1; // wymaga inicjalizacji, ponieważ może zawierać niepotrzebną wartość przed inicjalizacją dla (int t = 1; t> num; t ++) // iteracja {answer = answer * (t); powrót (odpowiedź); }}
W powyższym kodzie funkcja zwraca silnię liczby za pomocą instrukcji iteracji.
- Rekurencja ma miejsce, gdy metoda w programie wielokrotnie się wywołuje, natomiast iteracja następuje, gdy zestaw instrukcji w programie jest wielokrotnie wykonywany.
- Metoda rekurencyjna zawiera zestaw instrukcji, instrukcję wywołującą samą siebie i warunek zakończenia, podczas gdy instrukcje iteracji zawierają inicjalizację, przyrost, warunek, zestaw instrukcji w pętli i zmienną kontrolną.
- Instrukcja warunkowa decyduje o zakończeniu rekurencji, a wartość zmiennej kontrolnej decyduje o zakończeniu instrukcji iteracji.
- Jeśli metoda nie prowadzi do warunku zakończenia, przechodzi w nieskończoną rekurencję. Z drugiej strony, jeśli zmienna kontrolna nigdy nie prowadzi do wartości końcowej, instrukcja iteracji iteruje w nieskończoność.
- Nieskończona rekurencja może prowadzić do awarii systemu, podczas gdy nieskończona iteracja pochłania cykle procesora.
- Rekurencja jest zawsze stosowana do metody, podczas gdy iteracja jest stosowana do zestawu instrukcji.
- Zmienne utworzone podczas rekurencji są przechowywane na stosie, podczas gdy iteracja nie wymaga stosu.
- Rekurencja powoduje narzut powtarzanych wywołań funkcji, podczas gdy iteracja nie ma narzutu wywołującego funkcję.
- Z powodu wywoływania funkcji wykonywanie rekurencji narzutów jest wolniejsze, natomiast wykonywanie iteracji jest szybsze.
- Rekurencja zmniejsza rozmiar kodu, a iteracje wydłużają kod.
Wniosek:
Funkcja rekurencyjna jest łatwa do napisania, ale nie działają one dobrze w porównaniu z iteracją, podczas gdy iteracja jest trudna do napisania, ale ich wydajność jest dobra w porównaniu z rekurencją.