Razlika između rekurzije i ponavljanja

• 2019

Rekurzija i iteracija oba puta izvršavaju skup instrukcija. Rekurzija je kada se izraz u funkciji poziva više puta. Iteracija je kada se petlja više puta izvršava sve dok stanje kontrolinga ne postane lažno. Primarna razlika između rekurzije i iteracije jest da je rekurzija proces, koji se uvijek primjenjuje na funkciju. Iteracija se primjenjuje na skup uputa koje želimo više puta izvršiti.

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

1. Rekurzija je kada metoda u programu opetovano poziva sebe, dok je iteracija kada se skup instrukcija u programu više puta izvršava.
2. 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.
3. Uvjetna naredba odlučuje o završetku vrijednosti rekurzije i kontrolne varijable odlučuje o prestanku izjave o iteraciji.
4. 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.
5. Beskonačna rekurzija može dovesti do pada sustava, dok beskonačna iteracija troši CPU cikluse.
6. Rekurzija se uvijek primjenjuje na metodu, dok se iteracija primjenjuje na skup instrukcija.
7. Varijable stvorene tijekom rekurzije pohranjuju se na stog dok iteracija ne zahtijeva stog.
8. Rekurzija uzrokuje opterećenje ponovljenog funkcijskog poziva, dok iteracija nema funkciju pozivanja glave.
9. Zbog funkcije poziva nad glavom izvršenje rekurzije je sporije dok je izvršenje iteracije brže.
10. 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.