Rekursiya masalalari - Экономика - Курсовые работы

Информация о документе

Цена	13000UZS
Размер	50.0KB
Покупки	0
Дата загрузки	22 Сентябрь 2025
Расширение	docx
Раздел	Курсовые работы
Предмет	Экономика

Rekursiya masalalari

Купить

O‘ZBEKISTON RESPUBLIKASI OLIY TA’LIM, FAN VA INNOVATSIYALAR VAZIRLIGI
BUXORO DAVLAT UNIVERSITETI
« Fizika-matematika va axborot texnologiyalari fakulteti » fakulteti
“Tasdiqlandi”
Axborot tizimlari va raqamli
texnologiyalar kafedrasi
________________________
“____” ___________ 2025 y. “Ro‘yxatga olindi”
Fizika-matematika va axborot
texnologiyalari fakulteti
_________________________
“____” ___________ 2025 y.
“ Dasturlash asoslari ”
f anidan
“ Rekursiya masalalari ” mavzusidagi
KURS ISHI

MUNDARIJA
1.1. Rekursiya tushunchasi va dasturlashdagi o‘rni ............................................ 6
1.2. Rekursiv funksiyalarning ishlash mexanizmi va xotira bilan ishlash
jarayoni ..................................................................................................................... 8
1.3. Rekursiyaning afzalliklari va kamchiliklari ................................................ 10
II BOB. REKURSIV FUNKSIYALAR VA ULARNING
DASTURLASHDAGI QO‘LLANILISHI ........................................................... 12
2.1. Rekursiv funksiyalarni yaratish va ularning ishlash prinsiplari ............... 12
2.2. Rekursiyaning algoritmik yechimlardagi afzalliklari va cheklovlari ........ 14
2.3. Rekursiya va iteratsiyaning solishtirmali tahlili .......................................... 16
III BOB. REKURSIYADAN AMALIY FOYDALANISH VA
MASALALARNI YECHISH ALGORITMLARI .............................................. 19
3.1. Rekursiya asosida masalalarni yechishning umumiy yondashuvi ............. 19
3.2. Rekursiya yordamida matematik va algoritmik masalalarni yechish
usullari .................................................................................................................... 21
3.3. Rekursiv funksiyalarni optimallashtirish va ularning samaradorligini
oshirish usullari ..................................................................................................... 23
XULOSA ................................................................................................................ 27
FOYDALANILGAN ADABIYOTLAR .............................................................. 29
2

KIRISH
Rekursiya – bu dasturlashning fundamental va chuqur mantiqiy fikrlashni
talab qiluvchi usullaridan biri bo ‘ lib , u ko ‘ plab algoritmik muammolarni elegant va
ixcham shaklda yechish imkonini beradi . Ushbu texnika yordamida murakkab
strukturalar va takrorlanuvchi jarayonlar oddiy va aniq ifodalanadi. Zamonaviy
dasturlash tillarining deyarli barchasida, xususan, C++ tilida rekursiyadan keng
foydalaniladi, bu esa uni dasturchilar uchun zaruriy vositaga aylantiradi.
Kurs ishining dolzarbligi
Zamonaviy dasturlashda rekursiya tushunchasi nafaqat nazariy bilimlar
asosini, balki amaliy algoritmik muammolarga samarali yechim topish vositasini
ham tashkil etadi. Bugungi kunda sun’iy intellekt, algoritmlar dizayni, murakkab
ma’lumotlar strukturalari, graflar va daraxtlar bilan ishlashda rekursiya muhim
o‘rin tutadi. Ayniqsa, C++ kabi kuchli va samarador dasturlash tilida rekursiyani
to‘g‘ri qo‘llash, murakkab masalalarni ixcham, tushunarli va samarali tarzda hal
qilish imkonini beradi. Shu sababli, rekursiyani chuqur o‘rganish va uni real
dasturiy muhitda tatbiq etish hozirgi IT sohasi ehtiyojlari bilan bevosita bog‘liq
bo‘lib, kurs ishining dolzarbligini belgilaydi.
Kurs ishining maqsadi
Ushbu kurs ishining asosiy maqsadi – C++ dasturlash tilida rekursiya
tushunchasini nazariy va amaliy jihatdan chuqur o‘rganish, rekursiv
algoritmlarning ishlash prinsiplarini tahlil qilish hamda ularni real dasturiy
masalalarga tadbiq etish bo‘yicha mukammal bilim va ko‘nikmalarni
shakllantirishdir.
Kurs ishining obyekti
Mazkur kurs ishining obyekti – rekursiv funksiyalar va ularning C++ tilidagi
amalga oshirilishi hisoblanadi. Bu funksiyalar yordamida yechiladigan algoritmik
muammolar, xususan, daraxtlar, matematik hisob-kitoblar va kombinatorik
masalalardir.
Kurs ishining predmeti
3

Kurs ishining predmeti – rekursiv algoritmlarning tuzilishi, ishlash
mexanizmi, samaradorligi va optimallashtirish usullaridir. Shuningdek,
rekursiyaning iteratsiyadan farqlari, uning afzalliklari va cheklovlari, xotira
boshqaruvi va funksiya chaqiruvlarining ichki tuzilmasi ham predmet doirasiga
kiradi.
Kurs ishining vazifalari
1. Rekursiyaning nazariy asoslarini tahlil qilish;
2. C++ tilida rekursiv funksiyalarni yozish uslublarini o‘rganish;
3. Klassik rekursiv masalalar (faktorial, Fibonachchi, Evklid algoritmi,
Hanoi minoralari)ni tahlil qilish va ularning dasturiy yechimlarini ishlab chiqish;
4. Rekursiv algoritmlarning samaradorligini baholash va ularni
optimallashtirish yo‘llarini aniqlash;
5. Rekursiyaning real dasturiy muammolardagi qo‘llanilishini amaliy
misollar orqali yoritish;
6.Rekursiv funksiyalarning noto‘g‘ri ishlatilishi oqibatida yuzaga keladigan
muammolarni aniqlash va ularni bartaraf etish usullarini ko‘rsatish;
7. Yakunda o‘zlashtirilgan bilimlar asosida umumiy xulosa chiqarish va
tavsiyalar berish.
Rekursiyaning mohiyati – bu funksiya o‘zini o‘zi chaqirishi orqali
muammoni bosqichma-bosqich soddalashtirib, nihoyat yechimga olib kelishidir.
Bu yondashuv, ayniqsa, murakkab tuzilmalarga ega masalalarda, masalan,
daraxtlar, graflar, kombinatorik hisoblardagi hisob-kitoblar yoki matematik ketma-
ketliklarni tuzishda nihoyatda foydalidir. Oddiy ifoda bilan aytganda, rekursiv
funksiyalar muammoni kichik bo‘laklarga bo‘lib, har bir bo‘lakni yechish orqali
umumiy yechimga erishadi.
Rekursiv algoritmlarning samaradorligi ularning algoritmik tuzilmasi va
takrorlanuvchi jarayonlarga bo‘lgan tabiiy moslashuvi bilan bog‘liq. Ayniqsa,
rekursiya orqali factorial, Fibonachchi sonlari, Evklid algoritmi, Hanoi minoralari
kabi klassik masalalar juda ixcham va tushunarli shaklda yechiladi. Bunday
algoritmlar an’anaviy (iterativ) yondashuvlarga nisbatan kod jihatdan qisqaroq
4

