Skirtumas tarp rekursijos ir iteracijos

• 2019

Rekursija ir iteracija pakartotinai vykdo nurodymų rinkinį. Rekursija yra tuomet, kai funkcijos funkcija pakartotinai vadina save. Iteracija yra tada, kai kilpa pakartotinai vykdoma, kol kontrolinė sąlyga tampa klaidinga. Pagrindinis skirtumas tarp rekursijos ir iteracijos yra tai, kad rekursas yra procesas, visada taikomas funkcijai. Iteracija taikoma instrukcijų rinkiniui, kurį norime gauti pakartotinai.

Palyginimo diagrama

Palyginimo pagrindas	Rekursija	Iteracija
Pagrindinis	Pareiškimas funkcijų kode nurodo pačią funkciją.	Leidžia pakartotinai atlikti nurodymų rinkinį.
Formatas	Rekursijos funkcijoje nurodoma tik nutraukimo sąlyga (pagrindinė byla).	Iteracija apima inicijavimą, būseną, pareiškimo vykdymą cikle ir kontrolės kintamojo atnaujinimą (didinimą ir mažinimą).
Nutraukimas	Sąlyginis teiginys yra įtrauktas į funkcijos kūną, norint priversti funkciją grįžti be vykdomo skambučio.	Iteracijos pareiškimas pakartotinai vykdomas, kol pasiekiama tam tikra sąlyga.
Būklė	Jei funkcija nesutampa su tam tikra sąlyga, kurią vadinasi (bazinis atvejis), tai sukelia begalinį rekursiją.	Jei valdymo sąlyga iteracijos pareiškime niekada netampa klaidinga, tai veda prie begalinio iteracijos.
Begalinis kartojimas	Begalinis rekursas gali sugriauti sistemą.	Begalinė kilpa pakartotinai naudoja procesoriaus ciklus.
Taikoma	Rekursija visada taikoma funkcijoms.	Iteracija taikoma iteracijos pareiškimams arba „kilpoms“.
Stack	Sraigtas naudojamas naujų vietinių kintamųjų ir parametrų rinkiniams saugoti kiekvieną kartą, kai skambinama.	Nenaudoja kamino.
Pridėtinės išlaidos	Rekursija turi pakartotinių funkcijų skambučių pridėtinę vertę.	Nėra pakartotinių funkcijų skambučio.
Greitis	Lėtas vykdymas.	Greitas vykdymas.
Kodo dydis	Rekursija sumažina kodo dydį.	Iteracija daro kodą ilgiau.

Rekursijos apibrėžimas

„C ++“ leidžia funkciją vadinti savo kodu. Tai reiškia, kad funkcijos apibrėžimas turi funkciją, vadinamą savimi. Kartais tai vadinama „ apykaitine apibrėžtimi “. Vietos kintamųjų ir parametrų, kuriuos naudoja funkcija, rinkinys naujai sukuriamas kiekvieną kartą, kai funkcija vadina save ir yra saugomos kamino viršuje. Tačiau kiekvieną kartą, kai pati funkcija vadinama, ji nesukuria naujos šios funkcijos kopijos. Rekursinė funkcija reikšmingai nesumažina kodo dydžio ir netgi nepagerina atminties panaudojimo, tačiau kai kuri, lyginant su iteracija.

Norint nutraukti rekursiją, funkcijos apibrėžtyje turite įtraukti pasirinkimo pareiškimą, norint priversti funkciją grįžti, nesuteikiant rekursinio skambučio sau. Pasirinkimo pareiškimo nebuvimas rekursyviosios funkcijos apibrėžime leis funkciją begalinėje rekursijoje, kai jis bus vadinamas.

