Ključna razlika – rekurzija vs iteracija
Rekurzija i iteracija se mogu koristiti za rješavanje programskih problema. Pristup rješavanju problema korištenjem rekurzije ili iteracije ovisi o načinu rješavanja problema. Ključna razlika između rekurzije i iteracije je u tome što je rekurzija mehanizam za pozivanje funkcije unutar iste funkcije, dok je iteracija izvršavanje skupa instrukcija uzastopno sve dok zadati uvjet nije istinit. Rekurzija i iteracija su glavne tehnike za razvoj algoritama i izgradnju softverskih aplikacija.
Šta je rekurzija?
Kada funkcija sama sebe pozove unutar funkcije, to je poznato kao rekurzija. Postoje dvije vrste rekurzije. Oni su konačna rekurzija i beskonačna rekurzija. Konačna rekurzija ima završni uslov. Beskonačna rekurzija nema završni uslov.
Rekurzija se može objasniti korišćenjem programa za izračunavanje faktorijala.
n!=n(n-1)!, ako je n>0
n!=1, ako je n=0;
Pogledajte kod ispod da izračunate faktorijel od 3(3!=321).
intmain () {
int value=faktorski (3);
printf(“Faktorijal je %d\n”, vrijednost);
povrat 0;
}
intfactorial (intn) {
if(n==0) {
povratak 1;
}
ostalo {
return n factorial(n-1);
}
}
Kada pozove faktorijel (3), ta funkcija će pozvati faktorijel (2). Prilikom pozivanja faktorijala (2), ta funkcija će pozvati faktorijel (1). Tada će faktorijel (1) pozvati faktorijel (0). faktorijel (0) će vratiti 1. U gornjem programu, n==0 uslov u “if bloku” je osnovni uslov. U skladu sa Slično, faktorijalna funkcija se poziva iznova i iznova.
Rekurzivne funkcije su povezane sa stekom. U C-u, glavni program može imati mnogo funkcija. Dakle, main () je funkcija koja poziva, a funkcija koju poziva glavni program je pozvana funkcija. Kada se funkcija pozove, kontrola se daje pozvanoj funkciji. Nakon što je izvršenje funkcije završeno, kontrola se vraća na main. Zatim se nastavlja glavni program. Dakle, kreira aktivacijski zapis ili okvir steka za nastavak izvršavanja.
Slika 01: Rekurzija
U gornjem programu, kada poziva faktorial (3) iz glavnog, kreira aktivacioni zapis u steku poziva. Zatim se faktorski (2) okvir steka kreira na vrhu steka i tako dalje. Aktivacijski zapis čuva informacije o lokalnim varijablama itd. Svaki put kada se funkcija pozove, novi skup lokalnih varijabli se kreira na vrhu steka. Ovi okviri steka mogu usporiti brzinu. Slično u rekurziji, funkcija poziva samu sebe. Vremenska složenost za rekurzivnu funkciju utvrđuje se brojem puta kada se funkcija poziva. Vremenska složenost za jedan poziv funkcije je O(1). Za n broj rekurzivnih poziva, vremenska složenost je O(n).
Šta je iteracija?
Iteracija je blok instrukcija koji se ponavlja iznova i iznova dok se zadati uslov ne ispuni. Iteracija se može postići korištenjem “for petlje”, “do-while petlje” ili “while petlje”. Sintaksa “for petlje” je sljedeća.
za (inicijalizacija; stanje; modifikacija) {
// izjave;
}
Slika 02: “za dijagram toka petlje”
Korak inicijalizacije se prvo izvršava. Ovaj korak je deklarisanje i inicijalizacija kontrolnih varijabli petlje. Ako je uslov istinit, izvršavaju se naredbe unutar vitičastih zagrada. Te izjave se izvršavaju sve dok uvjet nije istinit. Ako je uslov netačan, kontrola ide na sljedeću naredbu nakon “for petlje”. Nakon izvršenja naredbi unutar petlje, kontrola ide u modificirani odjeljak. To je ažuriranje kontrolne varijable petlje. Zatim se stanje ponovo provjerava. Ako je uslov tačan, izvršit će se izrazi unutar vitičastih zagrada. Na ovaj način se ponavlja "for petlja".
U “while petlji”, naredbe unutar petlje se izvršavaju sve dok uvjet nije istinit.
dok (uslov){
//izjave
}
U “do-while” petlji, uslov se provjerava na kraju petlje. Dakle, petlja se izvršava najmanje jednom.
do{
//izjave
} dok(uslov)
Program za pronalaženje faktorijela od 3 (3!) koristeći iteraciju (“for petlju”) je sljedeći.
int main(){
intn=3, factorial=1;
inti;
for(i=1; i<=n; i++){
faktorski=faktorskii;
}
printf(“Faktorijal je %d\n”, faktorijelan);
povrat 0;
}
Koje su sličnosti između rekurzije i iteracije?
- Obje su tehnike za rješavanje problema.
- Zadatak se može riješiti bilo rekurzivno ili iteracijom.
Koja je razlika između rekurzije i iteracije?
Rekurzija vs Iteracija |
|
| Rekurzija je metoda pozivanja funkcije unutar iste funkcije. | Iteracija je blok instrukcija koji se ponavlja dok se zadati uslov ne ispuni. |
| Složenost prostora | |
| Prostorna složenost rekurzivnih programa veća je od iteracija. | Složenost prostora je niža u iteracijama. |
| Speed | |
| Izvršavanje rekurzije je sporo. | Normalno, iteracija je brža od rekurzije. |
| Uslov | |
| Ako ne postoji uslov prekida, može postojati beskonačna rekurzija. | Ako uslov nikada ne postane netačan, to će biti beskonačna iteracija. |
| Stog | |
| U rekurziji, stek se koristi za pohranjivanje lokalnih varijabli kada se funkcija pozove. | U iteraciji, stek se ne koristi. |
| Čitljivost koda | |
| Rekurzivni program je čitljiviji. | Iterativni program je teže čitati od rekurzivnog programa. |
Sažetak – Rekurzija vs Iteracija
Ovaj članak govori o razlici između rekurzije i iteracije. Oba se mogu koristiti za rješavanje problema programiranja. Razlika između rekurzije i iteracije je u tome što je rekurzija mehanizam za pozivanje funkcije unutar iste funkcije i iteracija kako bi se uzastopno izvršavao skup instrukcija sve dok zadati uvjet nije istinit. Ako se problem može riješiti u rekurzivnom obliku, može se riješiti i korištenjem iteracija.
Preuzmite PDF verziju rekurzije vs iteracije
Možete preuzeti PDF verziju ovog članka i koristiti ga za vanmrežne svrhe prema napomeni o citatu. Molimo preuzmite PDF verziju ovdje Razlika između rekurzije i iteracije