bo‘lsa-da, noto‘g‘ri ishlatilganda samaradorlik va xotira sarfi bilan bog‘liq
muammolar yuzaga kelishi mumkin. Shu sababli, rekursiyani to‘g‘ri ishlatish
uchun uning nazariy asoslarini chuqur o‘rganish, amaliy mashqlar bilan
mustahkamlash va optimallik tamoyillarini tushunish lozim bo‘ladi.
Rekursiyaga oid masalalar nafaqat dasturlash asoslarini o‘rganishda, balki
dasturiy ta’minotni loyihalash, algoritmik fikrlashni rivojlantirish, funksional
dasturlash paradigmasini o‘zlashtirishda ham muhim o‘rin tutadi. Shu sababli,
rekursiya bugungi kunda faqat nazariy tushuncha emas, balki real dunyodagi
amaliy muammolarni hal qilishda keng qo‘llaniladigan kuchli vosita sifatida e’tirof
etiladi.
Ushbu kurs ishida rekursiyaning asosiy tushunchalari, algoritmik asoslari va
amaliy qo‘llanilishiga oid turli xil masalalar tahlil qilinadi. Har bir bobda
rekursiyaning nazariy jihatlari, dasturlashdagi yondashuvlar, real hayotdagi
dasturiy misollar asosida rekursiv yechimlar yoritiladi. Bundan tashqari, rekursiv
algoritmlarning samaradorligi, ularni testlash, muammolarni aniqlash va ularni
optimallashtirish yo‘llari ham muhokama qilinadi. Kurs ishi yakunida rekursiya
bilan bog‘liq o‘zlashtirilgan bilimlar umumlashtirilib, ularning dasturlashdagi
ahamiyati haqida xulosa chiqariladi.
Rekursiyaning chuqur mohiyatini anglash va uni real dasturlarda qo‘llay
olish nafaqat nazariy bilimlarni, balki amaliy ko‘nikmalarni ham shakllantiradi.
Shu bois, rekursiya mavzusi C++ dasturlash tili doirasida o‘rganilishi lozim
bo‘lgan eng muhim mavzulardan biridir.
5

I BOB. REKURSIYA VA UNING NAZARIY ASOSLARI
1.1. Rekursiya tushunchasi va dasturlashdagi o‘rni
Rekursiya bu — muammoni o‘zining oddiyroq holatlari orqali hal qilishga
asoslangan yondashuv bo‘lib, bu jarayonda funksiya o‘zini o‘zi chaqiradi. Bu
g‘oya dastlab matematikada rekurrent formulalar orqali qo‘llanilgan, lekin
zamonaviy dasturlash tillarining rivojlanishi bilan, xususan C++, Python, Java va
boshqa yuqori darajadagi tillarda keng joriy etildi. Rekursiya dasturlashning eng
kuchli vositalaridan biri bo‘lib, ayniqsa, strukturalangan va modullashtirilgan
dasturlashda muhim rol o‘ynaydi.
Rekursiyaning mohiyati shundan iboratki, har qanday muammo o‘zining
kichikroq yoki sodda ko‘rinishlariga ajratiladi, va ushbu kichik muammolar yana
aynan shu metod asosida hal qilinadi. Bu usul oddiy va intuitiv yondashuv bo‘lib,
ko‘plab algoritmlarni sodda shaklda ifodalashga imkon beradi. Masalan, faktorialni
hisoblashda n! = n * (n-1)! formulasi yordamida biz n qiymatiga ega faktorialni n-
1, n-2, ... 1 qiymatlar orqali rekursiv tarzda hisoblaymiz.
Rekursiyaning dasturlashdagi afzalliklari ko‘p. Avvalo, kod yozilishi ancha
qisqaradi va tushunarliroq bo‘ladi. Shuningdek, ba’zi murakkab algoritmlar,
masalan, daraxt tuzilmalarida qidiruv (DFS), Fayl tizimlarida kataloglar orqali
yurish, matematik kombinatsiyalar, Hanoi minorasi, Fibonachchi sonlari kabi
masalalarni rekursiyasiz yechish ancha murakkab va chalkash bo‘lishi mumkin.
Rekursiya bu muammolarning echimini sodda, strukturaviy va modullashtirilgan
tarzda berishga imkon yaratadi.
Ammo rekursiv funksiyalarni yozishda juda muhim jihatlardan biri bu asosiy
holat (base case) ni aniq belgilashdir. Har qanday rekursiv funksiya to‘xtovsiz
ishlamasligi, ya’ni bir nuqtada to‘xtab, qaytishni boshlashi kerak. Agar asosiy
holat noto‘g‘ri yoki umuman ko‘rsatilmasa, funksiya o‘zini cheksiz chaqirishda
davom etadi va bu xotira to‘lib ketishiga, ya’ni stack overflow xatosiga olib keladi.
Shu sababli rekursiyani yozishda mantiqiy fikrlash, funksiyaning chaqirilish zanjiri
va uning to‘xtash shartini aniq belgilash talab etiladi.
6

Rekursiya turli xil shakllarda bo‘lishi mumkin. Eng oddiy holati bu birlik
rekursiya bo‘lib, bunda funksiya o‘zini bitta marta chaqiradi. Shuningdek, ko‘p
martalik rekursiya ham mavjud bo‘lib, bunda funksiya bir necha bor o‘zini o‘zi
chaqiradi, masalan, Fibonachchi sonlarini hisoblovchi algoritmda bo‘lgani kabi.
Bunday hollarda funksiyaning chaqiruv daraxti eksponenta bo‘yicha o‘sadi va
samarali ishlash uchun memoizatsiya yoki dinamik dasturlash yondashuvlaridan
foydalaniladi.
C++ dasturlash tilida rekursiv funksiyalarni yaratish sintaksisi juda qulay.
Funktsiya nomi o‘z ichida qayta chaqiriladi va shartli operatorlar orqali asosiy
holat belgilanadi. Misol uchun:
int factorial(int n) {
if (n == 0 || n == 1)
return 1;
else
return n * factorial(n - 1);
}
Ushbu oddiy kod rekursiyaning qanday ishlashini aniq ko‘rsatadi: har bir n
qiymatida funksiya o‘zini n-1 qiymati bilan chaqiradi va bu zanjir n = 1 bo‘lganida
to‘xtaydi.
Rekursiyaning dasturlashdagi o‘rni shunchalik muhimki, ko‘plab oliy
matematik konsepsiyalarni dasturlashga tadbiq etishda aynan rekursiya vositasi
ishlatiladi. Grafik algoritmlar, sun’iy intellektdagi qaror daraxtlari, chuqurlik
bo‘yicha qidiruv (DFS), o‘yinlar yaratishdagi harakatlar kombinatsiyasi —
bularning barchasi rekursiv model asosida tuziladi.
Shuni alohida ta’kidlash kerakki, rekursiyani noto‘g‘ri tushunish va noto‘g‘ri
qo‘llash ko‘plab funksional xatolarga, samarasizlikka olib keladi. Shu bois,
rekursiyani o‘rganish faqat sintaktik darajada emas, balki mantiqiy va algoritmik
tafakkur asosida chuqur o‘zlashtirilishi lozim. Dasturchi rekursiv funksiyaning har
bir chaqiruvini tasavvur qilish, stackda qanday kontekstlar hosil bo‘layotganini
tushunish va yakuniy natijani qanday yig‘ish kerakligini bilishi zarur.
7

Xulosa qilib aytganda, rekursiya bu — o‘zida matematika, algoritmika va
dasturlash estetikasi uyg‘unlashgan g‘oyadir. Uning chuqur mohiyatini
o‘zlashtirish orqali nafaqat samarali dasturlar yaratish, balki muammoni yechish
ko‘nikmasini yanada takomillashtirish, algoritmik tafakkurni shakllantirish va
dasturlash madaniyatini rivojlantirish mumkin.
1.2. Rekursiv funksiyalarning ishlash mexanizmi va xotira bilan ishlash
jarayoni
Rekursiv funksiyalarning ishlash tamoyili dasturlashda chuqur tushunchani
talab qiladi, chunki bu usulda yozilgan kodning bajarilishi davomida har bir
funksiyaning yangi nusxasi chaqiriladi va bu jarayon chuqur chuqurlashib ketishi
mumkin. Har safar rekursiv funksiya o‘zini chaqirganida, avvalgi chaqiruv
to‘xtatiladi va yangi chaqiruv xotiraning stek (stack) deb nomlanuvchi maxsus
hududiga joylashtiriladi. Stack bu yerda vaqtinchalik ma’lumotlarni, ya’ni
parametrlar, lokal o‘zgaruvchilar va qaytish manzilini saqlab turadi. Bu jarayon
stack frame deb ataladi. Har bir rekursiv chaqiruv yangi stack frame hosil qiladi va
bu xotirada o‘zining joyini egallaydi.
Bu mexanizmning samarali ishlashi uchun rekursiyaning to‘xtash sharti
bo‘lishi muhimdir. Aks holda, cheksiz rekursiv chaqiruvlar stack overflow
xatoligiga olib keladi, ya’ni xotira tugab, dastur to‘xtab qoladi. Shu sababli
rekursiv algoritmlar yozilayotganda bazaviy holat (base case) va rekursiv holat
(recursive case) aniq va to‘g‘ri belgilanishi zarur.
Oddiy misol tariqasida faktorial funksiyasini olaylik. Masalan, n! = n * (n-
1)! deb aniqlanadi va bunda 1! = 1 yoki 0! = 1 bazaviy holat sifatida qabul qilinadi.
Dastur ishlayotganda, faktorial(5) funksiyasi chaqirilsa, avval faktorial(4)
chaqiriladi, so‘ng faktorial(3), shuningdek bu jarayon faktorial(0)ga yetguncha
davom etadi. Har bir chaqiruvning natijasi xotirada saqlanadi va faktorial(0)
natijasi topilgach, dastur stack bo‘ylab orqaga qaytib, oldingi chaqiruvlar natijasini
hisoblab chiqadi.
8

