Rekursiya vs Iteratsiya

Image source: medium.com

“Rekursiya nimaligini tushunish uchun oldin rekursiya nimagligini tushunish kerak” — Stephen Hawking

Sizlar bilan rekursiya nimaligi va uni ishlatishdagi asosiy shartlar haqida gaplashgandik. Endi rekursiyaning iteratsiya bilan solishtirib, ularning o’xshash va farqli jihatlari, bir-biridan ustunlik va kamchiliklari haqida gaplashib o’tamiz.

Buning uchun birinchi darsda qo’llangan usuldan, hikoya usulidan foydalanamiz:

Kichik hikoya…

Tasavvur qiling siz qulflangan xona ichidasiz va sizda ichida kaliti bor quti bor. Lekin, qutini ichini ochsangiz uning ichida bir nechta kichikroq qutilar chiqdi. Kalitni topish uchun keyingi qadamingiz qanday bo’lar edi?

1-usul: (Iterativ usul)

1. Hamma qutilarni qator qilib qo’yib olamiz
2. Qatorimizda quti qolmagunicha quyidagi ishlarni qilamiz
3. Qatordagi birinchi qutini olamiz
4. Agar uning ichidan yana quti chiqsa uni qator oxiriga qo’shamiz.
5. Agar kalit chiqsa ishimiz yakunlanadi
6. 2-qadamga qaytamiz.

2-usul: (Rekursiv usul)

1. Quti ichidagi hamma narsani ko’rib boramiz
2. Agar kalit chiqsa, ishimiz yakunlanadi
3. Agar quti chiqsa o’sha quti uchun 1-qadamga qaytamiz
4. Quti ichida hech narsa qolmasa, ishimizni bitta oldingi qutida qolgan joyimizdan davom etamiz.

Qaysi usul soddaroq tuyilyapti? Ikki usulda ham biz oxirida o’z maqsadimizga erishamiz, ya’ni kalitni topamiz. Lekin, e’tibor bering rekursiv usul bizga tezlikdan yutishga yordam bermaydi aksincha ba’zan rekursiv usul iterativ usuldan ko’ra sekinroq ishlashi mumkin. Ammo, rekursiya masala yechimini soddaroq qismlarga ajratib yechishga imkon beradi va bu o’z navbatida boshqa odamlar uchun ham yechimni tushunarli qiladi.

Esda tuting! Har qanday iterativ usulda ishlash mumkin bo’lgan masalani rekursiya yordamida ham ishlash mumkin va buning aksi ham to’g’ri.

Shunday ekan, rekursiya bu iterativ usulda yechish imkoni yo’q masalani ishlashda yordam bermaydi, balki shu masalani ishlanish usuli va yoziladigan kodni soddalashtirib berishi mumkin. Iteratsiya haqida ham shu gapni aytish mumkin.

Rekursiv usulni iterativ usuldan kamchiliklari

• Rekursiv usul oldingi darsda aytilgan xotira stackidan foydalangani uchun iterativ usuldan ko’ra xotiradan qo’shimcha joy oladi. Ya’ni har bir chaqirilgan funksiya call stackda saqlanishi uchun operativ xotiradan joy kerak bo’ladi. Iterativ usulda esa bunday muammo deyarli yo’q.
• Aynan shu call stackga funksiyalar qo’shilishi va ularni qayta chaqirib olish rekursiya ishini iteratsiyaga qaraganda sekinlashtiradi.
• va yana boshqa kamchiliklar haqida quyidagi darsimizda gaplashib o’tgandik

Rekursiv usulni iterativ usuldan avfzalliklari

Bu haqida ham birinchi darsda to’xtalgan ekanmiz, shuning uchun ularni shunchaki qaytarish kifoya deb hisobladim:

• 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.

Asosan shu jihatlar rekursiya va iteratsiyani bir biridan ajratib turadi.

Maqolani foydali deb hisoblasangiz uni do’stlaringizga ham ulashing!

Manba: @AlgorithmUz telegram kanali

YouTube kanalimiz: Algorithms Uzbekistan

“Eng yaxshi reklama — bu mamnun mijoz tomonidan qilingan reklama” — Philip Kotler