Ključna razlika – rekurzija proti iteraciji
Rekurzijo in iteracijo je mogoče uporabiti za reševanje težav s programiranjem. Pristop k reševanju problema z uporabo rekurzije ali iteracije je odvisen od načina reševanja problema. Ključna razlika med rekurzijo in iteracijo je, da je rekurzija mehanizem za klicanje funkcije znotraj iste funkcije, medtem ko je iteracija ponavljajoče izvajanje niza navodil, dokler dani pogoj ni resničen. Rekurzija in iteracija sta glavni tehniki za razvoj algoritmov in gradnjo programskih aplikacij.
Kaj je rekurzija?
Ko funkcija pokliče samo sebe znotraj funkcije, je to znano kot rekurzija. Obstajata dve vrsti rekurzije. Sta končna rekurzija in neskončna rekurzija. Končna rekurzija ima končni pogoj. Neskončna rekurzija nima končnega pogoja.
Rekurzijo lahko razložimo s programom za izračun faktorialov.
n!=n(n-1)!, če je n>0
n!=1, če je n=0;
Glejte spodnjo kodo za izračun faktoriala 3(3!=321).
intmain () {
int vrednost=faktorial (3);
printf(“Faktorial je %d\n”, vrednost);
vrni 0;
}
intfactorial (intn) {
if(n==0) {
vrni 1;
}
drugo {
vrni n faktoriel(n-1);
}
}
Ko kličete faktorial (3), bo ta funkcija poklicala faktorial (2). Ko kliče faktorial (2), bo ta funkcija poklicala faktorial (1). Potem bo faktorial (1) poklical faktorial (0). factorial (0) bo vrnil 1. V zgornjem programu je pogoj n==0 v bloku »if« osnovni pogoj. V skladu z Likewise se funkcija faktorial kliče znova in znova.
Rekurzivne funkcije so povezane s skladom. V C ima lahko glavni program veliko funkcij. Torej je main () klicna funkcija, funkcija, ki jo pokliče glavni program, pa je klicana funkcija. Ko je funkcija poklicana, je nadzor dodeljen klicani funkciji. Po končani izvedbi funkcije se krmiljenje vrne na glavno. Nato se nadaljuje glavni program. Torej ustvari aktivacijski zapis ali okvir sklada za nadaljevanje izvajanja.
Slika 01: Rekurzija
V zgornjem programu, ko prikliče faktorial (3) iz main, ustvari aktivacijski zapis v klicnem skladu. Nato se na vrhu sklada ustvari faktorski (2) okvir sklada in tako naprej. Aktivacijski zapis hrani informacije o lokalnih spremenljivkah itd. Vsakič, ko je funkcija poklicana, se na vrhu sklada ustvari nov niz lokalnih spremenljivk. Ti okvirji skladov lahko upočasnijo hitrost. Podobno pri rekurziji funkcija pokliče samo sebe. Časovna zapletenost rekurzivne funkcije je določena s številom klicev funkcije. Časovna zahtevnost za en klic funkcije je O(1). Za n število rekurzivnih klicev je časovna kompleksnost O(n).
Kaj je iteracija?
Ponavljanje je blok navodil, ki se znova in znova ponavlja, dokler dani pogoj ni resničen. Iteracijo je mogoče doseči z uporabo "zanke for", "zanke do-while" ali "zanke medtem ko". Sintaksa »zanke« je naslednja.
za (inicializacija; stanje; spreminjanje) {
// izjave;
}
Slika 02: “diagram toka zanke”
Najprej se izvede korak inicializacije. Ta korak je deklaracija in inicializacija krmilnih spremenljivk zanke. Če je pogoj resničen, se stavki v zavitih oklepajih izvedejo. Ti stavki se izvajajo, dokler pogoj ni resničen. Če je pogoj napačen, se krmiljenje premakne na naslednji stavek za zanko for. Po izvedbi stavkov znotraj zanke gre kontrolnik v razdelek za spreminjanje. To je za posodobitev spremenljivke za nadzor zanke. Nato se stanje ponovno preveri. Če je pogoj resničen, se bodo izvedli stavki v zavitih oklepajih. Na ta način se ponavlja "zanka for".
V “while loop” se stavki znotraj zanke izvajajo, dokler pogoj ni resničen.
medtem ko (pogoj){
//izjave
}
V zanki “do-while” se pogoj preveri na koncu zanke. Torej se zanka izvede vsaj enkrat.
do{
//izjave
} medtem ko(pogoj)
Program za iskanje faktoriala 3 (3!) z uporabo iteracije (»zanke for«) je naslednji.
int main(){
intn=3, faktorial=1;
inti;
za(i=1; i<=n; i++){
faktorial=faktoriali;
}
printf(“Faktorial je %d\n”, faktorial);
vrni 0;
}
Kakšne so podobnosti med rekurzijo in iteracijo?
- Obe sta tehniki za rešitev težave.
- Nalogo je mogoče rešiti v rekurziji ali iteraciji.
Kakšna je razlika med rekurzijo in iteracijo?
Rekurzija proti iteraciji |
|
| Rekurzija je metoda klica funkcije znotraj iste funkcije. | Iteracija je blok navodil, ki se ponavlja, dokler dani pogoj ni resničen. |
| Vesoljska kompleksnost | |
| Prostorska kompleksnost rekurzivnih programov je višja od iteracij. | Zapletenost prostora je manjša pri iteracijah. |
| Hitrost | |
| Izvajanje rekurzije je počasno. | Običajno je iteracija hitrejša od rekurzije. |
| Stanje | |
| Če ni zaključnega pogoja, lahko pride do neskončne rekurzije. | Če pogoj nikoli ne postane napačen, bo to neskončna iteracija. |
| Sklad | |
| Pri rekurziji se sklad uporablja za shranjevanje lokalnih spremenljivk ob klicu funkcije. | V iteraciji se sklad ne uporablja. |
| Birljivost kode | |
| Rekurzivni program je bolj berljiv. | Iterativni program je težje brati kot rekurziven program. |
Povzetek – rekurzija proti iteraciji
Ta članek je obravnaval razliko med rekurzijo in iteracijo. Oboje je mogoče uporabiti za reševanje težav s programiranjem. Razlika med rekurzijo in iteracijo je v tem, da je rekurzija mehanizem za klicanje funkcije znotraj iste funkcije in iteracija za ponavljajoče se izvajanje niza navodil, dokler dani pogoj ni resničen. Če je problem mogoče rešiti v rekurzivni obliki, ga je mogoče rešiti tudi z uporabo iteracij.
Prenesite PDF različico rekurzije proti iteraciji
Lahko prenesete PDF različico tega članka in jo uporabite za namene brez povezave v skladu z opombo o citiranju. Prenesite PDF različico tukaj Razlika med rekurzijo in iteracijo
