Skirtumas tarp rekursijos ir pakartojimo
Turinys
Rekursija ir iteracija tiek pakartotinai vykdo instrukcijų rinkinį. Rekursija yra tada, kai funkcijos teiginys pakartotinai skambina. Pasikartojimas yra tada, kai kilpa pakartotinai vykdoma, kol valdymo sąlyga tampa klaidinga. Pagrindinis rekursijos ir iteracijos skirtumas yra tas, kad a rekursija yra procesas, visada taikomas funkcijai. iteracija yra taikomas instrukcijų rinkiniui, kurį norime pakartotinai vykdyti.
- Palyginimo diagrama
- Apibrėžimas
- Pagrindiniai skirtumai
- Išvada
Palyginimo diagrama
| Palyginimo pagrindas | Rekursija | Iteracija |
|---|---|---|
| Pagrindinis | Teiginys funkcijų rinkinyje vadina pačią funkciją. | Leidžia pakartotinai vykdyti instrukcijų rinkinį. |
| Formatas | Atliekant rekursinę funkciją, nurodomos tik nutraukimo sąlygos (pagrindinė byla). | Iteracija apima inicializavimą, sąlygą, ataskaitos vykdymą kilpoje ir valdymo kintamojo atnaujinimą (didinimas ir mažinimas). |
| Nutraukimas | Į funkcijos pagrindą įtrauktas sąlyginis sakinys, kuris verčia funkciją grįžti neįvykstant rekursiniam skambučiui. | Iteracijos teiginys pakartotinai vykdomas, kol bus pasiekta tam tikra sąlyga. |
| Būklė | Jei funkcija nekonverguoja į kokią nors sąlygą, vadinamą (pagrindiniu atveju), ji lemia begalinį pasikartojimą. | Jei kontrolės sąlyga iteracijos teiginyje niekada netaps klaidinga, tai lems begalinę iteraciją. |
| Begalinis kartojimas | Begalinis pasikartojimas gali sugadinti sistemą. | Begalinis ciklas pakartotinai naudoja procesoriaus ciklus. |
| Taikoma | Rekursija visada taikoma funkcijoms. | Iteracija taikoma iteracijos sakiniams arba „kilpoms“. |
| Stack | Rietuvė naudojama naujų vietinių kintamųjų ir parametrų rinkiniui saugoti kiekvieną kartą, kai iškviečiama funkcija. | Nenaudoja kamino. |
| Virš galvos | Rekursija apima pakartotinių funkcijų skambučius. | Nėra pakartotinio funkcijos skambučio. |
| Greitis | Lėtas vykdymas. | Greitas vykdymas. |
| Kodo dydis | Rekursija sumažina kodo dydį. | Dėl pakartojimo kodas tampa ilgesnis. |
Rekursijos apibrėžimas
„C ++“ leidžia funkcijai paskambinti savo kode. Tai reiškia, kad funkcijos apibrėžimas turi funkciją kviesti save. Kartais tai dar vadinama „apskrito apibrėžimas“. Vietinis kintamųjų ir parametrų rinkinys, kurį naudoja funkcija, yra naujai sukuriamas kiekvieną kartą, kai funkcija pati paskambina, ir yra saugoma krūvos viršuje. Bet kiekvieną kartą, kai funkcija pašaukiama, ji nesukuria naujos tos funkcijos kopijos. Rekursyvinė funkcija žymiai nesumažina kodo dydžio ir net nepagerina atminties panaudojimo, tačiau, palyginti su iteracija, ji šiek tiek pagerėja.
Norėdami nutraukti rekursiją, į funkcijos apibrėžimą turite įtraukti pasirinktą sakinį, kad priverstumėte funkciją grįžti, nekeldamas sau rekursinio skambučio. Pasirinkto teiginio nebuvimas rekursyvinės funkcijos apibrėžime leis funkcijai neribotai pasikartoti, kai tik ji bus iškviesta.
Supraskime rekursiją su funkcija, kuri grąžins skaičiaus faktorialą.
int faktorialus (int num) {int atsakymas; if (num == 1) {grįžti 1; } else {answer = faktorinis (num-1) * num; // rekursinis skambinimas} grįžimas (atsakymas); }
Aukščiau pateiktame kode kitoje dalyje pateiktas teiginys parodo rekursiją, nes teiginys vadina funkcijos faktorialą (), kurioje jis yra.
Iteracijos apibrėžimas
Iteracija yra pakartotinis instrukcijų rinkinio vykdymo procesas, kol iteracijos teiginyje esanti sąlyga tampa klaidinga. Į iteracijos teiginį įeina inicializavimas, palyginimas, vykdymas iteracijos sakinyje ir galiausiai valdymo kintamojo atnaujinimas. Atnaujinus kontrolinį kintamąjį, jis vėl lyginamas ir procesas kartojasi tol, kol iteracijos teiginyje esanti sąlyga pasirodo klaidinga. Iteracijos sakiniai yra „už“, „o“, „o“, „daryti“.
Iteracijos teiginyje nenaudojama krūva kintamiesiems laikyti. Taigi iteracijos teiginio vykdymas yra greitesnis, palyginti su rekursine funkcija. Netgi iteracijos funkcija neturi pakartotinių funkcijų iškvietimų, o tai taip pat padaro jos vykdymą greitesnę nei rekursinė funkcija. Iteracija nutraukiama, kai kontrolės sąlyga tampa klaidinga. Kontrolės sąlygos nebuvimas iteracijos sakinyje gali sukelti begalinę kilpą arba sudaryti kompiliavimo klaidą.
Supraskime aukščiau pateikto pavyzdžio iteraciją.
int faktorialus (int num) {int atsakymas = 1; // reikia inicijavimo, nes jame gali būti šiukšlių reikšmė prieš juos inicijuojant (int t = 1; t> num; t ++) // iteracija {answer = answer * (t); grįžti (atsakyti); }}
Aukščiau esančiame kodekse funkcija grąžina skaičiaus faktorialą, naudodama iteracijos teiginį.
- Rekursija yra tada, kai metodas programoje pakartotinai vadina save, o pasikartojimas yra tada, kai programoje nurodytos instrukcijos yra pakartotinai vykdomos.
- Rekursinį metodą sudaro instrukcijų rinkinys, pats sakinys ir pabaigos sąlyga, o iteracijos sakiniuose yra iniciacija, prieaugis, sąlyga, nurodymų rinkinys kilpoje ir valdymo kintamasis.
- Sąlyginis teiginys nusprendžia nutraukti rekursiją, o kontrolės kintamojo vertė nusprendžia nutraukti pakartojimo teiginį.
- Jei metodas nesukelia baigimo sąlygų, jis vėl pradeda begalę. Kita vertus, jei valdymo kintamasis niekada nevadina baigties vertės, iteracijos teiginys pakartojamas be galo.
- Begalinis pasikartojimas gali sukelti sistemos gedimą, tuo tarpu begalinis iteravimas sunaudoja procesoriaus ciklus.
- Rekursija visada taikoma metodui, o iteracija taikoma instrukcijų rinkiniui.
- Rekursijos metu sukurti kintamieji yra saugomi krūvoje, tuo tarpu iteracijai nereikia krūvos.
- Rekursija sukelia pakartotinių funkcijų iškvietimą, o iteracija neturi funkcijos, iššaukiančios pridėtinę vertę.
- Dėl funkcijų iškėlimo rekursijos vykdymas yra lėtesnis, o iteracijos vykdymas yra greitesnis.
- Rekursija sumažina kodo dydį, tuo tarpu kartojimai daro kodą ilgesnį.
Išvada:
Rekursyvinę funkciją lengva parašyti, tačiau jos, palyginti su iteracija, neveikia gerai, tuo tarpu sunku pakartoti iteraciją, tačiau jų atlikimas yra geras, palyginti su rekursija.