Rekursiya kompyuter xotirasi bilan bevosita bog‘liq bo‘lganligi sababli,
funksiyaning har bir chaqiruv bosqichi RAMning stek qismida joylashadi. Bu
joyda har bir funksiyaga alohida joy ajratiladi. Bu holatda har bir chaqiruv o‘zining
muhitini va o‘zgaruvchilarini saqlaydi. Bu orqali har bir chaqiruv yakunlanganidan
so‘ng, uning natijasi oldingi chaqiruvga uzatiladi va shu tarzda butun hisoblash
yakunlanadi.
Rekursiv funksiyalarning afzalliklari ko‘p, ularning eng muhim jihatlaridan
biri bu kodning soddaligi va tushunarli ifodalanishidir. Masalan, ko‘p sonli ichma-
ich takrorlanuvchi jarayonlarni iterativ usulda ifodalash murakkab va chalkash
bo‘lishi mumkin, ammo rekursiv yondashuv yordamida bu holatni ancha
soddalashtirish mumkin bo‘ladi. Biroq bu bilan birga, xotira sarfi va ishlash
samaradorligini ham hisobga olish lozim. Ba’zida rekursiv yondashuv kompyuter
resurslarini ko‘p talab qilishi mumkin, ayniqsa optimallashtirilmagan holatlarda.
Rekursiv funksiyalar bilan ishlashda yana bir muhim omil bu tail recursion
(quyruq rekursiyasi) tushunchasidir. Agar rekursiv chaqiruv funksiyaning oxirida
joylashgan bo‘lsa va undan so‘ng hech qanday amal bajarilmasa, bu tail recursion
hisoblanadi. Ko‘pgina zamonaviy kompilyatorlar tail recursion optimizatsiyasini
amalga oshira oladi va bu holatda stekda yangi frame ajratish o‘rniga mavjud
frame qayta ishlatiladi. Bu esa xotira sarfini kamaytiradi va ishlash tezligini
oshiradi.
Shuningdek, memoizatsiya (natijalarni keshga saqlab borish) kabi
yondashuvlar yordamida rekursiv algoritmlarning samaradorligini oshirish
mumkin. Bu usul ayniqsa dinamik dasturlashda qo‘llaniladi, bunda takroran
hisoblangan natijalar saqlanib qoladi va kerak bo‘lganda takror hisoblanmaydi.
Umuman olganda, rekursiv funksiyalarning ishlash mexanizmi bir qarashda
oddiydek tuyulgan bo‘lsa-da, u chuqur tahlil va ehtiyotkorlikni talab qiladigan
muhim va murakkab yo‘nalish hisoblanadi. Har bir rekursiv funksiya
yozilayotganda uning xotira bilan qanday ishlashi, stekda qanday joylashishi,
to‘xtash shartlari va optimallashtirish imkoniyatlari puxta o‘ylab chiqilishi zarur.
Aks holda, dasturning ishlashi sekinlashishi yoki umuman to‘xtab qolish xavfi
9

tug‘iladi. Shu sababli, rekursiyani nafaqat yozish, balki uni samarali tashkil etish
ham dasturchining muhim ko‘nikmalaridan biri hisoblanadi.
1.3. Rekursiyaning afzalliklari va kamchiliklari
Rekursiya dasturlashning kuchli vositalaridan biri bo‘lib, ko‘plab
algoritmlarni soddalashtirish va ularni intuitiv tarzda ifodalash imkonini beradi.
Ayniqsa, murakkab daraxt tuzilmalari, grafiklar, matematik masalalar va
takrorlanuvchi jarayonlarni tasvirlashda rekursiyaning o‘rni beqiyosdir. Ammo bu
yondashuv faqatgina afzalliklardan iborat emas, u bilan birga ayrim cheklovlar va
kamchiliklarni ham olib keladi. Shu bois, har qanday rekursiv yechim
yozilayotganda uning qulayliklari va xavf-xatarlari puxta baholab chiqilishi zarur.
Rekursiyaning birinchi va eng muhim afzalligi — kodning soddaligi.
Masalan, Fibonacci sonlarini hisoblash, faktorial funksiyasi, binar qidiruv,
daraxtlar bo‘yicha yurishlar kabi ko‘plab algoritmlar iterativ yondashuvga
qaraganda rekursiv tarzda ancha ixcham va tushunarli yoziladi. Bu, ayniqsa, yangi
boshlovchi dasturchilar uchun muhim bo‘lib, ular murakkab strukturaviy
muammolarni soddalashtirilgan ko‘rinishda tushunib olishlari mumkin.
Yana bir muhim afzallik — murakkab masalalarni kichikroq bo‘laklarga
ajratish imkoniyati. Rekursiv funksiyalar orqali katta masalani rekursiv tarzda
takroran kichik masalalarga bo‘lib, har birini alohida yechish mumkin. Bu
yondashuv, ayniqsa, divide and conquer (bo‘lib va yeng) strategiyasiga asoslangan
algoritmlarda (masalan, merge sort, quick sort, binary search) keng qo‘llaniladi.
Shuningdek, rekursiya orqali ma’lumot tuzilmalarini tabiiy shaklda bosib
chiqish yoki qayta ishlash ham osonlashadi. Masalan, fayllar sistemasi, HTML
hujjatlar, yoki daraxt ko‘rinishidagi mantiqiy strukturalarda rekursiv algoritmlar
juda samarali hisoblanadi. Har bir tugunni (node) qayta chaqirish orqali daraxt
yoki grafikning barcha elementlari tahlil qilinadi.
Biroq rekursiyaning bu qulay jihatlari bilan bir qatorda bir qancha
kamchiliklari ham mavjud. Ulardan birinchisi — xotira sarfi va hisoblash
samaradorligining pastligi. Har safar funksiya o‘zini qayta chaqirganda, xotirada
10

