Kluczowa różnica – rekurencja vs iteracja
Rekurencja i iteracja mogą być używane 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 rekursja jest mechanizmem 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.
Co to jest rekurencja?
Kiedy funkcja wywołuje samą siebie w funkcji, nazywa się to rekurencją. Istnieją dwa rodzaje rekurencji. Są to skończona rekurencja i nieskończona rekurencja. Skończona rekurencja 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;
Odnieś się do poniższego kodu, aby obliczyć silnię 3(3!=321).
intmain () {
wartość int=silnia (3);
printf(„Silnik to %d\n”, wartość);
powrót 0;
}
intfactorial (intn) {
if(n==0) {
powrót 1;
}
inne {
powrót n silnia(n-1);
}
}
Podczas wywoływania silni (3) ta funkcja wywoła silnię (2). Wywołując silnię (2), ta funkcja wywoła silnię (1). Wtedy silnia (1) wywoła silnię (0). silnia (0) zwróci 1. W powyższym programie warunek n==0 w bloku „if” jest warunkiem podstawowym. Według Likewise funkcja silnia jest wywoływana raz po raz.
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, która jest wywoływana przez program główny, jest funkcją wywoływaną. Gdy funkcja jest wywoływana, kontrola jest przekazywana do wywołanej funkcji. Po zakończeniu wykonywania funkcji sterowanie powraca do stanu main. Następnie główny program trwa. Dlatego tworzy rekord aktywacji lub ramkę stosu, aby kontynuować wykonywanie.
Rysunek 01: Rekurencja
W powyższym programie, podczas wywoływania silni (3) z main, tworzy rekord aktywacji w stosie wywołań. Następnie tworzona jest ramka stosu silnia (2) na górze stosu 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 rekurencji funkcja wywołuje samą siebie. Złożoność czasowa funkcji rekurencyjnej jest określana jako liczba wywołań funkcji. Złożoność czasowa dla jednego wywołania funkcji wynosi O(1). Dla liczby n wywołań rekurencyjnych złożoność czasowa wynosi O(n).
Co to jest iteracja?
Iteracja to blok instrukcji, który powtarza się raz za razem, aż dany warunek zostanie spełniony. Iterację można osiągnąć za pomocą „pętli for”, „pętli do while” lub „pętli while”. Składnia „for loop” jest następująca.
for (inicjalizacja; warunek; modyfikacja) {
// oświadczenia;
}
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 prawdziwy, wykonywane są instrukcje w nawiasach klamrowych. Te instrukcje są wykonywane, dopóki warunek nie zostanie spełniony. Jeśli warunek jest fałszywy, formant przechodzi do następnej instrukcji po „pętli for”. Po wykonaniu instrukcji wewnątrz pętli kontrolka przechodzi do sekcji modyfikacji. Ma to na celu aktualizację zmiennej sterującej pętlą. Następnie warunek jest sprawdzany ponownie. Jeśli warunek jest spełniony, zostaną wykonane instrukcje w nawiasach klamrowych. W ten sposób iteruje „pętla for”.
W „pętli while”, instrukcje wewnątrz pętli są wykonywane, dopóki warunek nie zostanie spełniony.
gdy (warunek){
//wypowiedzi
}
W pętli „do-while” warunek jest sprawdzany na końcu pętli. Tak więc pętla wykonuje się co najmniej raz.
zrobić{
//wypowiedzi
} while(warunek)
Program do znalezienia silni 3 (3!) przy użyciu iteracji („pętla for”) wygląda następująco.
int main(){
intn=3, silnia=1;
inti;
for(i=1; i<=n; i++){
silnia=silniai;
}
printf(„Silnia to %d\n”, silnia);
powrót 0;
}
Jakie są podobieństwa między rekurencją a iteracją?
- Oba są technikami rozwiązywania problemów.
- Zadanie można rozwiązać w 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. |
| Kosmiczna złożoność | |
| Złożoność przestrzenna programów rekurencyjnych jest wyższa niż iteracje. | Złożoność przestrzeni jest mniejsza w iteracjach. |
| Prędkość | |
| Wykonywanie rekursji jest powolne. | Normalnie iteracja jest szybsza niż rekursja. |
| Warunek | |
| Jeśli nie ma warunku zakończenia, może istnieć nieskończona rekurencja. | Jeśli warunek nigdy nie stanie się fałszywy, będzie to nieskończona iteracja. |
| Stos | |
| W rekursji 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 rekursja jest mechanizmem wywoływania funkcji w ramach tej samej funkcji i iteracji w celu wielokrotnego wykonywania zestawu instrukcji, aż dany warunek jest 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ć jej do celów offline zgodnie z notatką cytowania. Proszę pobrać wersję PDF tutaj Różnica między rekurencją a iteracją
