REKURSIYA VA UNI
DASTURLASHDA QO‘LLASH.
REKURSIV ALGORITMLAR,
ULARNING TAHLILI.
REKURSIYAGA DOIR
MISOLLAR.
REKURSIV ALGORITMLAR
Rekursiv funktsiyalar - ular ichida o'zini chaqiruvchi funktsiyalar. Rekursiv funktsiya
o'zining nusxasini chaqirish va dastlabki masalalarning kichikroq muammolarini hal
qilish orqali ma'lum bir muammoni hal qiladi. \
REKURSIYA
Faktorial hisoblash
Fibonachchi ketma-
ketligi
Ikkilik qidiruv
ODDIY REKURSIYA
To'g'ridan-to'g'ri rekursiya, shuningdek, oddiy rekursiya deb
ham ataladi, funktsiya o'z tanasi ichida o'zini bevosita
chaqirganda sodir bo'ladi. Boshqacha qilib aytganda,
to'g'ridan-to'g'ri rekursiv funktsiyada vositachi yoki
yordamchi funktsiya mavjud emas; bu o'zini chaqiradigan
funksiya. To'g'ridan-to'g'ri rekursiya rekursiv algoritmlarning
asosiy tushunchasi bo'lib, uni oddiy rekursiv chaqiruvlar bilan
aniqlash mumkin.
ODDIY REKURSIYA
def countdown(n):
if n <= 0:
print("Blastoff!")
else:
print(n)
countdown(n - 1)
countdown(5)
O’ZARO REKURSIYA
Bilvosita rekursiya, ya'ni o'zaro rekursiya deb ham ataladi, ikki yoki
undan ortiq funktsiyalar ma'lum bir vazifani bajarish uchun
to'g'ridan-to'g'ri yoki bilvosita bir-birini tsiklik tarzda chaqirganda
sodir bo'ladi. Boshqacha qilib aytganda, A funktsiyasi B
funktsiyasini chaqiradi, bu esa, o'z navbatida, A yoki boshqa
funktsiyani chaqiradi, bu esa oxir-oqibat A funktsiyaga olib keladi.
Bu tsiklik munosabatlar muammoni hal qilish uchun ushbu
funktsiyalarning birgalikda ishlashiga imkon beradi. Bilvosita
rekursiya dasturlashda kamroq tarqalgan, ammo kuchli
tushuncha bo'lib, muayyan turdagi muammolarni hal qilish
uchun foydali bo'lishi mumkin.
O’ZARO REKURSIYA
def is_even(n):
if n == 0:
return True
else:
return is_odd(n - 1)
def is_odd(n):
if n == 0:
return False
else:
return is_even(n - 1)
print(is_even(4))
print(is_odd(5))
DUMLI(TAILED) REKURSIYA
Dumli rekursiya - bu rekursiyaning o'ziga xos shakli bo'lib,
unda rekursiv chaqiruv natijani qaytarishdan oldin
funktsiyada bajarilgan oxirgi operatsiya bajariladi.
Boshqacha qilib aytganda, rekursiv chaqiruv funksiyaning
oxirida yoki "dumida" joylashgan. Bu xususiyat ba'zi
dasturlash tillari va muhitlarida ma'lum optimallashtirish
imkonini beradi, masalan, tail call optimization (TCO), bu
samaradorlikni oshirish va stek to'lib ketishi xatolarining
oldini olish imkonini beradi.
DUMLI(TAILED) REKURSIYA
def factorial_tail_recursive(n, accumulator=1):
if n == 0:
return accumulator
else:
return factorial_tail_recursive(n - 1, n *
accumulator)
result = factorial_tail_recursive(5)
print(result)
# Output: 120
DUMLI(TAILED) REKURSIYA
Quyruq rekursiyasi nafaqat samaraliroq, balki
kodni o'qish va tushunish nuqtai nazaridan
ham yaxshiroq. Biroq, barcha dasturlash tillari
va muhitlar qo'ng'iroqni optimallashtirishni
qo'llab-quvvatlamaydi, shuning uchun quyruq
rekursiyasining samaradorligi til va kompilyator
yoki tarjimonga qarab farq qilishi mumkin.
NON-TAILED REKURSIYA
Quyruq bo'lmagan rekursiya - bu rekursiyaning bir turi bo'lib, unda
rekursiv chaqiruv natijani qaytarishdan oldin funktsiyada bajarilgan
oxirgi operatsiya emas. Boshqacha qilib aytganda, rekursiv qo'ng'iroq
qaytib kelganidan keyin qo'shimcha ish yoki hisoblash amalga
oshiriladi. Quyruq bo'lmagan rekursiv funktsiyalar quyruq-rekursiv
funktsiyalarga qaraganda kamroq samarali bo'lishi mumkin, chunki
ular har bir rekursiv qo'ng'iroq bilan qo'ng'iroqlar to'plamini
yaratishga moyil bo'lib, chuqur rekursiya uchun stekning to'lib
ketishiga olib kelishi mumkin.
REKURSIV ALGORITMLAR
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
| 