yangi stack frame ajratiladi va bu holat stack overflow (ya’ni stack to‘lganligi
sababli xatolik) xavfini tug‘diradi. Ayniqsa, katta sonlar bilan ishlovchi rekursiv
funksiya kerakli optimallashtirishlarsiz yozilgan bo‘lsa, u tezda kompyuter
xotirasini to‘ldiradi va ishni to‘xtatadi.
Shuningdek, ba’zi rekursiv yondashuvlar o‘z-o‘zidan sekin ishlaydi.
Masalan, oddiy Fibonacci sonlarini rekursiv tarzda hisoblashda, bir xil qiymatlar
bir necha marta hisoblanadi, bu esa ortiqcha vaqt sarfiga olib keladi. Bu kabi
holatlarda memoizatsiya yoki dinamik dasturlash kabi yondashuvlar kerak bo‘ladi.
Aks holda, har bir yangi chaqiruv avvalgilarni takrorlaydi va bu esa eksponentsial
darajada sekinlikka olib keladi.
Yana bir kamchilik — rekursiv yechimlarni debug (nosozliklarni aniqlash)
qilish nisbatan qiyin. Ayniqsa, chuqur rekursiv funksiyalarda chaqiruvlar zanjiri
juda murakkab bo‘lishi mumkin va bu holatda xatolikni topish uchun har bir
bosqichni alohida tahlil qilish kerak bo‘ladi. Bu esa ko‘p vaqt va diqqat talab etadi.
Shu bilan birga, barcha masalalar uchun rekursiya eng yaxshi yechim emas.
Ayrim hollarda iteratsion (takroriy) yondashuv ancha samarali, xotira tejamkor va
tez ishlovchi bo‘lishi mumkin. Misol uchun, katta sikllar va aniq sonli
takrorlanishlar bilan bog‘liq masalalarda oddiy for yoki while sikllari rekursiyaga
qaraganda samaraliroq bo‘lishi mumkin.
Xulosa qilib aytganda, rekursiya kuchli vosita bo‘lishi bilan birga, undan
to‘g‘ri foydalanishni talab etadi. Har bir masala uchun rekursiv yechim taklif
qilishdan avval, uning afzallik va kamchiliklarini, xotira sarfini, ishlash tezligini va
algoritmning umumiy murakkabligini tahlil qilish zarur. Agar rekursiya
optimallashtirilgan, to‘g‘ri cheklovlar bilan yozilgan bo‘lsa, u holda u nafaqat
samarali, balki juda estetik jihatdan chiroyli va mukammal yechimlar taqdim eta
oladi. Shu bois rekursiyani o‘rganish va undan maqsadli foydalanish zamonaviy
dasturchilar uchun muhim ko‘nikmalardan biri hisoblanadi.
11

II BOB. REKURSIV FUNKSIYALAR VA ULARNING
DASTURLASHDAGI QO‘LLANILISHI
2.1. Rekursiv funksiyalarni yaratish va ularning ishlash prinsiplari
Rekursiv funksiyalar — bu o‘zining tanasida o‘zini chaqiradigan
funksiyalardir. Bunday funksiyalar orqali murakkab masalalarni oddiy qismlarga
ajratish va har bir qismini alohida hal qilish mumkin bo‘ladi. Rekursiyaning asosiy
g‘oyasi — har qanday murakkab masalani o‘xshash, ammo kichikroq versiyalarga
ajratish orqali yechimga erishishdir. Bunda dastur har bir kichik vazifani bajarib
bo‘lgach, ularni qayta birlashtirib, umumiy yechim hosil qiladi.
Rekursiv funksiyani yaratishda asosiy ikki muhim jihatga e’tibor qaratish
lozim: bu asosiy holat (base case) va rekursiv chaqiruv (recursive call). Asosiy
holat — bu funksiyaning rekursiyadan chiqadigan shartidir. U holda, funksiya
boshqa o‘zini chaqirmaydi, balki to‘xtaydi va natijani qaytaradi. Rekursiv chaqiruv
esa funksiyaning o‘zini chaqirish qismi bo‘lib, har gal masalaning bir oz
soddalashtirilgan ko‘rinishi bilan ishlaydi.
Quyidagi oddiy misolni ko‘rib chiqamiz — faktorialni hisoblash. Faktorial
— bu natural sonlarning 1 dan shu songacha bo‘lgan ko‘paytmasi:
int faktorial(int n) {
if (n == 0 || n == 1)
return 1;
else
return n * faktorial(n - 1);
}
Ushbu funksiyada n == 0 || n == 1 asosiy holat bo‘lib xizmat qiladi. Bu shart
bajarilganda rekursiya to‘xtaydi. Aks holda, funksiya o‘zini n - 1 qiymati bilan
yana chaqiradi. Har bir chaqiruv o‘zining javobini kutadi va bu javoblar
funksiyadan funksiyaga qaytib kelib, umumiy natijani hosil qiladi. Shunday qilib,
faktorial(5) chaqiruvining bajarilishi quyidagicha bo‘ladi:
faktorial(5)
= 5 * faktorial(4)
12

= 5 * 4 * faktorial(3)
= 5 * 4 * 3 * faktorial(2)
= 5 * 4 * 3 * 2 * faktorial(1)
= 5 * 4 * 3 * 2 * 1 = 120
Bu kabi funksiyalar oddiy ko‘rinishdagi rekursiyalardir. Bunday rekursiv
funksiyalar chiziqli rekursiyalar deb ataladi. Unda faqat bitta rekursiv chaqiruv
mavjud bo‘ladi.
Yana bir muhim tur — ikki tomonlama rekursiya bo‘lib, bunda funksiya
o‘zini ikkita yoki undan ortiq marta chaqiradi. Masalan, Fibonacci sonlarini
hisoblashda:
int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Bu yondashuvda har bir qiymat hisoblanishi uchun ikkita oldingi qiymat
kerak bo‘ladi. Natijada chaqiruvlar soni eksponentsial darajada ortib ketadi. Bu esa
ortiqcha hisob-kitoblarni keltirib chiqaradi. Bunday holatlarda memoizatsiya (ya’ni
hisoblangan qiymatlarni eslab qolish) yoki dinamik dasturlash yordamida
samaradorlikni oshirish mumkin.
Rekursiv funksiyalarni yaratishda e’tibor beriladigan yana bir muhim jihat
— cheklovlar va xatoliklar ehtimoli. Agar asosiy holat noto‘g‘ri yoki umuman
ko‘rsatilmasa, funksiya doimiy o‘zini chaqirib, stack overflow xatoligiga olib
kelishi mumkin. Stack overflow — bu kompyuter xotirasining maxsus qismini
(stack) haddan tashqari to‘ldirib yuborish natijasida yuzaga keladigan xatodir. Shu
bois har bir rekursiv funksiya aniq va ishonchli asosiy holatga ega bo‘lishi shart.
Rekursiv funksiyalar dasturchilardan aniq mantiqiy tafakkur va strukturaviy
fikrlashni talab qiladi. Har bir chaqiruvning qanday natija qaytarishini va bu
natijalar qanday qilib umumiy yechimga ta’sir qilishini tushunib olish muhimdir.
13

Bunday funksiyalar ayniqsa daraxtlar, grafiklar, kombinatorika, matematik
funksiyalar, qidiruv va saralash algoritmlarida keng qo‘llaniladi.
Shu bilan birga, zamonaviy dasturlash tillarining ko‘pchiligi (xususan C++,
Python, Java va boshqalar) rekursiyani samarali qo‘llab-quvvatlaydi. Ular orqali
hatto eng murakkab rekursiv algoritmlar ham tushunarli va aniq ifodalangan holda
yozilishi mumkin.
Umuman olganda, rekursiv funksiyalar dasturlashda yuqori darajadagi
konseptual vosita bo‘lib, u orqali ko‘plab murakkab muammolarni oddiy va
tushunarli shaklda ifodalash mumkin. Ularning to‘g‘ri tuzilishi, asosiy holat bilan
ta’minlanishi va optimallashtirilgan ishlashi muhim ahamiyatga ega. Rekursiyani
o‘rganish — bu nafaqat yangi algoritmik yondashuvni o‘zlashtirish, balki
dasturchilik tafakkurini chuqurlashtirish vositasi hamdir.
2.2. Rekursiyaning algoritmik yechimlardagi afzalliklari va cheklovlari
Rekursiya — bu algoritmik fikrlashda qulaylik va tabiiylikni ta’minlovchi
kuchli vositadir. Murakkab muammolarni soddalashtirish, takroriy tuzilmalarni
izchil yoritish, murakkab daraxtsimon yoki grafik tuzilmalar bilan ishlashda
rekursiv yondashuv juda foydalidir. Biroq, uni to‘g‘ri va samarali qo‘llash uchun,
uning afzalliklari bilan bir qatorda, cheklovlarini ham chuqur anglash zarur.
Rekursiyaning eng katta afzalliklaridan biri bu — murakkab
muammolarning soddalashtirilgan ifodasidir. Masalan, matematik formulalarda
mavjud bo‘lgan rekursiv tuzilmalarni dasturga to‘g‘ridan-to‘g‘ri ko‘chirish
mumkin bo‘ladi. Fibonacci sonlari, faktorial, binar daraxtlarni o‘rganish, grafik
bo‘ylab qidiruv kabi masalalar rekursiya orqali juda ixcham va tushunarli tarzda
ifodalanadi. Natijada kod uzunligi kamayadi, o‘qilishi osonlashadi va texnik
yondashuvlar o‘zining matematik asliga yaqinlashadi.
Yana bir muhim afzalligi bu — takroriy strukturani avtomatik tashkil etish.
Dasturchi har bir sathni alohida boshqarmaydi, balki umumiy shablonni yaratadi.
Har bir rekursiv chaqiruv avtomatik tarzda o‘zining yangi konteksti bilan amalga
14

