Ključna razlika - rekurzija proti ponovitvi
Rekurzijo in iteracijo lahko uporabimo za reševanje programskih problemov. Pristop k reševanju problema z uporabo rekurzije ali ponovitve je odvisen od načina reševanja problema. Ključna razlika med rekurzijo in ponovitvijo je, da je rekurzija mehanizem za klicanje funkcije znotraj iste funkcije, medtem ko je ponovitev, da večkrat izvaja nabor navodil, dokler dani pogoj ne izpolni. Rekurzija in ponovitev sta glavni tehniki za razvoj algoritmov in gradnjo programskih aplikacij.
VSEBINA
1. Pregled in ključna razlika
2. Kaj je rekurzija
3. Kaj je iteracija
4. Podobnosti med rekurzijo in iteracijo
5. Vzporedna primerjava - Rekurzija vs iteracija v tabelarni obliki
6. Povzetek
Kaj je rekurzija?
Ko se funkcija znotraj funkcije pokliče, je znana kot Rekurzija. Obstajata dve vrsti rekurzije. So končna rekurzija in neskončna rekurzija. Končna rekurzija ima zaključni pogoj. Neskončna rekurzija nima končnega stanja.
Rekurzijo je mogoče razložiti s pomočjo programa za izračun faktorjev.
n! = n * (n-1) !, če je n> 0
n! = 1, če je n = 0;
Za izračun faktorja 3 (3! = 3 * 2 * 1) glejte spodnjo kodo.
intmain () {
int vrednost = faktorijel (3);
printf (»Faktor je% d / n«, vrednost);
vrnitev 0;
}
intfactorial (intn) {
če (n == 0) {
vrnitev 1;
}
sicer {
vrne n * faktorijel (n-1);
}
}
Ko prikliče faktorijel (3), bo ta funkcija poklicala faktorijel (2). Ko prikliče faktorijel (2), bo ta funkcija poklicala faktorijel (1). Potem bo faktorja (1) poklicala faktorja (0). factorial (0) vrne 1. V zgornjem programu je osnovni pogoj n == 0 v "if block". V skladu s tem se tudi faktorjska funkcija vedno znova prikliče.
Rekurzivne funkcije so povezane s skladom. V jeziku C ima lahko glavni program veliko funkcij. Torej, main () je klicna funkcija, funkcija, ki jo pokliče glavni program, pa je klicana funkcija. Ko je funkcija poklicana, je nadzor dodeljen klicani funkciji. Po končanem izvajanju funkcije se nadzor vrne na glavno. Nato se glavni program nadaljuje. Torej ustvari aktivacijski zapis ali okvir sklada za nadaljevanje izvajanja.
Slika 01: Rekurzija
V zgornjem programu med klicem faktorja (3) iz glavnega ustvari aktivacijski zapis v nizu klicev. Nato se na vrhu sklada ustvari faktorjalski (2) okvir sklada in tako naprej. Aktivacijski zapis hrani informacije o lokalnih spremenljivkah itd. Vsakič, ko pokličete funkcijo, se na vrhu sklada ustvari nov nabor lokalnih spremenljivk. Ti okviri skladov lahko upočasnijo pospešitev. Podobno v rekurziji se funkcija pokliče sama. Zapletenost časa za rekurzivno funkcijo najdemo s številom klicev funkcije. Zapletenost časa za en klic funkcije je O (1). Pri n številu rekurzivnih klicev je časovna zapletenost O (n).
Kaj je ponovitev?
Iteracija je sklop navodil, ki se vedno znova ponavlja, dokler dani pogoj ne izpolni. Iteracijo lahko dosežemo z uporabo »for loop«, »do-while loop« ali »while loop«. Sintaksa "for loop" je naslednja.
for (inicializacija; pogoj; spreminjanje) {
// izjave;
}
Slika 02: "za diagram poteka zanke"
Najprej se izvede korak inicializacije. Ta korak je razglasitev in inicializacija nadzornih spremenljivk zanke. Če je pogoj resničen, se izvršijo stavki znotraj zavitih oklepajev. Ti stavki se izvajajo, dokler pogoj ni izpolnjen. Če je pogoj napačen, nadzor preide na naslednji stavek za zanko »for«. Po izvedbi stavkov znotraj zanke nadzor preide na razdelek za spreminjanje. Posodobiti je treba spremenljivko za nadzor zanke. Nato se stanje še enkrat preveri. Če je pogoj resničen, se izvršijo stavki znotraj zavitih oklepajev. Na ta način se zanka »for« ponovi.
V zanki »while« se stavki znotraj zanke izvajajo, dokler pogoj ni izpolnjen.
medtem ko (stanje) {
// izjave
}
V zanki »do-while« se stanje preveri na koncu zanke. Torej, zanka se izvede vsaj enkrat.
naredi {
// izjave
} medtem ko (stanje)
Program za iskanje faktorja 3 (3!) Z uporabo iteracije (»for loop«) je naslednji.
int main () {
intn = 3, faktorijel = 1;
inti;
za (i = 1; i <= n; i ++) {
factorial = faktorijel * i;
}
printf (»Faktorije je% d / n«, faktorije);
vrnitev 0;
}
Kakšne so podobnosti med rekurzijo in ponovitvijo?
- Obe tehniki sta rešitvi problema.
- Nalogo je mogoče rešiti v rekurziji ali iteraciji.
Kakšna je razlika med rekurzijo in ponovitvijo?
Diff Article Sredina pred mizo
Rekurzija vs ponovitev |
|
| Rekurzija je metoda klica funkcije znotraj iste funkcije. | Iteracija je sklop navodil, ki se ponavlja, dokler dani pogoj ne izpolni. |
| Zapletenost prostora | |
| Prostorska zapletenost rekurzivnih programov je večja od ponovitev. | Zapletenost vesolja je v ponovitvah manjša. |
| Hitrost | |
| Izvajanje rekurzije je počasno. | Običajno je ponovitev hitrejša od rekurzije. |
| Stanje | |
| Če ni pogoja za prekinitev, lahko pride do neskončne ponovitve. | Če stanje nikoli ne postane napačno, bo to neskončna ponovitev. |
| Stack | |
| V rekurziji se sklad uporablja za shranjevanje lokalnih spremenljivk, ko je funkcija poklicana. | V iteraciji se sklad ne uporablja. |
| Koda berljivost | |
| Rekurzivni program je bolj berljiv. | Ponavljajoči program je težje brati kot rekurzivni program. |
Povzetek - Rekurzija vs iteracija
Ta članek je obravnaval razliko med rekurzijo in ponovitvijo. Oboje lahko uporabimo za reševanje programskih problemov. Razlika med rekurzijo in ponovitvijo je v tem, da je rekurzija mehanizem za klicanje funkcije znotraj iste funkcije in ponovitev, da večkrat izvede nabor navodil, dokler dani pogoj ne izpolni. Če je težavo mogoče rešiti v rekurzivni obliki, jo je mogoče rešiti tudi s ponovitvami.
Prenesite PDF različico Recursion vs Iteration
Lahko prenesete različico tega članka v obliki PDF in jo uporabite za uporabo brez povezave, kot je navedeno v opombi. Prosimo, prenesite PDF različico tukaj Razlika med rekurzijo in ponovitvijo
