Kluczowa różnica - rekurencja a iteracja
Rekursji i iteracji można używać do rozwiązywania problemów programistycznych. Podejście do rozwiązania problemu za pomocą rekurencji lub iteracji zależy od sposobu rozwiązania problemu. Kluczowa różnica między rekurencją a iteracją polega na tym, że rekurencja jest mechanizmem wywoływania funkcji w ramach tej samej funkcji, podczas gdy iteracja polega na wielokrotnym wykonywaniu zestawu instrukcji, aż dany warunek będzie spełniony. Rekursja i iteracja to główne techniki opracowywania algorytmów i tworzenia aplikacji.
ZAWARTOŚĆ
1. Przegląd i kluczowe różnice
2. Czym jest rekursja
3. Czym jest iteracja
4. Podobieństwa między rekurencją a iteracją
5. Porównanie obok siebie - rekurencja a iteracja w formie tabelarycznej
6. Podsumowanie
Co to jest rekursja?
Gdy funkcja wywołuje samą siebie w ramach funkcji, nazywa się to rekursją. Istnieją dwa typy rekursji. Są to rekursja skończona i rekurencja nieskończona. Rekurencja skończona ma warunek kończący. 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;
Aby obliczyć silnię z 3 (3! = 3 * 2 * 1), skorzystaj z poniższego kodu.
intmain () {
wartość int = silnia (3);
printf („Silnia to% d / n”, wartość);
return 0;
}
intfactorial (intn) {
if (n == 0) {
powrót 1;
}
else {
return n * silnia (n-1);
}
}
Podczas wywoływania factorial (3) ta funkcja wywoła factorial (2). Podczas wywoływania factorial (2) ta funkcja wywoła factorial (1). Wtedy silnia (1) wywoła silnię (0). silnia (0) zwróci 1. W powyższym programie warunek n == 0 w bloku „jeśli” jest warunkiem podstawowym. Zgodnie z Podobnie, funkcja silnia jest wywoływana wielokrotnie.
Funkcje rekurencyjne są powiązane ze stosem. W języku C program główny może mieć wiele funkcji. Zatem main () jest funkcją wywołującą, a funkcja wywoływana przez program główny to wywoływana funkcja. Gdy funkcja jest wywoływana, sterowanie jest przekazywane wywoływanej funkcji. Po zakończeniu wykonywania funkcji sterowanie wraca do main. Następnie główny program jest kontynuowany. Tworzy więc rekord aktywacji lub ramkę stosu, aby kontynuować wykonywanie.
Rysunek 01: Rekursja
W powyższym programie, podczas wywoływania factorial (3) z main, tworzy on rekord aktywacji na stosie wywołań. Następnie na szczycie stosu tworzona jest ramka stosu silnia (2) i tak dalej. Rekord aktywacji przechowuje informacje o zmiennych lokalnych itp. Za każdym razem, gdy funkcja jest wywoływana, na szczycie stosu tworzony jest nowy zestaw zmiennych lokalnych. Te ramki stosu mogą spowolnić przyspieszenie. Podobnie w przypadku rekurencji funkcja wywołuje samą siebie. Złożoność czasowa dla funkcji rekurencyjnej jest określana przez liczbę wywołań funkcji. Złożoność czasowa dla jednego wywołania funkcji wynosi O (1). Dla n liczby wywołań rekurencyjnych złożoność czasowa wynosi O (n).
Co to jest iteracja?
Iteracja to blok instrukcji, który powtarza się raz po raz, aż podany warunek zostanie spełniony. Iterację można osiągnąć za pomocą „pętli for”, „pętli do-while” lub „pętli while”. Składnia „pętli for” jest następująca.
for (inicjalizacja; warunek; modyfikacja) {
// sprawozdania;
}
Rysunek 02: „dla schematu przepływu pętli”
Krok inicjalizacji jest wykonywany jako pierwszy. Ten krok polega na zadeklarowaniu i zainicjowaniu zmiennych sterujących pętlą. Jeśli warunek jest prawdziwy, wykonywane są instrukcje w nawiasach klamrowych. Te instrukcje są wykonywane do momentu spełnienia warunku. Jeśli warunek jest fałszywy, sterowanie przechodzi do następnej instrukcji po „pętli for”. Po wykonaniu instrukcji wewnątrz pętli formant przechodzi do modyfikacji sekcji. Ma to na celu aktualizację zmiennej sterującej pętlą. Następnie warunek jest ponownie sprawdzany. Jeśli warunek jest spełniony, zostaną wykonane instrukcje wewnątrz nawiasów klamrowych. W ten sposób iteruje „pętla for”.
W „pętli while” instrukcje wewnątrz pętli są wykonywane do momentu spełnienia warunku.
while (condition) {
//sprawozdania
}
W pętli „do-while” warunek jest sprawdzany na końcu pętli. Tak więc pętla jest wykonywana co najmniej raz.
zrobić{
//sprawozdania
} while (warunek)
Program do znajdowania silni 3 (3!) Za pomocą iteracji („pętla for”) jest następujący.
int main () {
intn = 3, silnia = 1;
inti;
for (i = 1; i <= n; i ++) {
silnia = silnia * i;
}
printf ("Silnia to% d / n", silnia);
return 0;
}
Jakie są podobieństwa między rekurencją a iteracją?
- Obie są technikami rozwiązania problemu.
- Zadanie można rozwiązać w rekurencji lub iteracji.
Jaka jest różnica między rekurencją a iteracją?
Porównaj środek artykułu przed tabelą
Rekurencja a iteracja |
|
| Rekursja to metoda wywoływania funkcji w ramach tej samej funkcji. | Iteracja to blok instrukcji, który powtarza się do momentu spełnienia podanego warunku. |
| Złożoność przestrzeni | |
| Złożoność przestrzeni programów rekurencyjnych jest większa niż iteracji. | Złożoność przestrzeni jest mniejsza w iteracjach. |
| Prędkość | |
| Wykonywanie rekursji jest powolne. | Zwykle iteracja jest szybsza niż rekurencja. |
| Stan: schorzenie | |
| Jeśli nie ma warunku zakończenia, rekurencja może być nieskończona. | 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, gdy funkcja jest wywoływana. | 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 a iteracja
W tym artykule omówiono różnicę między rekurencją a iteracją. Oba mogą być używane do rozwiązywania problemów programistycznych. Różnica między rekurencją a iteracją polega na tym, że rekurencja jest mechanizmem do wywoływania funkcji w ramach tej samej funkcji i iteracji w celu wielokrotnego wykonywania zestawu instrukcji, dopóki dany warunek nie będzie prawdziwy. Jeśli problem można rozwiązać w formie rekurencyjnej, można go również rozwiązać za pomocą iteracji.
Pobierz wersję PDF programu Rekursja vs Iteracja
Możesz pobrać wersję PDF tego artykułu i używać jej w trybie offline, zgodnie z notą cytowania. Proszę pobrać wersję PDF tutaj Różnica między rekurencją a iteracją