oshadi. Bu esa masalaning har bir sathini alohida e’tiborga olish zaruratini bartaraf
etadi.
Rekursiya yordamida yig‘iluvchi strukturalar (masalan, massivlar,
ro‘yxatlar, daraxtlar) ustida ko‘plab foydali amallar bajarish mumkin: chuqurlik
bo‘yicha o‘tish, teskari tartibda chiqarish, bo‘shliqlarni to‘ldirish va hokazo.
Ayniqsa qidiruv va saralash algoritmlarida rekursiv metodlar samarali ishlaydi.
Masalan, Merge Sort, Quick Sort kabi algoritmlar rekursiv tuzilgan bo‘lib, katta
massivlarni kichik qismlarga ajratib, ularni tartiblab, qayta birlashtirish orqali
ishlaydi.
Biroq rekursiyaning afzalliklari bilan bir qatorda cheklovlari va
kamchiliklari ham mavjud. Eng asosiy kamchilik — bu xotira sarfi. Har bir
rekursiv chaqiruv chaqiruvlar stekiga (stack memory) joylashtiriladi. Har bir yangi
chaqiruv yangi kontekstda, alohida xotira maydonida saqlanadi. Bu esa rekursiya
chuqur bo‘lganda yoki juda ko‘p sonli chaqiruvlar bo‘lsa, stekning to‘lib ketishiga
olib keladi. Bu holatda dasturda stack overflow (xotira toshishi) xatoligi yuzaga
keladi.
Shu sababli, rekursiyani ishlatishda asosiy holat (base case) mavjudligiga
ishonch hosil qilish zarur. Asosiy holatsiz yoki noto‘g‘ri asosiy holat bilan
yozilgan rekursiv funksiyalar cheksiz qayta chaqiruvga olib keladi va dastur
ishlamay qoladi. Bu holatlar ko‘pincha dasturchilar tomonidan eng ko‘p yo‘l
qo‘yiladigan xatolardan biridir.
Yana bir muammo — rekursiv funksiyalarning samaradorlik darajasi past
bo‘lishi mumkin. Masalan, oddiy rekursiv yondashuv bilan Fibonacci sonlarini
hisoblashda har bir qiymat ko‘p marta qayta hisoblanadi. Bu esa eksponentsial vaqt
sarfiga olib keladi. Shuning uchun, rekursiyani qo‘llashda memoizatsiya (oldingi
natijalarni saqlab qo‘yish) yoki dinamik dasturlash texnikalari bilan birgalikda
foydalanish tavsiya etiladi.
Rekursiyaning yana bir cheklovli tomoni bu — trassirovka va xatoni tuzatish
qiyinligi. Har bir rekursiv chaqiruv alohida kontekstda bajarilgani sababli, kodni
tahlil qilishda va xatoni aniqlashda oddiy iteratsion metodlarga qaraganda ko‘proq
15

e’tibor va aniqlik talab etiladi. Ayniqsa, murakkab rekursiv strukturalarda noto‘g‘ri
asosiy holat yoki noto‘g‘ri rekursiv chaqiruv butun algoritmning ishlashiga salbiy
ta’sir qilishi mumkin.
Shuningdek, rekursiv yondashuvlar barcha holatlar uchun optimal
bo‘lavermaydi. Ba’zi algoritmlarni iteratsion (takrorlovchi) metodlar bilan amalga
oshirish nafaqat samaraliroq, balki xotira jihatdan tejamkorroq ham bo‘ladi. Shu
bois, rekursiyani faqat zarur hollarda, murakkablikni kamaytirish yoki rekursiv
tuzilma mavjud bo‘lgan masalalarda qo‘llash maqsadga muvofiqdir.
Xulosa qilib aytganda, rekursiya — bu kuchli va qulay algoritmik vosita
bo‘lib, u orqali murakkab strukturalar soddalashtiriladi, kod qisqaradi va
matematik modelga yaqinlashtiriladi. Ammo undan foydalanishda texnik xatoliklar
ehtimoli yuqori bo‘lgani sababli, chuqur tahlil, to‘g‘ri shartlar, samaradorlik va
xotira sarfini hisobga olish muhimdir. Rekursiyani o‘zlashtirish orqali dasturchi
o‘zining algoritmik bilimlarini mustahkamlaydi, mantiqiy fikrlash doirasini
kengaytiradi va murakkab dasturiy loyihalarni muvaffaqiyatli amalga oshirishga
qodir bo‘ladi.
2.3. Rekursiya va iteratsiyaning solishtirmali tahlili
Rekursiya va iteratsiya — bu dasturlashda muammolarni hal qilishda keng
qo‘llaniladigan ikki asosiy yondashuv bo‘lib, ularning har biri o‘ziga xos
afzalliklari va kamchiliklariga ega. Ko‘plab muammolarni ham rekursiv, ham
iterativ usulda hal qilish mumkin, biroq ularning samaradorligi, tushunarliligi va
texnik imkoniyatlari muammoning tabiatiga bog‘liq. Shu bois ushbu bobda
rekursiya va iteratsiya o‘rtasidagi asosiy farqlar, o‘xshashliklar, ularning
qo‘llanilish holatlari va samaradorlik jihatidan tahlili batafsil ko‘rib chiqiladi.
Rekursiya — bu funksiyaning o‘zini o‘zi chaqirishi orqali yechimga
erishadigan usul bo‘lsa, iteratsiya — bu muammoni ketma-ket takrorlovchi sikllar
yordamida hal qiluvchi metoddir. Har ikki yondashuv takroriylik g‘oyasiga
asoslanadi, lekin ularning bajarilish mexanizmi tamoman boshqacha. Rekursiyada
16

har bir chaqiruv yangi stek ramkasida bajariladi, iteratsiyada esa bir xil kod bloki
ko‘p marta aylanadi.
Samaradorlik nuqtayi nazaridan qaralganda, iteratsiya odatda xotira jihatidan
tejamkorroqdir. Iteratsion usullarda ko‘pincha yagona sikl ishlatilgani sababli stack
xotirasi ortiqcha ishlatilmaydi, bu esa katta miqdordagi hisob-kitoblarda afzallik
beradi. Rekursiya esa, har bir funksiyani stekda alohida saqlagani sababli, chuqur
chaqiruvlarda tezda xotirani to‘ldirishi va “stack overflow”ga olib kelishi mumkin.
Ayniqsa, masalaning rekursiv yechimi chuqur bo‘lsa (masalan, binar daraxtda 10
000 dan ortiq tugunlar mavjud bo‘lsa), bu holat sezilarli darajada muammo
tug‘diradi.
Biroq rekursiya ko‘plab holatlarda kodning soddaligi va tushunarliligini
ta’minlaydi. Masalan, matematik formulalar orqali ifodalangan masalalarni
yozishda rekursiya muammoni bevosita model shaklida ifodalash imkonini beradi.
Fibonacci sonlari, faktorial, Tower of Hanoi muammosi, daraxt strukturalari bilan
ishlash — bularning barchasi rekursiya orqali juda aniq va ixcham ko‘rinishda
dasturlashtiriladi.
Iteratsiyaning asosiy ustunligi esa uning aniqligi va nazoratga osonligi bilan
bog‘liq. Har bir bosqichda aniq nima sodir bo‘layotgani ko‘rinadi, xatolikni
aniqlash va tuzatish oson bo‘ladi. Rekursiyada esa, ayniqsa murakkablik ortgani
sari, dastur oqimini tahlil qilish qiyinlashadi, ayniqsa xatolikni aniqlashda va qayta
chaqiruvlar ketma-ketligini tushunishda qiyinchiliklar yuzaga keladi.
Yana bir muhim jihat — dasturchining tajribasi va loyihani amalga
oshirishdagi talablar. Tajribali dasturchilar ko‘pincha rekursiyani samarali
qo‘llashni biladi, memoizatsiya, tail-recursion, va boshqa optimallashtirish
vositalari yordamida undan maksimal darajada foydalanadilar. Ammo
o‘rganayotganlar uchun iteratsion yondashuv odatda tushunarliroq va xavfsizroq
bo‘ladi.
Rekursiv va iterativ yondashuvlarning ayrim jihatlari quyidagicha
taqqoslanadi:
17

