Pagrindinis skirtumas – rekursija vs iteracija
Rekursija ir iteracija gali būti naudojamos programavimo problemoms spręsti. Problemos sprendimo būdas naudojant rekursiją arba iteraciją priklauso nuo problemos sprendimo būdo. Pagrindinis skirtumas tarp rekursijos ir iteracijos yra tas, kad rekursija yra mechanizmas, skirtas iškviesti funkciją toje pačioje funkcijoje, o iteracija yra pakartotinai vykdyti instrukcijų rinkinį, kol nurodyta sąlyga yra teisinga. Rekursija ir iteracija yra pagrindiniai algoritmų kūrimo ir programinės įrangos programų kūrimo būdai.
Kas yra rekursija?
Kai funkcija išsikviečia save funkcijoje, ji vadinama rekursija. Yra dviejų tipų rekursija. Tai yra baigtinė ir begalinė rekursija. Baigtinė rekursija turi baigiamąją sąlygą. Begalinė rekursija neturi baigiamosios sąlygos.
Rekursiją galima paaiškinti naudojant faktorių skaičiavimo programą.
n!=n(n-1)!, jei n>0
n!=1, jei n=0;
Žr. toliau pateiktą kodą, kad apskaičiuotumėte faktorialą 3(3!=321).
intmain () {
int vertė=fakcinė (3);
printf(“Faktoriaus vertė yra %d\n”, reikšmė);
grįžti 0;
}
nefactorial (intn) {
if(n==0) {
grįžti 1;
}
kita {
grįžti n faktorialas(n-1);
}
}
Kviečiant faktorialą (3), ši funkcija iškvies faktorialą (2). Iškviečiant faktorialą (2), ši funkcija iškvies faktorialą (1). Tada faktorialas (1) iškvies faktorialą (0). faktorialas (0) grąžins 1. Aukščiau pateiktoje programoje n==0 sąlyga „jei bloke“yra pagrindinė sąlyga. Pagal Lygiai faktorių funkcija iškviečiama vėl ir vėl.
Rekursinės funkcijos yra susijusios su krūva. C kalboje pagrindinė programa gali turėti daug funkcijų. Taigi, pagrindinis () yra iškvietimo funkcija, o funkcija, kurią iškviečia pagrindinė programa, yra vadinamoji funkcija. Kai funkcija iškviečiama, iškviestai funkcijai suteikiamas valdymas. Pasibaigus funkcijos vykdymui, valdiklis grąžinamas į pagrindinį. Tada pagrindinė programa tęsiasi. Taigi, jis sukuria aktyvinimo įrašą arba krūvos rėmelį, kad būtų galima tęsti vykdymą.
01 pav.: Rekursija
Aukščiau pateiktoje programoje, skambinant faktorialu (3) iš pagrindinio, skambučių krūvoje sukuriamas aktyvinimo įrašas. Tada ant krūvos viršaus sukuriamas faktorinis (2) krūvos rėmas ir pan. Aktyvinimo įraše saugoma informacija apie vietinius kintamuosius ir pan. Kiekvieną kartą, kai funkcija iškviečiama, krūvos viršuje sukuriamas naujas vietinių kintamųjų rinkinys. Šie krūvos rėmeliai gali sulėtinti greitį. Panašiai ir rekursijoje funkcija išsikviečia save. Rekursinės funkcijos laiko sudėtingumas nustatomas pagal tai, kiek kartų funkcija iškviečiama. Vieno funkcijos iškvietimo laiko sudėtingumas yra O(1). n skaičiaus rekursinių skambučių laiko sudėtingumas yra O(n).
Kas yra iteracija?
Iteracija yra instrukcijų blokas, kuris kartojasi vėl ir vėl, kol ši sąlyga yra teisinga. Iteraciją galima pasiekti naudojant „for loop“, „do-while loop“arba „while loop“. „for loop“sintaksė yra tokia.
už (inicializavimas; sąlyga; modifikavimas) {
// pareiškimai;
}
02 pav.: „ciklo srauto diagrama“
Pirmiausia įvykdomas inicijavimo veiksmas. Šis veiksmas yra kilpos valdymo kintamųjų deklaravimas ir inicijavimas. Jei sąlyga yra teisinga, vykdomi teiginiai, esantys riestiniuose skliaustuose. Šie teiginiai vykdomi tol, kol sąlyga yra teisinga. Jei sąlyga klaidinga, valdiklis pereina prie kito teiginio po „ciklo“. Įvykdęs teiginius ciklo viduje, valdiklis pereina prie modifikavimo skyriaus. Tai yra atnaujinti kilpos valdymo kintamąjį. Tada būklė dar kartą patikrinama. Jei sąlyga teisinga, bus vykdomi teiginiai, esantys riestiniuose skliaustuose. Tokiu būdu kartojasi „for ciklas“.
„While loop“ciklo viduje esantys teiginiai vykdomi tol, kol sąlyga yra teisinga.
o (sąlyga){
//teiginiai
}
Cilpoje „do-while“sąlyga tikrinama ciklo pabaigoje. Taigi ciklas vykdomas bent kartą.
daryk{
//teiginiai
}, o(sąlyga)
Programa rasti faktorių 3 (3!) naudojant iteraciją („ciklą“) yra tokia.
int main(){
intn=3, faktorialus=1;
inti;
for(i=1; i<=n; i++){
faktorinis=faktorialasi;
}
printf("Factory yra %d\n", faktorialus);
grįžti 0;
}
Kokie yra rekursijos ir iteracijos panašumai?
- Abu yra problemos sprendimo būdai.
- Užduotis gali būti išspręsta rekursijos arba iteracijos būdu.
Kuo skiriasi rekursija ir iteracija?
Rekursija prieš iteraciją |
|
| Rekursija yra tos pačios funkcijos funkcijos iškvietimo metodas. | Iteracija yra instrukcijų blokas, kuris kartojamas tol, kol nurodyta sąlyga yra teisinga. |
| Kosmoso sudėtingumas | |
| Rekursinių programų erdvės sudėtingumas yra didesnis nei iteracijų. | Erdvės sudėtingumas yra mažesnis iteracijų metu. |
| Greitis | |
| Rekursijos vykdymas lėtas. | Paprastai iteracija yra greitesnė nei rekursija. |
| Būklė | |
| Jei nėra nutraukimo sąlygos, gali būti begalinė rekursija. | Jei sąlyga niekada netaps klaidinga, tai bus begalinė iteracija. |
| Stack | |
| Rekursijos metu krūva naudojama vietiniams kintamiesiems saugoti, kai iškviečiama funkcija. | Iteracijoje dėklas nenaudojamas. |
| Kodo skaitomumas | |
| Rekursyvi programa yra lengviau skaitoma. | Iteratyviąją programą sunkiau skaityti nei rekursyvią. |
Santrauka – rekursija prieš iteraciją
Šiame straipsnyje aptariamas skirtumas tarp rekursijos ir iteracijos. Abi gali būti naudojamos programavimo problemoms spręsti. Skirtumas tarp rekursijos ir iteracijos yra tas, kad rekursija yra mechanizmas, leidžiantis iškviesti funkciją toje pačioje funkcijoje ir iteruoti ją, kad būtų vykdomas instrukcijų rinkinys pakartotinai, kol nurodyta sąlyga yra teisinga. Jei problemą galima išspręsti rekursine forma, ją taip pat galima išspręsti naudojant iteracijas.
Atsisiųskite Recursion vs Iteration PDF versiją
Galite atsisiųsti šio straipsnio PDF versiją ir naudoti ją neprisijungus, kaip nurodyta citatos pastaboje. Atsisiųskite PDF versiją čia Skirtumas tarp rekursijos ir iteracijos
