Galvenā atšķirība - rekursija pret atkārtojumu
Rekursiju un atkārtojumu var izmantot, lai atrisinātu programmēšanas problēmas. 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āda, ka rekursija ir mehānisms, lai izsauktu funkciju tajā pašā funkcijā, savukārt iterācija ir atkārtoti izpildīt instrukciju kopu, līdz dotais nosacījums ir patiess. Rekursija un iterācija ir galvenie paņēmieni algoritmu izstrādē un programmatūras lietojumu izveidē.
SATURS
1. Pārskats un galvenās atšķirības
2. Kas ir rekursija
3. Kas ir atkārtojums
4. Rekursijas un iterācijas līdzības
5. Blakus salīdzinājums - Rekursija vs atkārtojums tabulas veidā
6. Kopsavilkums
Kas ir rekursija?
Kad funkcija sevi izsauc funkcijas ietvaros, to sauc par Rekursiju. Ir divu veidu rekursija. Tie ir ierobežota rekursija un bezgalīga rekursija. Galīgai rekursijai ir beigu nosacījums. Bezgalīgai rekursijai nav beigu nosacījuma.
Rekursiju var izskaidrot, izmantojot programmu, lai aprēķinātu faktorialus.
n! = n * (n-1) !, ja n> 0
n! = 1, ja n = 0;
Skatiet zemāk redzamo kodu, lai aprēķinātu faktoriālo vērtību 3 (3! = 3 * 2 * 1).
intmain () {
int vērtība = faktoriāls (3);
printf (“Faktoriāls ir% d / n”, vērtība);
atgriešanās 0;
}
intaktuāls (intn) {
ja (n == 0) {
atgriezties 1;
}
cits {
atgriešanās n * faktoriāls (n-1);
}
}
Izsaucot faktoriālu (3), šī funkcija izsauks faktoriālo (2). Zvanot uz faktoriālo (2), šī funkcija izsauks faktoriālo (1). Tad faktoriāls (1) sauks faktoriālo (0). faktoriāls (0) atgriezīsies 1. Iepriekš minētajā programmā bāzes nosacījums ir “if block” nosacījums n == 0. Saskaņā ar Līdzīgi faktoriālo funkciju sauc atkal un atkal.
Rekursīvās funkcijas ir saistītas ar skursteni. C valodā galvenajai programmai var būt daudzas funkcijas. Tātad, main () ir izsaukšanas funkcija, un funkcija, kuru izsauc galvenā programma, ir tā sauktā funkcija. Kad funkcija tiek izsaukta, vadība tiek piešķirta izsauktajai funkcijai. Pēc funkcijas izpildes vadība tiek atgriezta galvenajā. Tad galvenā programma turpinās. Tātad, lai turpinātu izpildi, tiek izveidots aktivizācijas ieraksts vai kaudzes rāmis.
01. attēls: Rekursija
Iepriekš minētajā programmā, izsaucot faktoriālu (3) no galvenā, tas zvanu kaudzē izveido aktivizācijas ierakstu. Pēc tam tiek izveidots faktoriālais (2) kaudzes rāmis un tā tālāk. Aktivizācijas ieraksts glabā informāciju par lokālajiem mainīgajiem utt. Katru reizi, kad tiek izsaukta funkcija, kaudzes augšpusē tiek izveidota jauna lokālo mainīgo kopa. Šie kaudzes rāmji var palēnināt ātrumu. Tāpat rekursijā funkcija sevi sauc. Rekursīvās funkcijas laika sarežģītība tiek noteikta pēc reižu skaita, funkcija tiek izsaukta. Laika sarežģītība vienam funkcijas izsaukumam ir O (1). N rekursīvo zvanu skaitam laika sarežģītība ir O (n).
Kas ir atkārtojums?
Atkārtojums ir instrukciju bloks, kas atkārtojas atkal un atkal, līdz dotais nosacījums ir patiess. Atkārtojumu var panākt, izmantojot “for loop”, “do-while loop” vai “while loop”. “Cilpai” sintakse ir šāda.
par (inicializēšana; nosacījums; modificēt) {
// paziņojumi;
}
02. attēls: “cilpas plūsmas diagrammai”
Vispirms tiek veikts inicializācijas solis. Šis solis ir deklarēt un inicializēt cilpas vadības mainīgos. Ja nosacījums ir patiess, izpilda cirtaino lencīšu iekšienē esošos apgalvojumus. Šie paziņojumi tiek izpildīti, kamēr nosacījums ir patiess. Ja nosacījums ir nepatiess, vadīkla pāriet uz nākamo paziņojumu aiz “for loop”. Pēc paziņojumu izpildīšanas cilpa iekšpusē vadīkla pāriet uz sadaļas modificēšanu. Tas ir atjaunināt cilpas vadības mainīgo. Tad stāvoklis tiek pārbaudīts vēlreiz. Ja nosacījums ir patiess, tiks izpildīti paziņojumi cirtaino lencīšu iekšpusē. Tādā veidā atkārtojas “for loop”.
Sadaļā “while loop” paziņojumi cilpas iekšpusē tiek izpildīti, līdz nosacījums ir patiess.
while (nosacījums) {
//paziņojumi
}
Cilnē “do-while” stāvoklis tiek pārbaudīts cikla beigās. Tātad, cilpa tiek izpildīta vismaz vienu reizi.
darīt {
//paziņojumi
} while (nosacījums)
Programma, lai atrastu faktori no 3 (3!), Izmantojot iterāciju (“ciklam”), ir šāda.
int main () {
intn = 3, faktoriāls = 1;
inti;
par (i = 1; i <= n; i ++) {
faktoriāls = faktoriāls * i;
}
printf (“Faktoriāls ir% d / n”, faktoriāls);
atgriešanās 0;
}
Kādas ir rekursijas un atkārtojumu līdzības?
- Abi ir paņēmieni problēmas risināšanai.
- Uzdevumu var atrisināt vai nu rekursijā, vai atkārtojumā.
Kāda ir atšķirība starp rekursiju un atkārtojumiem?
Atšķirīgs raksts vidū pirms tabulas
Rekursija vs atkārtojums |
|
| Rekursija ir metode, kā izsaukt funkciju tajā pašā funkcijā. | Atkārtojums ir instrukciju bloks, kas atkārtojas, līdz dotais nosacījums ir patiess. |
| Kosmosa sarežģītība | |
| Rekursīvo programmu sarežģītība kosmosā ir augstāka nekā atkārtojumi. | Kosmosa sarežģītība ir mazāka iterācijās. |
| Ātrums | |
| Rekursijas izpilde ir lēna. | Parasti iterācija notiek ātrāk nekā rekursija. |
| Stāvoklis | |
| Ja nav pārtraukuma nosacījuma, var būt bezgalīga rekursija. | Ja nosacījums nekad nekļūst nepatiess, tas būs bezgalīgs atkārtojums. |
| Kaudze | |
| Rekursijā kaudze tiek izmantota vietējo mainīgo glabāšanai, kad tiek izsaukta funkcija. | Atkārtojot, kaudze netiek izmantota. |
| Kodu lasāmība | |
| Rekursīvā programma ir lasāmāka. | Iteratīvo programmu ir grūtāk nolasīt nekā rekursīvo programmu. |
Kopsavilkums - rekursija pret atkārtojumu
Šajā rakstā tika apspriesta rekursijas un atkārtojuma atšķirība. Abus var izmantot, lai atrisinātu programmēšanas problēmas. Atšķirība starp rekursiju un iterāciju ir tāda, ka rekursija ir mehānisms, kas izsauc funkciju tajā pašā funkcijā, un iterācija to izpilda instrukciju kopumu atkārtoti, līdz dotais nosacījums ir patiess. Ja problēmu var atrisināt rekursīvā formā, to var atrisināt arī, izmantojot atkārtojumus.
Lejupielādējiet rekursijas vs atkārtojuma PDF versiju
Jūs varat lejupielādēt šī raksta PDF versiju un izmantot to bezsaistes vajadzībām, kā norādīts piezīmē. Lūdzu, lejupielādējiet PDF versiju šeit Starpība starp rekursiju un atkārtojumiem