Mezon Rekursiya Iteratsiya
Kod soddaligi Oddiy va ixcham Ba’zan murakkab
Xotira sarfi Ko‘proq (stack ishlatiladi) Kamroq
Amalga oshirish osonligi Matematik ifodalarda qulay Oddiy jarayonlar
uchun qulay
Kengaytirilgan masalalar Ko‘p holatda tabiiy yechim Ba’zan murakkab
Tahlil va xatoni topish Qiyinroq Osonroq
Shuningdek, ba’zi zamonaviy dasturlash tillarida “tail-recursion
optimization” qo‘llaniladi. Bu usulda rekursiyaning oxirgi chaqiruvlari iteratsiya
kabi optimallashtiriladi va stackdan foydalanmasdan amalga oshiriladi. Ammo bu
imkoniyat barcha tillarda mavjud emas, masalan, C++ tilida bunday
optimallashtirish avtomatik tarzda qo‘llanilmaydi.
Shunday qilib, rekursiya va iteratsiyaning har biri o‘ziga xos vazifalarda
qo‘llanadi. Masalaning tuzilmasi, yechimga ketadigan vaqt va xotira, hamda
kodning o‘qilishi kabi omillarni hisobga olgan holda qaysi yondashuv samaraliroq
ekanini tanlash zarur. Umuman olganda, rekursiya — nazariy soddalik va amaliy
qulaylik, iteratsiya esa amaliy samaradorlik va xotira tejamkorligi tarafdori
hisoblanadi. Har ikki yondashuvni mukammal bilish dasturchining imkoniyatlarini
kengaytiradi, kod sifatini oshiradi va turli xil murakkab masalalarni hal qilishda
moslashuvchanlikni ta’minlaydi.
18

III BOB. REKURSIYADAN AMALIY FOYDALANISH VA
MASALALARNI YECHISH ALGORITMLARI
3.1. Rekursiya asosida masalalarni yechishning umumiy yondashuvi
Rekursiv yondashuv dasturlashda turli murakkab masalalarning yechimini
soddalashtirishda muhim vosita hisoblanadi. Ushbu bobning ushbu bo‘limida
rekursiya yordamida masalalarni qanday tahlil qilish, ularga umumiy algoritmik
yondashuvni qanday shakllantirish mumkinligi keng ko‘lamda ko‘rib chiqiladi.
Rekursiv algoritmni ishlab chiqish uchun quyidagi bosqichlarni
aniqlashtirish juda muhim:
1. Bazaviy holat (base case) — bu rekursiyani to‘xtatadigan shart bo‘lib,
unga yetilganda rekursiv chaqiruvlar tugaydi. Bazaviy holat to‘g‘ri tanlanmasa,
algoritm “infinite recursion”ga tushadi, ya’ni cheksiz o‘z-o‘zini chaqirish
jarayoniga kirib qoladi. Har bir rekursiv funksiyada, avvalo, bazaviy holat mavjud
bo‘lishi shart.
2. Qayta chaqirish qoidasi (recursive case) — bu muammoni kichikroq
bo‘laklarga ajratib, har birini rekursiv tarzda yechish jarayonidir. Bu qoidaning
to‘g‘ri tuzilishi natijasida muammo har safar soddalashib boradi va oxir-oqibatda
bazaviy holatga yetadi.
3. Funktsiyaning shartli strukturasi — rekursiv funktsiyalar odatda if-else,
switch, yoki boshqa shart operatorlari yordamida yoziladi. Shartli tuzilmalar
muammoni bazaviy holat va rekursiv holatga ajratishda qulaylik yaratadi.
Masalan, rekursiv tarzda faktorial funksiyasini quyidagicha ifodalash
mumkin:
int factorial(int n) {
if (n == 0 || n == 1) return 1; // Bazaviy holat
else return n * factorial(n - 1); // Rekursiv chaqiruv
}
Bu yerda n == 0 va n == 1 bazaviy holatlar bo‘lib, ular faktorialning
qiymatini bevosita qaytaradi. Aks holda, funksiya o‘zini n-1 qiymat bilan yana
chaqiradi.
19

Rekursiya asosidagi masalalarga yondashishda yana bir muhim jihat — bu
algoritmning to‘xtalishiga ishonch hosil qilish. Har bir rekursiv chaqiruv avvalgi
chaqiruvga nisbatan kichikroq yoki soddaroq muammoni yechishi lozim. Aks
holda, rekursiv funksiya hech qachon bazaviy holatga yetmaydi va dastur ish
faoliyatidan to‘xtaydi.
Rekursiya yondashuvi ba’zi strukturalar, ayniqsa daraxtlar, graf tarmoqlari,
kombinatorika masalalari, matematik ketma-ketliklar, va qidiruv algoritmlarida
ayniqsa foydali. Misol uchun, binar daraxtdagi tugunlar sonini hisoblash, barcha
tugunlarni aylanib chiqish (traversal), qismlarga bo‘lish asosidagi muammolar
(masalan, merge sort), va orqaga qadam (backtracking) algoritmlarining
ko‘pchiligi rekursiyaga asoslanadi.
Backtracking — bu rekursiyaning bir ko‘rinishi bo‘lib, unda har bir
bosqichda ehtimoliy variantlar sinab ko‘riladi, agar noto‘g‘ri yo‘l tanlansa, oldingi
nuqtaga qaytiladi. Bunday uslub, masalan, shaxmatdagi yurishlarni tahlil qilish,
Sudoku yechish, labirintdan chiqish yo‘lini topish kabi muammolarda keng
qo‘llaniladi.
Rekursiv algoritm yaratishda muhim bosqichlar quyidagilar:
Muammoni soddaroq kichik qismlarga ajratish mumkinmi?
Har bir kichik muammo asl muammo bilan bir xil turga kiradimi?
Kichik muammo natijasidan umumiy natijani qanday olish mumkin?
Bazaviy holat qachon va qanday bo‘ladi?
Ushbu savollarga aniq javob topa olish, masalaning rekursiv modelini
shakllantirishda asosiy omildir. Bu savollar yordamida masalaning ichki tuzilmasi
aniqlanadi va algoritmik yechim shakllanadi.
Shunday qilib, rekursiya asosida masalalarni yechish muammoni matematik
jihatdan chuqur tahlil qilish, uni oddiylashtirish va bu oddiy qismlarni rekursiv
chaqiruvlar orqali hal qilishga asoslanadi. Ushbu yondashuv, zamonaviy
algoritmlarni ishlab chiqishda keng qo‘llanilmoqda va bu sohada samarali ishlash
uchun uni puxta o‘zlashtirish talab etiladi. Keyingi bo‘limlarda rekursiya asosida
echiladigan real masalalar va algoritmlarni batafsil tahlil qilamiz.
20

