|
Rekursiya deyarli hamma joyda ishlatiladi
|
| bet | 5/6 | | Sana | 29.05.2024 | | Hajmi | 2,45 Mb. | | #256522 |
Bog'liq Algoritm tahlili asoslariga kirish Rekursiya deyarli hamma joyda ishlatiladi. Ya’ni, lo’nda qilib aytganda undan qochib qutilishning iloji yo’q. Harakat qilib ko’rish esa qimmatga tushishi aniq.
Ba’zi holatlarda rekursiv yechim ancha soddaroq. Ayniqsa, ba’zi masalalarning iterativ yechimi juda ham uzun bo’lib ketishi mumkin. Rekursiya esa kodni bir necha barobar qisqartirib berishi mumkin.
- Aksariyat tuzilmalar va algoritmlarni rekursiyasiz tasavvur qilib bo’lmaydi. Tree, Graph, Heap, QuickSort, MergeSort, … Bu ro’yhatni juda uzoq davom ettirish mumkin. Ayniqsa, murakkab tuzilmalar bo’lgan Tree va Graphlarda rekursiya har qadamda uchraydi. Dasturchilikni esa ularsiz tasavvur qilib bo’lmaydi, bu esa o’z o’rnida rekursiya qanchalik muhimligini belgilab beradi.
- Rekursiya funksional dasturlashning asosiy elementlaridan hisoblanadi. Hali funksional dasturlash haqida eshitmagan bo’lsangiz u haqida ma’lumot axtarib o’qib ko’rishni maslahat beraman. Bir so’z bilan aytganda, hozirda dasturlash sohasi jadallik bilan funksional dasturlash paradigmasi tomon ketmoqda (Go va Scala yorqin namunalar).
Endi rekursiyaning iteratsiya bilan solishtirib, ularning o’xshash va farqli jihatlari, bir-biridan ustunlik va kamchiliklari haqida gaplashib o’tamiz.
1-usul: (Iterativ usul)
- Hamma qutilarni qator qilib qo’yib olamiz
- Qatorimizda quti qolmagunicha quyidagi ishlarni qilamiz
- Qatordagi birinchi qutini olamiz
- Agar uning ichidan yana quti chiqsa uni qator oxiriga qo’shamiz.
- Agar kalit chiqsa ishimiz yakunlanadi
- 2-qadamga qaytamiz.
2-usul: (Rekursiv usul)
- Quti ichidagi hamma narsani ko’rib boramiz
- Agar kalit chiqsa, ishimiz yakunlanadi
- Agar quti chiqsa o’sha quti uchun 1-qadamga qaytamiz
- Quti ichida hech narsa qolmasa, ishimizni bitta oldingi qutida qolgan joyimizdan davom etamiz.
- Rekursiya har doim xotiradan qo’shimcha joy talab qiladi.
- Rekursiv yechimda xato qilib ehtimoli yuqori.
- Rekursiv yechimni xatosini topish qiyin.
- Rekursiv algoritmning murakkabligini hisoblash ko’pincha juda murakkab.
Qidiruv algoritmi - bu ma'lumotlar to'plamidan ma'lum ma'lumotlarni topish uchun ishlatiladigan bosqichma-bosqich protsedura. Bu hisoblashda asosiy protsedura hisoblanadi. Informatika fanida ma'lumotlarni qidirishda tez va sekin dastur o'rtasidagi farq ko'pincha to'g'ri qidiruv algoritmidan foydalanishdir.
|
| |