Suprasime rekursiją su funkcija, kuri grąžins numerio faktorių.

 int faktorius (int num) {int answer; jei (num == 1) {return 1; } other {answer = faktorius (num-1) * num; // rekursinis skambinimas} grįžimas (atsakymas); } 

Pirmiau pateiktame kode, kitoje dalyje, parodoma rekursija, nes pareiškimas vadina funkcijų faktoriumi (), kuriame jis yra.

Iteracijos apibrėžimas

Iteracija yra instrukcijų rinkinio pakartotinis vykdymo procesas, kol iteracijos pareiškime esanti būsena tampa klaidinga. Iteracijos pareiškimas apima inicijavimą, palyginimą, ataskaitų vykdymą iteracijos ataskaitoje ir, galiausiai, kontrolės kintamojo atnaujinimą. Atnaujinus kontrolinį kintamąjį, jis vėl palyginamas, ir procesas kartojasi, kol iteracijos pareiškime esanti būsena yra klaidinga. Iteraciniai teiginiai yra „už“ kilpą, „o“ kilpa, „ciklas“.

Kintamųjų išsaugojimui iteracijos pareiškime nenaudojama kamino. Todėl iteracijos pareiškimo vykdymas yra greitesnis, palyginti su rekursine funkcija. Net iteracijos funkcija neturi pakartotinių funkcijų skambučio, kuris taip pat leidžia atlikti jo vykdymą greičiau nei rekursinė funkcija. Iteracija nutraukiama, kai valdymo sąlyga tampa netikra. Kontrolės būsenos nebuvimas iteracijos ataskaitoje gali sukelti begalinę kilpą arba gali sukelti kompiliavimo klaidą.

Suprasime iteraciją, susijusią su aukščiau pateiktu pavyzdžiu.

 int faktorius (int num) {int answer = 1; // reikia inicijuoti, nes jis gali turėti šiukšlių reikšmę prieš jo inicijavimą (int t = 1; t> num; t ++) // iteracija {answer = atsakymas * (t); grąžinimas (atsakymas); }} 

Anksčiau pateiktame kode funkcija grąžina skaičiaus faktorių, naudodama iteracijos pareiškimą.

Pagrindiniai skirtumai tarp rekursijos ir iteracijos

1. Rekursija yra tada, kai programoje esantis metodas pakartotinai kviečia save, o iteracija yra tada, kai programoje pateiktų instrukcijų rinkinys yra pakartotinai vykdomas.
2. Rekursinis metodas apima instrukcijų rinkinį, pareiškimą, kuriame skambinama, ir užbaigimo sąlygą, o iteracijos pareiškimai apima inicijavimą, prieaugį, būklę, nurodymų rinkinį kilpoje ir valdymo kintamąjį.
3. Sąlyginis teiginys nusprendžia, kad rekursijos ir kontrolinio kintamojo vertė nutraukiama iteracijos pareiškimo nutraukimu.
4. Jei metodas nesukelia nutraukimo sąlygų, jis patenka į begalinį rekursiją. Kita vertus, jei valdymo kintamasis niekada nesibaigia užbaigimo verte, iteracijos pareiškimas iteruoja be galo.
5. Begalinis rekursas gali sukelti sistemos gedimą, o begalinis iteravimas sunaudoja procesoriaus ciklus.
6. Rekursija visada taikoma metodui, o iteracija taikoma instrukcijų rinkiniui.
7. Rekursijos metu sukurti kintamieji yra saugomi kaminai, o iteracijai nereikia kamino.
8. Rekursija sukelia pakartotinės funkcijos skambinimą, o iteracija neturi funkcijos, vadinančios viršutinę.
9. Dėl funkcijų skambinimo, rekursijos vykdymas yra lėtesnis, o iteracijos vykdymas yra greitesnis.
10. Rekursija sumažina kodo dydį, o iteracijos - kodą ilgiau.

Išvada:

Rekursyvią funkciją lengva rašyti, tačiau jie neveikia gerai, lyginant su iteracija, o iteracija sunku rašyti, tačiau jų atlikimas yra geras, palyginti su rekursija.