Tablica usporedbe
| Osnova za usporedbu | rekurzije | ponavljanje |
|---|---|---|
| Osnovni, temeljni | Izjava u tijelu funkcije poziva samu funkciju. | Omogućuje ponavljanje izvršavanja skupa uputa. |
| Format | U rekurzivnoj funkciji se navodi samo uvjet završetka (osnovni slučaj). | Iteracija uključuje inicijalizaciju, stanje, izvršenje izraza unutar petlje i ažuriranje (povećanja i smanjenja) kontrolne varijable. |
| završetak | U tijelo funkcije uključena je uvjetna naredba koja prisiljava funkciju na povratak bez izvršenja poziva rekurzije. | Izjava o ponavljanju se ponavljano izvršava sve dok se ne postigne određeni uvjet. |
| Stanje | Ako funkcija ne konvergira u neki uvjet koji se zove (osnovni slučaj), to dovodi do beskonačne rekurzije. | Ako kontrolni uvjet u izjavi iteracije nikada ne postane lažan, to dovodi do beskonačne iteracije. |
| Beskonačno ponavljanje | Beskonačna rekurzija može srušiti sustav. | Beskonačna petlja više puta koristi cikluse procesora. |
| primijenjen | Rekurzija se uvijek primjenjuje na funkcije. | Ponavljanje se primjenjuje na izjave iteracije ili "petlje". |
| Stog | Stog se koristi za pohranjivanje skupa novih lokalnih varijabli i parametara svaki put kada se funkcija pozove. | Ne koristi stog. |
| gore | Rekurzija posjeduje opterećenje ponovljenih poziva funkcija. | Nema opterećenja ponovljenog poziva funkcije. |
| Ubrzati | Sporo u izvršenju. | Brzo u izvršenju. |
| Veličina koda | Rekurzija smanjuje veličinu koda. | Ponavljanje čini kod duži. |
Definicija rekurzije
C ++ omogućuje funkciji da se nazove unutar svog koda. To znači da definicija funkcije posjeduje funkcijski poziv na sebe. Ponekad se naziva i „ kružna definicija “. Skup lokalnih varijabli i parametara koje koristi funkcija su novostvoreni svaki put kada se funkcija pozove i pohranjuju se na vrhu stog. No, svaki put kada funkcija pozove sebe, ona ne stvara novu kopiju te funkcije. Rekurzivna funkcija ne umanjuje značajno veličinu koda i ne poboljšava čak ni iskorištenje memorije, ali čini nešto u usporedbi s iteracijom.
Da biste prekinuli rekurziju, morate uključiti naredbu select u definiciju funkcije kako biste prisilili funkciju da se vrati bez davanja rekurzivnog poziva sebi. Odsustvo naredbe za odabir u definiciji rekurzivne funkcije pustiti će funkciju u beskonačnu rekurziju jednom.
Razmotrimo rekurziju s funkcijom koja će vratiti faktorijale broja.
int factorial (int num) {int answer; if (num == 1) {return 1; } else {answer = faktorski (num-1) * num; // povratni poziv (recursive)} (odgovor); } U gornjem kodu, izraz in else dio pokazuje rekurziju, jer izraz poziva funkciju factorial () u kojoj se nalazi.
Definicija ponavljanja
Ponavljanje je proces izvršavanja skupa instrukcija više puta dok se uvjet u izjavi o ponudi ne postane lažnim. Izjava o iteraciji uključuje inicijalizaciju, usporedbu, izvršavanje naredbi unutar izjave o iteraciji i konačno ažuriranje kontrolne varijable. Nakon što se kontrolna varijabla ažurira, ona se ponovno uspoređuje, a proces se ponavlja dok se ispostavi da je uvjet u ponavljanju izjave pogrešan. Izjave o iteraciji su petlje "za", petlja "dok", petlja "do-while".
Izjava iteracije ne koristi stog za spremanje varijabli. Stoga je izvršenje izjave o iteraciji brže u usporedbi s rekurzivnom funkcijom. Čak i funkcija iteracije nema opterećenje ponovljenog funkcijskog pozivanja koje također čini njegovo izvršavanje bržim od rekurzivne funkcije. Iteracija se završava kada kontrolni uvjet postane lažan. Odsustvo kontrolnih uvjeta u izrazu iteracije može rezultirati beskonačnom petljom ili može uzrokovati pogrešku kompilacije.
Razumimo iteraciju u odnosu na gornji primjer.
int factorial (int num) {int answer = 1; // treba inicijalizaciju jer može sadržavati vrijednost smeća prije inicijalizacije za (int t = 1; t> num; t ++) // iteracija {answer = answer * (t); povratak (odgovor); }} U gore navedenom kodu funkcija vraća faktorijale broja pomoću izraza iteration.
Ključne razlike između rekurzije i ponavljanja
- Rekurzija je kada metoda u programu opetovano poziva sebe, dok je iteracija kada se skup instrukcija u programu više puta izvršava.
- Rekurzivna metoda sadrži skup naredbi, pozivanje izjave i uvjet raskida, dok izjave iteracije sadrže inicijalizaciju, inkrement, stanje, skup instrukcija unutar petlje i kontrolnu varijablu.
- Uvjetna naredba odlučuje o završetku vrijednosti rekurzije i kontrolne varijable odlučuje o prestanku izjave o iteraciji.
- Ako metoda ne dovodi do uvjeta prekida, on ulazi u beskonačnu rekurziju. S druge strane, ako kontrolna varijabla nikad ne dovede do vrijednosti završetka, izraz iteracije se ponavlja beskonačno.
- Beskonačna rekurzija može dovesti do pada sustava, dok beskonačna iteracija troši CPU cikluse.
- Rekurzija se uvijek primjenjuje na metodu, dok se iteracija primjenjuje na skup instrukcija.
- Varijable stvorene tijekom rekurzije pohranjuju se na stog dok iteracija ne zahtijeva stog.
- Rekurzija uzrokuje opterećenje ponovljenog funkcijskog poziva, dok iteracija nema funkciju pozivanja glave.
- Zbog funkcije poziva nad glavom izvršenje rekurzije je sporije dok je izvršenje iteracije brže.
- Rekurzija smanjuje veličinu koda, dok iteracije čine dulji kod.
Zaključak:
Rekurzivna funkcija se lako piše, ali ne uspijeva dobro u usporedbi s iteracijom, dok je iteracija teško pisati, ali je njihova izvedba dobra u usporedbi s rekurzijom.
