Primerjalna tabela
| Osnova za primerjavo | Rekurzija | Iteracija |
|---|---|---|
| Osnovno | Stavek v telesu funkcije kliče samo funkcijo. | Omogoča večkratnemu izvrševanju niza navodil. |
| Oblika | V rekurzivni funkciji je podan le zaključni pogoj (osnovni primer). | Iteracija vključuje inicializacijo, stanje, izvedbo stavka znotraj zanke in posodobitev (povečave in zmanjšanja) kontrolne spremenljivke. |
| Prekinitev | Pogojni stavek je vključen v telo funkcije, da se funkcija vrne, ne da bi se izvedel rekurzijski klic. | Stavek ponovitve se večkrat izvaja, dokler ni dosežen določen pogoj. |
| Stanje | Če funkcija ne ustreza določenemu pogoju, ki se imenuje (osnovni primer), to vodi do neskončne rekurzije. | Če kontrolni pogoj v iteracijski izjavi nikoli ne postane napačen, to vodi do neskončne ponovitve. |
| Neskončno ponavljanje | Neskončna rekurzija lahko zruši sistem. | Infinite loop večkrat uporablja cikle CPU. |
| Uporabljeno | Rekurzija se vedno uporablja za funkcije. | Ponavljanje se uporablja za ponovitvene izjave ali "zanke". |
| Stack | Sklad se uporablja za shranjevanje niza novih lokalnih spremenljivk in parametrov vsakič, ko je funkcija klicana. | Ne uporablja sklada. |
| Zgoraj | Rekurzija ima večkratne funkcijske klice. | Brez večkratnega klica funkcije. |
| Hitrost | Počasi v izvedbi. | Hitro v izvedbi. |
| Velikost kode | Rekurzija zmanjša velikost kode. | Ponavljanje povzroči, da je koda daljša. |
Opredelitev rekurzije
C ++ omogoča funkciji, da se kliče v svojo kodo. To pomeni, da ima definicija funkcije funkcijski klic. Včasih se imenuje tudi » krožna definicija «. Niz lokalnih spremenljivk in parametrov, ki jih uporablja funkcija, so na novo ustvarjeni vsakič, ko se funkcija pokliče in so shranjeni na vrhu sklada. Vsakič, ko se funkcija pokliče sama, ne ustvari nove kopije te funkcije. Rekurzivna funkcija bistveno ne zmanjša velikosti kode in celo ne izboljša izkoriščenosti pomnilnika, vendar v primerjavi z iteracijo.
Če želite prekiniti rekurzijo, morate v definicijo funkcije vključiti ukaz select, ki bo funkciji prisilil, da se vrne, ne da bi rekurzivno klicalo k sebi. Odsotnost izbirnega stavka v definiciji rekurzivne funkcije pusti funkcijo v neskončni rekurziji.
Razumimo rekurzijo s funkcijo, ki bo vrnila faktorijalo števila.
int factorial (int num) {int answer; if (num == 1) {return 1; } else {answer = faktorial (num-1) * num; // vrnitev rekurzivnega klica} (odgovor); } V zgornji kodi je stavek v drugem delu prikazan rekurzija, saj stavek kliče funkcijo factorial (), v kateri se nahaja.
Opredelitev ponovitve
Ponavljanje je postopek večkratnega izvajanja niza navodil, dokler pogoj v izjavi ne postane napačen. Stavek ponovitve vključuje inicializacijo, primerjavo, izvajanje stavkov v stavku za ponovitev in končno posodabljanje kontrolne spremenljivke. Po posodobitvi kontrolne spremenljivke se ponovno primerja in proces se ponovi, dokler se pogoj v izjavi ne ponudi napačen. Ponovitvene izjave so zanke "za", zanke "medtem", zanke "do-while".
Izjava o ponovitvi ne uporablja sklada za shranjevanje spremenljivk. Izvedba ponovitvene izjave je torej hitrejša kot rekurzivna funkcija. Tudi funkcija iteracije nima več režijskih funkcij, ki zahtevajo večkratno funkcijsko klicanje. Ponovitev se zaključi, ko kontrolni pogoj postane napačen. Odsotnost kontrolnih pogojev v stavku ponovitve lahko povzroči neskončno zanko ali pa povzroči napako pri prevajanju.
Razumimo iteracijo v zvezi z zgornjim primerom.
int factorial (int num) {int answer = 1; // potrebuje inicializacijo, ker lahko pred inicializacijo vsebuje vrednost smeti (int t = 1; t> num; t ++) // iteracija {answer = answer * (t); vrnitev (odgovor); }} V zgornji kodi funkcija vrne faktorijo števila z uporabo stavka za ponovitev.
Ključne razlike med rekurziji in ponovitvijo
- Rekurzija je takrat, ko se metoda v programu večkrat javi, medtem ko je ponovitev, ko se niz navodil v programu večkrat izvaja.
- Rekurzivna metoda vsebuje nabor navodil, samo klicno izjavo in pogoj za zaključek, medtem ko iteracijske izjave vsebujejo inicializacijo, inkrement, pogoj, niz navodil znotraj zanke in kontrolno spremenljivko.
- Pogojni stavek odloči, da se zaključek vrednosti rekurzije in kontrolne spremenljivke odloči za zaključek ponovitvene izjave.
- Če metoda ne vodi do zaključnega pogoja, vstopi v neskončno rekurzijo. Po drugi strani, če kontrolna spremenljivka nikoli ne privede do zaključne vrednosti, se izjava ponovitve ponavlja neomejeno.
- Neskončna rekurzija lahko povzroči zrušitev sistema, medtem ko neskončna iteracija porabi cikle procesorja.
- Rekurzija se vedno uporablja za metodo, medtem ko se iteracija uporablja za nabor navodil.
- Spremenljivke, ustvarjene med rekurzijo, so shranjene v skladu, medtem ko iteracija ne zahteva sklada.
- Rekurzija povzroči obremenitev ponavljajočega se klicanja funkcij, medtem ko iteracija nima funkcije, ki kliče obremenitve.
- Zaradi funkcij, ki zahtevajo izvajanje režija rekurzija je počasnejša, medtem ko je izvajanje iteracije hitrejše.
- Rekurzija zmanjša velikost kode, medtem ko iteracije ustvarijo kodo dlje.
Sklep:
Rekurzivna funkcija je preprosta za pisanje, vendar v primerjavi z iteracijo ne delujejo dobro, medtem ko je iteracija težko napisati, vendar je njihova uspešnost dobra v primerjavi z rekurzijo.
