Różnica między rekurencją a iteracją
Share
Kluczowa różnica - rekurencja vs iteracja
Rekurencja i iteracja mogą być wykorzystane do rozwiązania problemów programistycznych. Podejście do rozwiązania problemu za pomocą rekurencji lub iteracji zależy od sposobu rozwiązania problemu. The kluczowa różnica między rekurencją a iteracją jest to rekurencja to mechanizm wywoływania funkcji w ramach tej samej funkcji, podczas gdy iteracja polega na wielokrotnym wykonywaniu zestawu instrukcji, dopóki dany warunek nie zostanie spełniony. Rekurencja i iteracja to główne techniki opracowywania algorytmów i tworzenia aplikacji.
ZAWARTOŚĆ
1. Przegląd i kluczowa różnica
2. Co to jest rekurencja
3. Co to jest iteracja
4. Podobieństwa między rekurencją a iteracją
5. Porównanie obok siebie - Rekurencja vs iteracja w formie tabelarycznej
6. Podsumowanie
Co to jest rekurencja?
Kiedy funkcja wywołuje się w obrębie funkcji, jest znana jako Rekurencja. Istnieją dwa rodzaje rekurencji. Są rekurencją skończoną i rekurencją nieskończoną. Skończona rekurencja ma warunek zakończenia. Nieskończona rekurencja nie ma warunku zakończenia.
Rekurencję można wyjaśnić za pomocą programu do obliczania silni.
n! = n * (n-1) !, jeśli n> 0
n! = 1, jeśli n = 0;
Odnieś poniższy kod, aby obliczyć silnię 3 (3! = 3 * 2 * 1).
intmain ()
wartość int = silnia (3);
printf („Silnia to% d \ n”, wartość);
zwraca 0;
intfactorial (intn)
jeśli (n == 0)
zwraca 1;
jeszcze
zwróć n * silnia (n-1);
Podczas wywoływania silnia (3), funkcja wywoła silnia (2). Podczas wywoływania silnia (2), funkcja wywoła silnia (1). Następnie silnia (1) wywoła silnię (0). silnia (0) zwróci 1. W powyższym programie, n == 0 warunek w „if block” jest warunkiem podstawowym. Podobnie, funkcja silnia jest wywoływana wielokrotnie.
Funkcje rekurencyjne są powiązane ze stosem. W C program główny może mieć wiele funkcji. Zatem main () jest funkcją wywołującą, a funkcja wywoływana przez program główny jest funkcją wywoływaną. Gdy funkcja jest wywoływana, kontrola jest nadawana funkcji wywoływanej. Po zakończeniu wykonywania funkcji sterowanie powraca do głównego. Następnie program główny jest kontynuowany. Tworzy więc rekord aktywacji lub ramkę stosu, aby kontynuować wykonywanie.
Rysunek 01: Rekurencja
W powyższym programie, wywołując silnię (3) z main, tworzy rekord aktywacyjny na stosie wywołań. Następnie tworzona jest rama stosu silnia (2) na szczycie stosu i tak dalej. Rekord aktywacji przechowuje informacje o zmiennych lokalnych itp. Za każdym razem, gdy wywoływana jest funkcja, na górze stosu tworzony jest nowy zestaw zmiennych lokalnych. Te ramki stosu mogą spowolnić przyspieszenie. Podobnie w rekurencji funkcja wywołuje się sama. Złożoność czasowa funkcji rekurencyjnej jest określana na podstawie liczby wywołań funkcji. Złożoność czasowa dla jednego wywołania funkcji wynosi O (1). Dla n liczby wywołań rekurencyjnych złożoność czasu wynosi O (n).
Co to jest iteracja?
Iteracja to blok instrukcji, który powtarza się wielokrotnie, aż dany warunek jest spełniony. Iterację można uzyskać za pomocą „for loop”, „do-while loop” lub „while loop”. Składnia „for loop” jest następująca.
dla (inicjalizacja; warunek; modyfikacja)
// sprawozdania;
Rysunek 02: „dla schematu przepływu w pętli”
Krok inicjalizacji jest wykonywany jako pierwszy. Ten krok polega na zadeklarowaniu i zainicjowaniu zmiennych sterujących pętli. Jeśli warunek jest spełniony, wykonywane są instrukcje w nawiasach klamrowych. Te instrukcje są wykonywane do momentu spełnienia warunku. Jeśli warunek jest fałszywy, formant przechodzi do następnej instrukcji po „pętli for”. Po wykonaniu instrukcji wewnątrz pętli formant przechodzi do modyfikacji sekcji. Jest to aktualizacja zmiennej kontrolnej pętli. Następnie warunek jest sprawdzany ponownie. Jeśli warunek jest spełniony, instrukcje wewnątrz nawiasów klamrowych zostaną wykonane. W ten sposób iteruje się „pętla for”.
W „pętli while”, instrukcje wewnątrz pętli są wykonywane do momentu spełnienia warunku.
while (warunek)
//sprawozdania
W pętli „do-while”, warunek jest sprawdzany na końcu pętli. Pętla wykonuje się co najmniej raz.
robić
//sprawozdania
while (warunek)
Program do znajdowania silni 3 (3!) Za pomocą iteracji („dla pętli”) jest następujący.
int main ()
intn = 3, silnia = 1;
inti;
dla (i = 1; i<=n ; i++)
silnia = silnia * i;
printf („Silnia to% d \ n”, silnia);
zwraca 0;
Jakie są podobieństwa między rekurencją a iteracją?
- Obie są technikami rozwiązania problemu.
- Zadanie można rozwiązać w trybie rekurencji lub iteracji.
Jaka jest różnica między rekurencją a iteracją?
Rekurencja a iteracja | |
| Rekurencja to metoda wywoływania funkcji w ramach tej samej funkcji. | Iteracja to blok instrukcji, który powtarza się, dopóki dany warunek nie zostanie spełniony. |
| Złożoność przestrzeni kosmicznej | |
| Złożoność przestrzenna programów rekurencyjnych jest większa niż iteracje. | Złożoność przestrzeni jest mniejsza w iteracjach. |
| Prędkość | |
| Wykonywanie rekurencji jest powolne. | Zwykle iteracja jest szybsza niż rekurencja. |
| Stan | |
| Jeśli nie ma warunku zakończenia, może wystąpić nieskończona rekurencja. | Jeśli warunek nigdy nie stanie się fałszywy, będzie to nieskończona iteracja. |
| Stos | |
| W rekurencji stos jest używany do przechowywania zmiennych lokalnych po wywołaniu funkcji. | W iteracji stos nie jest używany. |
| Czytelność kodu | |
| Program rekurencyjny jest bardziej czytelny. | Program iteracyjny jest trudniejszy do odczytania niż program rekurencyjny. |
Podsumowanie - rekurencja vs iteracja
W tym artykule omówiono różnicę między rekurencją a iteracją. Oba mogą służyć do rozwiązywania problemów programistycznych. Różnica między rekurencją a iteracją polega na tym, że rekurencja jest mechanizmem wywoływania funkcji w ramach tej samej funkcji i iteracji w celu wielokrotnego wykonywania zestawu instrukcji, dopóki dany warunek nie zostanie spełniony. Jeśli problem można rozwiązać w formie rekurencyjnej, można go również rozwiązać za pomocą iteracji.
Pobierz wersję PDF Rekurencji a iteracji
Możesz pobrać wersję PDF tego artykułu i używać go do celów offline zgodnie z cytatem. Pobierz wersję PDF tutaj Różnica między rekurencją a iteracją
Odniesienie:
1.Punkt, samouczki. „Struktury danych i podstawy rekurencji algorytmów”., Tutorials Point, 15 sierpnia 2017. Dostępne tutaj
2.nareshtechnologies. „Rekurencja w funkcjach C | Samouczek języka C ”YouTube, YouTube, 12 września 2016 r. Dostępny tutaj
3. yusuf shakeel. „Algorytm rekurencji | Factorial - przewodnik krok po kroku ”YouTube, YouTube, 14 października 2013. Dostępny tutaj
Zdjęcie dzięki uprzejmości:
1.'CCP-Recursion-Factorial-Code'By Pluke - Praca własna, (domena publiczna) przez Commons Wikimedia
2. „For-loop-diagram” Przez Nie podano autora do odczytu maszynowego - Założono pracę własną. (CC BY-SA 2.5) przez Commons Wikimedia
