Ključna razlika – rekurzija naspram iteracije
Rekurzija i iteracija mogu se koristiti za rješavanje programskih problema. Pristup rješavanju problema pomoću 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 ponavljanje niza instrukcija sve dok zadani uvjet nije istinit. Rekurzija i iteracija glavne su tehnike za razvoj algoritama i izradu softverskih aplikacija.
Što je rekurzija?
Kada funkcija poziva samu sebe unutar funkcije, to je poznato kao rekurzija. Postoje dvije vrste rekurzije. To su konačna rekurzija i beskonačna rekurzija. Konačna rekurzija ima uvjet završetka. Beskonačna rekurzija nema uvjet završetka.
Rekurzija se može objasniti pomoću programa za izračunavanje faktorijela.
n!=n(n-1)!, ako je n>0
n!=1, ako je n=0;
Pogledajte donji kod za izračunavanje faktorijela 3(3!=321).
intmain () {
int vrijednost=faktorijel (3);
printf(“Faktorijel je %d\n”, vrijednost);
return 0;
}
intfaktorij (intn) {
if(n==0) {
return 1;
}
drugo {
vrati n faktorijel(n-1);
}
}
Kada pozivate faktorijel (3), ta funkcija će pozvati faktorijel (2). Kada poziva faktorijel (2), ta funkcija će pozvati faktorijel (1). Tada će faktorijel (1) zvati faktorijel (0). faktorijel (0) će vratiti 1. U gornjem programu, n==0 uvjet u “if bloku” je osnovni uvjet. Prema Likewise, funkcija faktorijela se poziva uvijek iznova.
Rekurzivne funkcije povezane su sa stogom. U C-u, glavni program može imati mnoge funkcije. Dakle, main () je pozivajuća funkcija, a funkcija koju poziva glavni program je pozvana funkcija. Kada se funkcija pozove, kontrola se daje pozvanoj funkciji. Nakon završetka izvršavanja funkcije, upravljanje se vraća na glavno. Potom se nastavlja glavni program. Dakle, stvara aktivacijski zapis ili okvir hrpe za nastavak izvođenja.
Slika 01: Rekurzija
U gornjem programu, kada poziva faktorijel (3) iz glavnog, stvara aktivacijski zapis u pozivnom stogu. Zatim se faktorski (2) okvir stoga stvara na vrhu stoga i tako dalje. Aktivacijski zapis čuva informacije o lokalnim varijablama itd. Svaki put kad se funkcija pozove, novi skup lokalnih varijabli stvara se na vrhu stoga. Ovi okviri snopa mogu usporiti brzinu. Slično u rekurziji, funkcija poziva samu sebe. Vremenska složenost rekurzivne funkcije određena je brojem poziva funkcije. Vremenska složenost za jedan poziv funkcije je O(1). Za n broj rekurzivnih poziva, vremenska složenost je O(n).
Što je iteracija?
Iteracija je blok instrukcija koje se ponavljaju iznova i iznova sve dok zadani uvjet nije istinit. 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; izmjena) {
// izjave;
}
Slika 02: “dijagram toka za petlju”
Prvo se izvršava korak inicijalizacije. Ovaj korak je deklaracija i inicijalizacija kontrolnih varijabli petlje. Ako je uvjet istinit, izvršavaju se naredbe unutar vitičastih zagrada. Te se naredbe izvršavaju dok uvjet nije istinit. Ako je uvjet lažan, kontrola ide na sljedeću naredbu nakon "for petlje". Nakon izvršavanja naredbi unutar petlje, kontrola ide u modificirani odjeljak. To je ažuriranje varijable kontrole petlje. Zatim se stanje ponovno provjerava. Ako je uvjet istinit, iskazi unutar vitičastih zagrada će se izvršiti. Na ovaj način "for petlja" ponavlja.
U “while petlji”, izjave unutar petlje se izvršavaju dok uvjet nije istinit.
dok (uvjet){
//izjave
}
U “do-while” petlji, uvjet se provjerava na kraju petlje. Dakle, petlja se izvodi barem jednom.
do{
//izjave
} dok(uvjet)
Program za pronalaženje faktorijela od 3 (3!) pomoću iteracije (“for petlje”) je sljedeći.
int main(){
intn=3, faktorijel=1;
inti;
za(i=1; i<=n; i++){
faktorij=faktorijeli;
}
printf(“Faktorijel je %d\n”, faktorijel);
return 0;
}
Koje su sličnosti između rekurzije i iteracije?
- Obje su tehnike za rješavanje problema.
- Zadatak se može riješiti u rekurziji ili iteraciji.
Koja je razlika između rekurzije i iteracije?
Rekurzija vs iteracija |
|
| Rekurzija je metoda pozivanja funkcije unutar iste funkcije. | Iteracija je blok instrukcija koje se ponavljaju sve dok zadani uvjet nije istinit. |
| Svemirska složenost | |
| Prostorna složenost rekurzivnih programa veća je od iteracija. | Složenost prostora manja je u iteracijama. |
| Brzina | |
| Izvršenje rekurzije je sporo. | Normalno, iteracija je brža od rekurzije. |
| Stanje | |
| Ako ne postoji uvjet prekida, može postojati beskonačna rekurzija. | Ako uvjet nikad ne postane lažan, bit će to beskonačna iteracija. |
| Snop | |
| U rekurziji, stog se koristi za pohranu lokalnih varijabli kada se funkcija pozove. | U iteraciji, stog se ne koristi. |
| Čitljivost koda | |
| Rekurzivni program je čitljiviji. | Iterativni program je teži za čitanje nego rekurzivni program. |
Sažetak – rekurzija vs iteracija
Ovaj članak raspravlja o razlici između rekurzije i iteracije. Oba se mogu koristiti za rješavanje programskih problema. Razlika između rekurzije i iteracije je u tome što je rekurzija mehanizam za pozivanje funkcije unutar iste funkcije i iteracija za ponovno izvršavanje skupa instrukcija sve dok zadani uvjet nije istinit. Ako se problem može riješiti u rekurzivnom obliku, također se može riješiti pomoću iteracija.
Preuzmite PDF verziju rekurzije protiv iteracije
Možete preuzeti PDF verziju ovog članka i koristiti ga za izvanmrežne svrhe prema napomeni o citatu. Ovdje preuzmite PDF verziju. Razlika između rekurzije i iteracije
