Galvenā atšķirība - rekursija pret iterāciju
Rekursiju un iterāciju var izmantot programmēšanas problēmu risināšanai. Pieeja problēmas risināšanai, izmantojot rekursiju vai iterāciju, ir atkarīga no problēmas risināšanas veida. Galvenā atšķirība starp rekursiju un iterāciju ir tā, ka rekursija ir mehānisms funkcijas izsaukšanai tajā pašā funkcijā, savukārt iterācija ir atkārtota instrukciju kopas izpilde, līdz noteiktais nosacījums ir patiess. Rekursija un iterācija ir galvenās metodes algoritmu izstrādei un programmatūras lietojumprogrammu veidošanai.
Kas ir rekursija?
Kad funkcija izsauc sevi funkcijā, to sauc par rekursiju. Ir divu veidu rekursija. Tās ir ierobežotas rekursijas un bezgalīgas rekursijas. Ierobežotai rekursijai ir beigu nosacījums. Bezgalīgai rekursijai nav beigu nosacījuma.
Rekursiju var izskaidrot, izmantojot programmu faktoriālu aprēķināšanai.
n!=n(n-1)!, ja n>0
n!=1, ja n=0;
Skatiet tālāk norādīto kodu, lai aprēķinātu koeficientu 3(3!=321).
intmain () {
int vērtība=faktoriāla (3);
printf(“Faktiskais ir %d\n”, vērtība);
atgriezties 0;
}
infactorial (intn) {
if(n==0) {
atgriezties 1;
}
cits {
atgriezties n faktoriāls(n-1);
}
}
Izsaucot faktoriālu (3), šī funkcija izsauks faktoriālu (2). Izsaucot faktoriālu (2), šī funkcija izsauks faktoriālu (1). Tad faktoriāls (1) izsauks faktoriālu (0). faktoriāls (0) atgriezīs 1. Iepriekš minētajā programmā n==0 nosacījums “ja blokā” ir pamatnosacījums. Saskaņā ar Tāpat faktoriālo funkciju izsauc atkal un atkal.
Rekursīvās funkcijas ir saistītas ar steku. C valodā galvenajai programmai var būt daudz funkciju. Tātad galvenā () ir izsaukšanas funkcija, un funkcija, kuru izsauc galvenā programma, ir izsauktā funkcija. Kad funkcija tiek izsaukta, vadība tiek piešķirta izsauktajai funkcijai. Kad funkcijas izpilde ir pabeigta, vadība tiek atgriezta galvenajā režīmā. Pēc tam galvenā programma turpinās. Tādējādi tiek izveidots aktivizācijas ieraksts vai steka rāmis, lai turpinātu izpildi.
Attēls 01: Rekursija
Iepriekšminētajā programmā, izsaucot faktoriālu (3) no galvenā, tā izveido aktivizācijas ierakstu zvanu kaudzē. Pēc tam virs steka tiek izveidots faktoriāls (2) skursteņa rāmis un tā tālāk. Aktivizācijas ierakstā tiek saglabāta informācija par vietējiem mainīgajiem utt. Katru reizi, kad funkcija tiek izsaukta, steka augšpusē tiek izveidota jauna vietējo mainīgo kopa. Šie kaudzes rāmji var palēnināt ātrumu. Tāpat rekursijā funkcija izsauc sevi. Rekursīvās funkcijas laika sarežģītību nosaka pēc reižu skaita, funkcija tiek izsaukta. Viena funkcijas izsaukuma laika sarežģītība ir O(1). n skaitam rekursīvo zvanu laika sarežģītība ir O(n).
Kas ir iterācija?
Iterācija ir instrukciju bloks, kas atkārtojas atkal un atkal, līdz dotais nosacījums ir patiess. Iterāciju var panākt, izmantojot “for loop”, “do-while loop” vai “while loop”. Sintakse “cilpai” ir šāda.
for (inicializācija; nosacījums; modifikācija) {
// paziņojumi;
}
Attēls 02: “cilpas plūsmas diagramma”
Pirmais tiek izpildīts inicializācijas solis. Šis solis ir cilpas vadības mainīgo deklarēšana un inicializācija. Ja nosacījums ir patiess, tiek izpildīti priekšraksti cirtainajās iekavās. Šie paziņojumi tiek izpildīti, līdz nosacījums ir patiess. Ja nosacījums ir nepatiess, vadīkla pāriet uz nākamo paziņojumu pēc cilpas “for”. Pēc priekšrakstu izpildes cilpas iekšpusē, vadīkla pāriet uz modifikācijas sadaļu. Tas ir, lai atjauninātu cilpas vadības mainīgo. Pēc tam stāvoklis tiek pārbaudīts vēlreiz. Ja nosacījums ir patiess, tiks izpildīti cirtainajās lencēs esošie paziņojumi. Tādā veidā atkārtojas cilpa.
Cilpā “while loop” cilpas iekšpusē esošie paziņojumi tiek izpildīti, līdz nosacījums ir patiess.
kamēr (stāvoklis){
//paziņojumi
}
Cipā “do-while” nosacījums tiek pārbaudīts cilpas beigās. Tātad cilpa tiek izpildīta vismaz vienu reizi.
do{
//paziņojumi
}, kamēr(stāvoklis)
Programma, lai atrastu koeficientu 3 (3!), izmantojot iterāciju (“cilpai”), ir šāda.
int main(){
intn=3, faktoriāls=1;
inti;
for(i=1; i<=n; i++){
faktoriāls=faktoriālsi;
}
printf(“Faktiskais ir %d\n”, faktoriāls);
atgriezties 0;
}
Kādas ir līdzības starp rekursiju un iterāciju?
- Abas ir problēmas risināšanas metodes.
- Uzdevumu var atrisināt vai nu rekursijā, vai iterācijā.
Kāda ir atšķirība starp rekursiju un iterāciju?
Rekursija pret iterāciju |
|
| Rekursija ir vienas funkcijas funkcijas izsaukšanas metode. | Iterācija ir instrukciju bloks, kas atkārtojas, līdz norādītais nosacījums ir patiess. |
| Kosmosa sarežģītība | |
| Rekursīvo programmu telpas sarežģītība ir lielāka nekā iterāciju. | Telpas sarežģītība iterācijās ir mazāka. |
| Ātrums | |
| Rekursijas izpilde ir lēna. | Parasti iterācija ir ātrāka nekā rekursija. |
| Stāvoklis | |
| Ja nav izbeigšanas nosacījuma, var būt bezgalīga rekursija. | Ja nosacījums nekad nekļūst nepatiess, tā būs bezgalīga iterācija. |
| Steck | |
| Rekursijā kaudze tiek izmantota vietējo mainīgo saglabāšanai, kad funkcija tiek izsaukta. | Iterācijas laikā steks netiek izmantots. |
| Koda lasāmība | |
| Rekursīvā programma ir lasāmāka. | Iteratīvo programmu ir grūtāk lasīt nekā rekursīvu programmu. |
Kopsavilkums - rekursija pret iterāciju
Šajā rakstā tika apspriesta atšķirība starp rekursiju un iterāciju. Abus var izmantot programmēšanas problēmu risināšanai. Atšķirība starp rekursiju un iterāciju ir tāda, ka rekursija ir mehānisms, lai izsauktu funkciju tajā pašā funkcijā un iterētu to, lai atkārtoti izpildītu instrukciju kopu, līdz noteiktais nosacījums ir patiess. Ja problēmu var atrisināt rekursīvā formā, to var atrisināt arī, izmantojot iterācijas.
Lejupielādēt PDF versiju Recursion vs Iteration
Varat lejupielādēt šī raksta PDF versiju un izmantot to bezsaistē saskaņā ar atsauces piezīmi. Lūdzu, lejupielādējiet PDF versiju šeit Atšķirība starp rekursiju un iterāciju
