Asosiy farq – Rekursiya va takrorlash
Rekursiya va iteratsiyadan dasturlash masalalarini yechishda foydalanish mumkin. Rekursiya yoki iteratsiya yordamida masalani yechishga yondashuv muammoni yechish yo‘liga bog‘liq. Rekursiya va iteratsiya o'rtasidagi asosiy farq shundaki, rekursiya - bu bir xil funktsiya ichidagi funktsiyani chaqirish mexanizmi, iteratsiya esa berilgan shart to'g'ri bo'lgunga qadar ko'rsatmalar to'plamini qayta-qayta bajarishdir. Rekursiya va iteratsiya algoritmlarni ishlab chiqish va dasturiy ilovalar yaratish uchun asosiy usullardir.
Rekursiya nima?
Funksiya funksiya ichida oʻzini chaqirganda, u Rekursiya deb nomlanadi. Rekursiyaning ikki turi mavjud. Ular chekli rekursiya va cheksiz rekursiyadir. Cheklangan rekursiya tugatish shartiga ega. Cheksiz rekursiyada tugatish sharti yo‘q.
Rekursiyani faktoriallarni hisoblash uchun dastur yordamida tushuntirish mumkin.
n!=n(n-1)!, agar n>0
n!=1, agar n=0;
3(3!=321) faktorialini hisoblash uchun quyidagi kodga qarang.
intmain () {
int qiymati=faktorial (3);
printf(“Faktorial %d\n”, qiymat);
qaytish 0;
}
intfaktorial (intn) {
agar(n==0) {
qaytish 1;
}
boshqa {
qaytish n faktorial(n-1);
}
}
Faktorial (3) ni chaqirganda, bu funksiya faktorial (2) chaqiradi. Faktorial (2) ni chaqirganda, bu funksiya faktorial (1) ni chaqiradi. Keyin faktorial (1) faktorial (0) chaqiradi. faktorial (0) 1 ni qaytaradi. Yuqoridagi dasturda “if bloki”dagi n==0 shart asosiy shart hisoblanadi. Xuddi shunday, faktorial funksiya qayta-qayta chaqiriladi.
Rekursiv funksiyalar stek bilan bogʻliq. C tilida asosiy dastur ko'plab funktsiyalarga ega bo'lishi mumkin. Demak, main () chaqiruvchi funksiya, asosiy dastur tomonidan chaqiriladigan funksiya esa chaqirilgan funksiyadir. Funksiya chaqirilganda boshqaruv chaqirilgan funksiyaga beriladi. Funktsiyani bajarish tugagandan so'ng, boshqaruv asosiyga qaytariladi. Keyin asosiy dastur davom etadi. Shunday qilib, u faollashtirish yozuvini yoki ijroni davom ettirish uchun stek ramkasini yaratadi.
01-rasm: Rekursiya
Yuqoridagi dasturda asosiydan faktorial (3) ga qoʻngʻiroq qilganda qoʻngʻiroqlar toʻplamida faollashtirish yozuvini yaratadi. Keyin stekning tepasida faktorial (2) stek ramkasi yaratiladi va hokazo. Faollashtirish yozuvi mahalliy o'zgaruvchilar va hokazolar haqidagi ma'lumotlarni saqlaydi. Funktsiya har safar chaqirilganda, stekning yuqori qismida mahalliy o'zgaruvchilarning yangi to'plami yaratiladi. Ushbu stack ramkalar tezlikni sekinlashtirishi mumkin. Xuddi shunday, rekursiyada ham funktsiya o'zini chaqiradi. Rekursiv funksiya uchun vaqt murakkabligi necha marta topiladi, funksiya chaqiriladi. Bitta funktsiya chaqiruvi uchun vaqt murakkabligi O(1) ga teng. Rekursiv qo‘ng‘iroqlarning n soni uchun vaqt murakkabligi O(n).
Iteratsiya nima?
Iteratsiya - bu berilgan shart to'g'ri bo'lgunga qadar qayta-qayta takrorlanadigan ko'rsatmalar blokidir. Iteratsiyaga “for loop”, “do-while loop” yoki “while loop” yordamida erishish mumkin. “for loop” sintaksisi quyidagicha.
uchun (boshlash; shart; oʻzgartirish) {
// bayonotlar;
}
02-rasm: “loop oqim diagrammasi”
Initializatsiya bosqichi birinchi navbatda amalga oshiriladi. Ushbu qadam tsiklni boshqarish o'zgaruvchilarini e'lon qilish va ishga tushirishdir. Agar shart rost bo'lsa, jingalak qavs ichidagi gaplar bajariladi. Ushbu bayonotlar shart to'g'ri bo'lgunga qadar bajariladi. Agar shart noto'g'ri bo'lsa, boshqaruv "for loop" dan keyin keyingi bayonotga o'tadi. Lokal ichidagi operatorlar bajarilgandan so'ng, boshqaruv elementi o'zgartirish bo'limiga o'tadi. Bu loop boshqaruv o'zgaruvchisini yangilashdir. Keyin holat yana tekshiriladi. Agar shart rost bo'lsa, jingalak qavs ichidagi gaplar bajariladi. Shu tarzda “for loop” takrorlanadi.
“While loop”da sikl ichidagi gaplar shart rost boʻlguncha bajariladi.
while (holat){
//bayonotlar
}
“do-while” siklida shart tsikl oxirida tekshiriladi. Shunday qilib, tsikl kamida bir marta bajariladi.
qilish{
//bayonotlar
} while(shart)
Iteratsiya (“for loop”) yordamida 3 (3!) ning faktorialini topish dasturi quyidagicha.
int main(){
intn=3, faktorial=1;
inti;
for(i=1; i<=n; i++){
faktorial=faktoriali;
}
printf(“Faktorial %d\n”, faktorial);
qaytish 0;
}
Rekursiya va iteratsiya oʻrtasidagi oʻxshashliklar qanday?
- Ikkalasi ham muammoni hal qilish texnikasi.
- Vazifani rekursiya yoki iteratsiyada hal qilish mumkin.
Rekursiya va iteratsiya oʻrtasidagi farq nima?
Rekursiya va takrorlash |
|
| Rekursiya bir xil funksiya ichidagi funksiyani chaqirish usulidir. | Takrorlash - berilgan shart rost boʻlgunga qadar takrorlanadigan koʻrsatmalar blokidir. |
| Kosmik murakkablik | |
| Rekursiv dasturlarning fazoviy murakkabligi iteratsiyalardan yuqori. | Kosmik murakkablik takrorlanishlarda kamroq. |
| Tezlik | |
| Rekursiya sekin bajarilmoqda. | Odatda iteratsiya rekursiyaga qaraganda tezroq. |
| Holat | |
| Agar tugatish sharti boʻlmasa, cheksiz rekursiya boʻlishi mumkin. | Agar shart hech qachon noto'g'ri bo'lmasa, u cheksiz iteratsiya bo'ladi. |
| Stack | |
| Rekursiyada funktsiya chaqirilganda stek mahalliy o'zgaruvchilarni saqlash uchun ishlatiladi. | Iteratsiyada stek ishlatilmaydi. |
| Kodni o'qish imkoniyati | |
| Rekursiv dastur koʻproq oʻqilishi mumkin. | Iterativ dasturni o'qish rekursiv dasturga qaraganda qiyinroq. |
Xulosa – Rekursiya va takrorlash
Ushbu maqolada rekursiya va iteratsiya oʻrtasidagi farq muhokama qilingan. Ikkalasi ham dasturlash muammolarini hal qilish uchun ishlatilishi mumkin. Rekursiya va iteratsiya o'rtasidagi farq shundaki, rekursiya bir xil funktsiya doirasidagi funktsiyani chaqirish va berilgan shart rost bo'lgunga qadar ko'rsatmalar to'plamini qayta-qayta bajarish uchun uni iteratsiya qilish mexanizmidir. Agar muammoni rekursiv shaklda hal qilish mumkin bo'lsa, uni iteratsiyalar yordamida ham hal qilish mumkin.
Rekursiya va iteratsiyaning PDF versiyasini yuklab oling
Siz ushbu maqolaning PDF-versiyasini yuklab olishingiz va iqtibos keltirgan holda oflayn maqsadlarda foydalanishingiz mumkin. Iltimos, PDF versiyasini bu yerdan yuklab oling Rekursiya va iteratsiya o'rtasidagi farq