3.2. Rekursiya yordamida matematik va algoritmik masalalarni yechish
usullari
Rekursiya dasturlashda eng samarali va qulay yondashuvlardan biri
hisoblanadi, ayniqsa matematik va algoritmik xarakterga ega bo‘lgan masalalarni
yechishda. Ushbu bo‘limda biz rekursiv funksiyalardan foydalanib qanday qilib
turli xil matematik va algoritmik muammolarni hal qilish mumkinligi haqida
batafsil to‘xtalib o‘tamiz. Bu masalalar nafaqat nazariy, balki amaliy dasturlashda
ham keng qo‘llaniladi.
Rekursiya orqali yechiladigan eng oddiy matematik masalalardan biri bu
faktorial funksiyasi hisoblanadi. Avvalgi bobda ushbu funksiyaning rekursiv
ifodasi ko‘rib chiqilgan edi. Quyida boshqa muhim masalalar — Fibonacci sonlari,
binomial koeffitsientlar, Evklid algoritmi, va kombinatsion muammolar tahlil
qilinadi.
Fibonacci sonlari
Fibonacci sonlari ketma-ketligi quyidagi rekursiv formulaga asoslangan:
F(n) = F(n-1) + F(n-2),
F(0) = 0,
F(1) = 1.
Rekursiv funksiyasi quyidagicha yoziladi:
int fibonacci(int n) {
if (n == 0) return 0;
else if (n == 1) return 1;
else return fibonacci(n - 1) + fibonacci(n - 2);
}
Bu funksiya to‘g‘ri ishlaydi, ammo har bir chaqiruvda ikki marta yangi
chaqiruv hosil qilinadi, bu esa eksponensial vaqt murakkabligiga olib keladi. Shu
sababli, amaliyotda uni optimallashtirish uchun memorization (natijalarni eslab
qolish) yoki iterativ usuldan foydalanish tavsiya etiladi.
Binomial koeffitsientlar
21

Kombinatorikada binomial koeffitsientlar, ya’ni qiymatlari ham rekursiv
tarzda ifodalanadi:
bazaviy holatlari:
Rekursiv kod:
int C(int n, int k) {
if (k == 0 || k == n) return 1;
else return C(n - 1, k - 1) + C(n - 1, k);
}
Bu usul ham sodda va tushunarli, lekin murakkabligi yuqori. Shu boisdan
amaliy ishlanmalarda dinamik dasturlashdan foydalaniladi.
Evklid algoritmi
Ikki sonning eng katta umumiy bo‘luvchisini topishda eng mashhur
usullardan biri bu Evklid algoritmidir. Ushbu algoritm ham rekursiv usulda
yozilishi mumkin:
int gcd(int a, int b) {
if (b == 0) return a;
else return gcd(b, a % b);
}
Bu yerda a % b har bir bosqichda sonlarni qisqartiradi va oxirida b == 0
bo‘lsa, a eng katta umumiy bo‘luvchi hisoblanadi. Evklid algoritmi juda samarali
bo‘lib, amaliyotda keng qo‘llaniladi.
Kombinatsion muammolar
Masalan, barcha permutatsiyalarni yoki kombinatsiyalarni aniqlash kabi
masalalar rekursiv tarzda hal qilinadi. Bu yerda backtracking usuli keng ishlatiladi.
Quyida satrning barcha permutatsiyalarini chiqarish uchun yozilgan rekursiv
funksiya misoli keltiriladi:
void permute(string str, int l, int r) {
if (l == r)
cout << str << endl;
else {
22

for (int i = l; i <= r; i++) {
swap(str[l], str[i]);
permute(str, l + 1, r);
swap(str[l], str[i]); // rollback (backtrack)
}
}
}
Bu kodda har bir bosqichda satrning elementlari o‘zaro almashtiriladi va
keyingi rekursiv chaqiruvga o‘tiladi. Bu kabi yondashuvlar NP-murakkablikdagi
masalalarda ham foydali bo‘ladi.
Massivlar va daraxtlar bilan ishlashda rekursiya
Rekursiv usullar daraxt ko‘rinishidagi tuzilmalarda tugunlar ustida amallar
bajarish uchun ideal hisoblanadi. Masalan, binary search tree (BST) bo‘yicha
element qidirish, qo‘shish yoki o‘chirish ham rekursiya orqali oson ifodalanadi.
Shuningdek, fayl tizimlarini rekursiv ko‘rib chiqish yoki kataloglar ichidagi barcha
fayllarni aniqlash uchun ham aynan rekursiv yondashuv qo‘llaniladi.
Shunday qilib, rekursiya matematik va algoritmik muammolarning keng
doirasini hal etishda beqiyos vositadir. U orqali murakkablikni soddalashtirish,
mantiqiy tahlilni yaxshilash, va kodni soddalashtirish mumkin. Shu sababli,
rekursiv yondashuvlarni o‘rganish dasturchilar uchun zaruriy bilimlardan biridir.
Keyingi bo‘limda esa bu bilimlar asosida amaliy masalalarni yechish tajribasi
kengaytiriladi.
3.3. Rekursiv funksiyalarni optimallashtirish va ularning samaradorligini
oshirish usullari
Rekursiv funksiyalar dasturlashda muhim va qulay vositalardan biri
bo‘lishiga qaramasdan, noto‘g‘ri ishlatilganda ularning ishlash samaradorligi
keskin kamayishi mumkin. Ayniqsa, rekursiv chaqiruvlar soni ortib borgani sari
kompyuter xotirasi va hisoblash quvvatiga bo‘lgan talab keskin oshadi. Shu
sababli, ushbu bobda rekursiv funksiyalarni optimallashtirishning samarali usullari,
23

ularning ishlash vaqtini qisqartirish, xotira sarfini kamaytirish, va kodni yanada
barqaror qilish yo‘llari tahlil qilinadi.
Rekursiv funksiyalarning asosiy muammolaridan biri bu takroriy hisob-
kitoblar (ya'ni bir xil qiymatlar bir necha marta hisoblanishi) va stack overflow
(ya'ni rekursiya chuqurligining juda katta bo‘lishi natijasida stek xotiraning to‘lib
qolishi) holatlaridir. Bu holatlarni oldini olish uchun quyidagi asosiy usullar
qo‘llaniladi:
1. Memorization (natijalarni keshga yozib borish)
Ko‘p hollarda rekursiv funksiyalar bir xil kirish qiymatlari uchun qayta-
qayta chaqiriladi. Bu holatni yo‘qotish uchun "memorization" texnikasidan
foydalaniladi. Ushbu yondashuvda funksiyalar bajarilgan natijalar maxsus massiv
yoki xotira strukturasi (masalan, map) orqali saqlab boriladi. Shunday qilib, bir xil
kirish qiymati takroran chaqirilganda natijani qayta hisoblashga hojat qolmaydi.
Misol uchun, Fibonacci sonlarini quyidagi tarzda optimallashtirish mumkin:
#include <iostream>
#include <vector>
using namespace std;
vector<long long> fibCache(1000, -1);
long long fib(int n) {
if (n <= 1) return n;
if (fibCache[n] != -1) return fibCache[n];
return fibCache[n] = fib(n - 1) + fib(n - 2);
}
Bu yondashuv hisoblashlar sonini keskin kamaytiradi va samaradorlikni
sezilarli darajada oshiradi.
2. Tail recursion (dum rekursiya)
"Dum rekursiya" bu rekursiv funksiyaning oxirgi amali yana o‘sha
funksiyani chaqirishdan iborat bo‘lgan holatdir. Ko‘pgina zamonaviy
kompilyatorlar tail-recursion'ni avtomatik ravishda iteratsiyaga aylantirib
24

optimallashtiradi. Misol uchun, faktorialni quyidagi tarzda tail-recursive qilish
mumkin:
int factorialTail(int n, int acc = 1) {
if (n == 0) return acc;
return factorialTail(n - 1, n * acc);
}
Bu funksiya odatiy rekursiyadan ko‘ra samaraliroq ishlaydi, chunki har bir
chaqiruvdan keyin yangi amallar bajarilmaydi.
3. Iterativ yondashuvga o‘tish
Agar rekursiya juda chuqur bo‘lib ketayotgan bo‘lsa yoki kompyuter
resurslari cheklangan bo‘lsa, unda rekursiyani iteratsiya (ya’ni for, while sikllar)
orqali yozish maqsadga muvofiq. Bu holatda rekursiv chaqiruvlar stek xotirani
egallamaydi va hisoblashlar doimiy davom etadi.
Masalan, faktorial funksiyasining iterativ ko‘rinishi quyidagicha bo‘ladi:
int factorialIter(int n) {
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
4. Rekursiyani cheklash yoki shartlar orqali to‘xtatish
Ba’zi holatlarda rekursiv funksiyalar ortiqcha chaqiruvlarga sabab bo‘ladi.
Buni oldini olish uchun aniq shartlar va chegaralarni belgilash lozim. Masalan,
rekursiv algoritmlarda maksimal chuqurlik yoki vaqt cheklovi kiritiladi.
5. Dinamik dasturlashga o‘tish
Agar rekursiya biror kombinator muammoni hal qilishda ishlatilayotgan
bo‘lsa va hisoblashlar ko‘p marotaba takrorlanayotgan bo‘lsa, uni to‘liq dinamik
dasturlashga o‘tkazish tavsiya etiladi. Bu usulda masalaning kichik holatlari
natijalari oldindan hisoblanadi va keyingi natijalar shu asosda quriladi.
25

6. Rekursiv daraxtlarni optimallashtirish
Ayniqsa, kombinatsiyalar, permutatsiyalar, yoki graf muammolarini hal
qilganda yuzaga keladigan rekursiv daraxtlar sonini kamaytirish uchun
backtracking optimallashtirish, branch and bound, yoki pruning kabi usullar
qo‘llaniladi. Bu usullar har bir ehtimoliy yo‘lni tekshirishdan oldin kerakli
shartlarni tekshiradi va ortiqcha hisoblashlarni kamaytiradi.
Xulosa sifatida, rekursiv funksiyalar kuchli vosita bo‘lishiga qaramay, ularni
to‘g‘ri va samarali ishlatish talab etiladi. Optimallashtirish orqali nafaqat hisoblash
tezligini oshirish, balki dastur barqarorligi va ishonchliligini ham ta’minlash
mumkin. Dasturchi sifatida biz har doim rekursiv yondashuvni muammoga mos
holatda tanlashimiz va kerak bo‘lsa uni alternativ yondashuvlar bilan
almashtirishni ko‘rib chiqishimiz zarur. Shu orqali katta va murakkab hisoblash
masalalarini ham samarali hal qilish mumkin bo‘ladi.
26

XULOSA
Rekursiya algoritmlar nazariyasida va amaliy dasturlashda keng
qo‘llaniladigan samarali usullardan biri hisoblanadi. U orqali ko‘plab murakkab
masalalarni sodda, tushunarli va elegant shaklda ifodalash mumkin bo‘ladi. Ushbu
kurs ishida rekursiv funksiyalarning asosiy tushunchalari, ishlash prinsiplari, ularni
turli vazifalarda qo‘llash usullari hamda samaradorlikni oshirish yo‘llari chuqur
tahlil qilindi.
Birinchi bobda rekursiyaning nazariy asosi, ya’ni uning matematik va
mantiqiy mazmuni, kompyuter xotirasida qanday ishlashi, rekursiv va iterativ
funksiyalar o‘rtasidagi farqlar, shuningdek, rekursiyaning turlari (to‘liq, qisman,
to‘xtovsiz, ko‘p tarmoqli) batafsil o‘rganildi. Ushbu bilimlar dasturchilar uchun
rekursiyaning qanday holatlarda afzal va qanday holatlarda xavfli bo‘lishini
anglashda juda muhimdir.
Ikkinchi bobda rekursiv yondashuv yordamida yechiladigan turli masalalar –
faktorial, Fibonachchi sonlari, Euklid algoritmi, minoralar masalasi, qidiruv va
saralash algoritmlari, kombinatorika va graflarga oid muammolar bo‘yicha keng
amaliy misollar keltirildi. Bu bob orqali rekursiyaning naqadar keng
imkoniyatlarga ega ekani, ayniqsa, ma’lumotlar tuzilmalari va murakkab
algoritmik muammolarda undan unumli foydalanish mumkinligi ko‘rsatildi.
Uchinchi bob esa rekursiv funksiyalarni optimallashtirishga bag‘ishlandi.
Sababi, rekursiya noto‘g‘ri ishlatilsa, samaradorlik past bo‘lishi, stack overflow
xatoliklariga olib kelishi mumkin. Shuning uchun memorization (keshga saqlash),
tail recursion (dum rekursiya), iteratsiyaga o‘tkazish, dinamik dasturlash va
rekursiv daraxtlarni qisqartirish texnikalari muhim rol o‘ynaydi. Dasturchilar
ushbu usullarni to‘g‘ri tanlagan taqdirda, dastur tezligi va barqarorligi sezilarli
darajada ortadi.
Umuman olganda, rekursiya zamonaviy algoritmlar, til kompilyatsiyasi,
sun’iy intellekt, graf nazariyasi, fayl tizimlarini yuritish, ma’lumotlarni saralash va
tahlil qilish, matematik modellashtirish kabi ko‘plab sohalarda qo‘llaniladi. Uni
o‘rganish nafaqat dasturlash bilimlarini chuqurlashtiradi, balki algoritmik fikrlash
27

qobiliyatini ham rivojlantiradi. Rekursiv yondashuvni to‘g‘ri tushunib, u bilan
samarali ishlay oladigan dasturchilar o‘z sohasining yetakchi mutaxassislariga
aylanishadi.
Ushbu kurs ishi orqali rekursiyaning nazariy va amaliy tomonlarini
mukammal o‘rganish, u orqali algoritmlarni optimallashtirish, murakkab
masalalarni samarali yechish va dasturlashda qulaylik yaratish imkoniyati mavjud
ekanligini ko‘rsatish maqsad qilingan. O‘rgangan bilim va ko‘nikmalar kelgusidagi
dasturlash amaliyotida muhim vosita sifatida xizmat qiladi.
28

FOYDALANILGAN ADABIYOTLAR
1. Abdullayev A.A. – Algoritmlarni loyihalash asoslari, Toshkent, 2016.
2. Abduraxmanov A. – C++ dasturlash tili asoslari, Toshkent, 2017.
3. Azizov S. – Dasturlash asoslari va amaliyoti, Toshkent, 2021.
4. Baxromov I.B. – Ma’lumotlar tuzilmasi va algoritmlar, Toshkent, 2020.
5. D.E. Knuth – The Art of Computer Programming, Volume 1, Addison-
Wesley, 197.
6. Dasturchilar uchun qo‘llanma – C++ Reference Manual, GNU Press,
2015.
7. Ganiyev B. – Algoritmlar va ma’lumotlar tuzilmasi, Toshkent, 2019.
8. Grinchenko N.A. – Rekursiv algoritmlar nazariyasi, Moskva, 2005.
9. Horowitz E., Sahni S. – Fundamentals of Data Structures, Computer
Science Press, 198.
10. Karimov A.A. – Zamonaviy dasturlash usullari, Toshkent, 2020.
11. Kichkina V.P. – Algoritmlar nazariyasi, Moskva, 2002.
12. Malik D.S. – C++ Programming: From Problem Analysis to Program
Design, Cengage Learning, 2012.
13. Niklaus Wirth – Algorithms and Data Structures, Prentice Hall, 1985.
14. Sedgewick R. – Algorithms in C++, Addison-Wesley, 2001.
15. Umarkhodjayev B. – Dasturlash algoritmlari va ularning tahlili,
Toshkent, 2022.
Qo‘shimcha adabiyotlar:
Robert Lafore – Object-Oriented Programming in C++, Sams Publishing,
2002.
Abdulov A.K. – Rekursiv algoritmlarning amaliy tahlili, Toshkent, 2018.
Taniqulov A.A. – Kompyuter fanlari va rekursiv hisoblash, Toshkent, 2015.
29

Internet manbalari:
https://www.geeksforgeeks.org – Rekursiya asoslari va masalalari
https://cplusplus.com – C++ funksiyalar va rekursiya bo‘yicha rasmiy
hujjatlar
https://stackoverflow.com – Rekursiv algoritmlar haqida savol-javoblar
https://www.tutorialspoint.com/cplusplus – C++ rekursiv funksiyalar
bo‘yicha qo‘llanma
https://visualgo.net – Rekursiv algoritmlarning vizualizatsiyasi
30

Rekursiya masalalari

Купить