REKURSIV FUNKSIYA VA ISHLATILISHI

Загружено в:

20.11.2024

Скачано:

0

Размер:

35.275390625 KB

Скачать

REKURSIV FUNKSIYA VA ISHLATILISHI
MUNDARIJA
I.KIRISH………………………………………………………………………..3
1.1Rekursiv funksilari…………………………………………….………..…. . 4
1.2 Rekursiya tushunchasi va uning turlari…………………………..……... . 6
1.3 Rekursiv chaqiruv mexanizmi……………………………………….…... .. 9
1.4 Aniqroq tushuntirish uchun, rekursiv yondashuv orqali yechilgan bir
nechta masalalar bilan birlikda C++ da dasturiy modullarni yaratishni ko'rib
chiqamiz................................................................................ .............................. 11
1.5 Rekursiya va uning dasturlashda ishlatilishi………………………….13
III.XULOSA…………………………………………………………………...19
IV.FOYDALANILGAN ADABIYOTLAR RO'YXATI…………………....21
Kirish.

Kompyuterlarning kuchayib borishi va hal qilinayotgan muammolarning
murakkabligi ushbu mashinalarning algoritmlarini boshqarishning samarali
usullarini topishni talab qiladi.
Dasturni o'zgartirish va unga xizmat ko'rsatish jarayonini soddalashtirish
uchun dastur kodining tushunarliligini ta'minlash kerak. Bunday muammolarni hal
qilishning eng samarali va qulay usullaridan biri rekursiv protseduralarni ilovalarni
amalga oshirishga kiritishdir, ularning amalga oshirish mexanizmlari ko'pgina
zamonaviy kompilyatorlar va ilovalarni ishlab chiqish muhitlariga kiritilgan.
Tadqiqot muammosining dolzarbligi rekursiv mexanizmlarni amaliy
qo'llash sohasining kengligi bilan belgilanadi. Jumladan, rekursiya sonli tahlilning
murakkab masalalarini yechish, tarjima algoritmlarini qurish va ro yxatlar bo yichaʻ ʻ
har xil turdagi operatsiyalarni bajarish uchun qo llaniladi, bu esa o z navbatida
ʻ ʻ
zamonaviy avtomatlashtirilgan boshqaruv tizimlarini ishlab chiqishda zarurdir.
Rekursiyaning ahamiyatini ortiqcha baholab bo'lmaydi. Rekursiya eng
kuchli usullardan biri bo'lib, ilmiy bilimlarning eng umumiy mexanizmi
hisoblanadi. Rekursiya nafaqat ko'plab amaliy masalalarni yechishda samarali
qo'llanilishini topdi, balki nazariy tabiatshunoslik fanlarining ajralmas qismiga
aylandi.
Ushbu kurs ishisi doirasida olib borilgan tadqiqotning maqsadi C++ yuqori
darajadagi dasturlash tilida dasturlarni ishlab chiqish va amalga oshirishdan iborat.
Ushbu kurs ishisining o'rganish ob'ekti yuqori darajadagi dasturlash tillaridir.
Ushbu kurs ishisining mavzusi rekursiv protseduralar va funktsiyalar, shuningdek,
rekursiv chaqiruvlar mexanizmi va turlari.
Tadqiqot maqsadlari:
1) tadqiqot ob’ektini tahlil qilish;
2) tadqiqot mavzusi bo'yicha nazariy ma'lumotlarni tahlil qilish;
3) amaliy misollarni o'rganish;
4) tadqiqot davomida olingan bilim va ko‘nikmalarni amaliyotda qo‘llash, shu
jumladan rekursiv mexanizmlardan foydalangan holda dasturiy modulni ishlab
chiqish;
2

5) o'tkazilgan tadqiqot va yuklangan vazifalarni hal qilish bo'yicha hisobotni
shakllantirish, shu jumladan ishlab chiqilgan dasturiy modul tavsifi, shuningdek
xulosalarni shakllantirish.
Muammoni hal qilish uchun C++ dasturlash tili sifatida uning quyidagi
afzalliklarini hisobga olgan holda tanlandi:
-tushunish imkoniyati (shu jumladan tuzilmalarning mazmunli nomlari);
-ko'lamlilik;
-xotira, portlar va past darajadagi adreslash bilan o'zaro aloqa qilish qobiliyati
-har xil turdagi ma'lumotlarning umumiy algoritmlarini ishlab chiqish, ularning
ixtisoslashuvi va kompilyatsiya bosqichida hisob-kitoblarni shablonlardan
foydalangan holda ishlab chiqish qobiliyati.
1.1.Rekursiv funksiya
Rekursiv funksiya, o'zini takrorlash imkoniyatiga ega bo'lgan funksiya. Bu
funksiyalar boshqa funksiyalarni o'z ichiga olgan holda chaqirish orqali
takrorlanadi. Rekursiya boshqa funksiyani o'z ichiga olgan holda chaqirish orqali
amalga oshiriladi.
Rekursiv funksiyalar quyidagi asosiy xususiyatlarga ega:
1. O'zini chaqirish: Rekursiv funksiya o'zini takrorlash imkoniyatiga ega bo'lgani
uchun, ular o'zlarini chaqirish orqali amalga oshiriladi.
2. O'zgaruvchilarning o'zgarishi: Rekursiv funksiya o'z ichida o'zgaruvchilarni
ishlatadi, va har bir chaqiruvda ularning qiymati o'zgaradi.
3. Base case: Rekursiv funksiyaning chaqirilishi vaqti o'zgaruvchilar qiymati
o'zgarmasini ta'minlovchi shartni qo'yilishi kerak. Bu shart, funksiya
takrorlanishini to'xtatadi.
4. Oxirgi tikish sharti: Har bir rekursiv funksiya oxirgi o'qishida funksiya ish
bajarishini to'xtatish uchun oxirgi tikish sharti mavjud bo'lishi kerak.
3

Rekursiv funksiyalardan to'g'ri foydalanish juda kuchli algoritmlar yaratishda
va dasturlashda yordam beradi. Masalan, faktorial hisoblash, Fibonacci ketma-
ketligi, qatlam qiyoslash, va h.k. amallar rekursiv funksiyalar orqali yaxshi
yechimlar topish mumkin.Rekursiv funksiyalar, dasturlashda takrorlanuvchi
vazifalarni yechish uchun juda foydali bo'lib, ularga misollar ko'rsatilishi mumkin:
1. Faktorial hisoblash: Faktorialni hisoblashda, n! = n * (n-1)! formula
yordamida rekursiv funksiya ishlatiladi.
2. Fibonacci ketma-ketligi: Fibonacci ketma-ketligi, har bir sonning o'zidan
oldingi ikki son yig'indisiga teng bo'lgan birinchi son 0 va ikkinchi son 1 bilan
boshlanadi. Bunday rekursiv funksiya orqali Fibonacci ketma-ketligi
hisoblanadi.
3. Soni to'plamining hisoblanishi: Soni to'plami, berilgan sonning o'zidan
avvalgi barcha sonlarni qo'shuvchi funksiya yordamida hisoblanadi. Rekursiv
funksiya yordamida ushbu amal bajariladi.
Rekursiv funksiyalarni yaxshi tushunish uchun bir nechta misollarga e'tibor
beraylik:
Faktorial hisoblash:
def factorial(n):
return ;
else:
trturn n*factorial(n-1)
print(factorial(5))
#Natija: 120
1. Fibanachi ketma-ketligi:
4

def factorial(n):
if n<=1:
return n
else:
return fiboncci(n-2)
print(fiboncci(6))
#Natija: 8
Ushbu misollarda, har bir funksiya o'zining takrorlash jarayonini o'rnatadi va
rekursiv ravishda ishlatiladi. Muhimdirki, har bir funksiya takrorlashni to'xtatish
uchun shartlar mavjud bo'lsin.
1.2 Rekursiya tushunchasi va uning turlari
Rekursiya dasturlashda o'zini takrorlashning amaliyoti uchun ishlatiladi.
Rekursiya tushunchasi, funksiya yoki algoritmni boshqarish usulini ifodalaydi, bu
usulda funksiya o'zini o'z ichiga olgan holda chaqirish orqali takrorlanadi.
Rekursiv funksiyalar o'zining takrorlanishida ishlatiladigan funksiyalardir. Bu
funksiyalar o'zlarini o'z ichiga olgan holda chaqirish orqali bajariladi.
Rekursiv funksiyalar turli turdagi vazifalarni bajarishda foydalaniladi.
Masalan, faktorial hisoblash, Fibonacci ketma-ketligi hisoblash, binar qidirish
algoritmi, graf yaratish va qayta o'rganish kabi vazifalarni bajarishda rekursiv
funksiyalar keng qo'llaniladi.
Rekursiv funksiyalar quyidagi turlarga bo'linadi:
Oddiy (sirtdan qaytadan) : Bu turdagi rekursiv funksiyalar o'zlarini o'z ichiga
olgan holda chaqirish orqali takrorlanadi.
5

Durchi (orqadan oldinga) : Bu turdagi rekursiv funksiyalar o'zlarini o'z ichiga
olgan holda chaqirish orqali takrorlanadi, lekin natija qaytib ko'rish vaqti orqali
kichikroq bo'lgan holatlarda ishlatiladi.
Ko'p qadamli (multiplicative) : Bu turdagi rekursiv funksiyalar o'zlarini o'z ichiga
olgan holda bir nechta marta chaqirish orqali takrorlanadi.
Rekursiv funksiyalarni yozishda har doim base case (boshlang'ich holat) ni
belgilash muhimdir. Bu shart funksiyani takrorlashni to'xtatadi. Aks holda,
funksiya infinite loopga tushishi mumkin. Rekursiv funksiyalarni to'g'ri yozishda
amalni aniq va to'g'ri natijaga yo'l qo'ymoq muhimdir.
Rekursiv funksiya qanday ishlaydi? Rekursiv funksiya o'zini takrorlash
imkoniyatiga ega bo'lgan funksiya hisoblanadi. Bu funksiya o'z ichiga olgan holda
o'zini chaqirib ishlaydi.
Rekursiv funksiyalarni nima uchun ishlatish mumkin? Rekursiv funksiyalar
murakkab algoritmlarni yozishda va yechishda yordam beradi. Ularga misol
sifatida, faktorial hisoblash, Fibonacci ketma-ketligi hisoblash, binar qidirish
algoritmi, graf yaratish va qayta o'rganish kabi amallar kiritiladi.
Rekursiv funksiyalarni yozish qoidalari nima? Rekursiv funksiyalarni yozishda
quyidagi qoidalarga rioya etilishi kerak:
Har bir funksiya o'zining base case (boshlang'ich holat) ni belgilashi kerak.
Rekursiv qadamda o'zgaruvchilarning qiymati o'zgarishi kerak.
Oxirgi tikish sharti funksiya oxirgi tikishida takrorlashni to'xtatish uchun
belgilanishi kerak.
Base case va rekursiv qadam to'g'ri ishga tushishi lozim.
6

Rekursiv funksiyalarni yozishda qanday ko'p qadamli algoritmlarni yozish
muhimmi? Ha, rekursiv funksiyalar ko'p qadamli algoritmlarni yozishda juda
foydali bo'ladi. Masalan, biror sonni tub sonmi yoki yo'qligini aniqlash, ko'p
qadamli bo'shliqni hisoblash kabi masalalar rekursiv funksiyalar orqali yechiladi.
Rekursiv funksiyalar juda kuchli algoritmik vositalar hisoblanadi, lekin ularni
yozishda ehtiyotkorlik kerak. To'g'ri rekursiv funksiyalarni yozishga harakat qilish
kerak, aks holda infinite loop yoki dasturning xavfsizligi uchun muammolar
yuzaga kelishi mumkin.
Aniqroq ma'lumot uchun, faktorial hisoblash misolini ko'rsatib beraman.
Faktorial hisoblash uchun rekursiv funksiyani quyidagi ko'rinishda yozish
mumkin:
Bu misolda, rekursiv funksiya factorial() yaratildi. Agar kiritilgan son 0 yoki
1 ga teng bo'lsa, funksiya 1 qaytaradi (base case). Aks holda, faktorialni hisoblash
uchun sonni o'zidan bir kichik sonning faktorialini hisoblash uchun rekursiv
ravishda o'zini chaqiradi.
1.3 Rekursiv chaqiruv mexanizmi
Bu, funksiyalar ko'plab ishni biror bir shartning bajarilishidan oldin, o'zini
chaqirish orqali bajargan holda yechishni osonlashtiradi.
Rekursiv chaqiruvning ikki asosiy qismlari bor:
Rekursiv chaqiruv, dasturlashda funksiyani o'zini o'z ichiga olgan holda
chaqirishni ifodalaydi. Boshlang'ich holat (Base case): Bu shart funksiya
chaqirishining to'xtatilishi uchun belgilanadi. Rekursiv funksiyada, agar bu shart
bajarilganda, funksiya takrorlanishini to'xtatadi va ma'lum bir qiymatni qaytaradi.
7

Rekursiv qadam (Recursive step): Bu qadam, funksiya o'zini chaqirib, ishni
bajarish uchun belgilanadi. Bu qadamda funksiya o'zini o'z ichiga olgan holda
chaqiriladi, ammo bu chaqiruvning natijasida amallar bajariladi.
Rekursiv funksiyalarda, har bir chaqiruvda, boshlang'ich holat va rekursiv qadam
muhimdir. Boshlang'ich holat, takrorlanish jarayonini to'xtatish uchun belgilanadi.
Agar bu shart bajarilganda, funksiya takrorlanishni to'xtatadi. Rekursiv qadam esa
funksiya o'zini chaqirishni o'z ichiga olgan holda amalga oshiradi.
Rekursiv funksiyalarni to'g'ri yozish juda muhimdir, aks holda infinite loop yoki
dasturning isrofi sodir bo'lishi mumkin. Raqamli misollarda, boshlang'ich holat va
rekursiv qadamning to'g'ri belgilanishi katta ahamiyatga ega ChatGPT
Rekursiv funksiyalarni o'rganish uchun, bir misol ko'rsatishdan boshlaymiz.
Ko'rsatilgan masalaga, C++ da faktorial hisoblash misolini quyidagi ko'rinishda
yozish mumkin :
#include <iostream>
using namespace std;
int son(int n){
int t,j=0;
while(n>0){
t=n%10;
j=j*10+t;
n=n/10;
}
return j;
}
int main(){
int n;
cout<<"sonni kiriting:"<<endl; cin>>n;
8

cout<<"kiritilgan sonning teskarisi:"<<son(n)<<endl;
return 0;}
-Zamonaviy dasturlash tillaridagi ko'plab ma'lumotlar tuzilmalari va ko'p
sonli ob'ektlar tabiatan rekursiv (masalan, fraktal ob'ektlar, sinf ierarxiyasi,
daraxtga o'xshash oddiy ma'lumotlar tuzilmalari) va takroriy amalga oshirishda
bunday tuzilmalar bilan o'zaro ta'sir qilish dasturlari juda g'ayritabiiy va ish uchun
noqulay.
-rekursiya kodni o'qish jarayonini sezilarli darajada osonlashtiradi (chunki kodni
istalgan joydan boshlab o'qish mumkin bo'ladi va o'zgaruvchilardagi barcha
o'zgarishlarni kuzatish uchun butun kodni boshidanoq o'rganishning hojati yo'q),
shu bilan nosozliklarni tuzatishni osonlashtiradi. .
-rekursiya “harakatlarning noto‘g‘ri tartibi”, “boshlanmagan o‘zgaruvchilardan
foydalanish” va boshqa shu kabi xatolardan qochish imkonini beradi.
Biroq, rekursiyaning ko'plab kamchiliklari ham bor. Ular orasida quyidagilarni
ta'kidlash kerak:
-dasturni cheksiz tsiklga kiritish ehtimoli yuqori;
-ba'zi formulalardan foydalanish kompyuter resurslarining nomutanosib ravishda
katta xarajatlari bilan bog'liq;
-juda ko'p funksiya chaqirilganda stekning to'lib ketishi ehtimoli yuqori.
Rekursiv qo'ng'iroqlarga xizmat ko'rsatish muayyan qo'shimcha xarajatlarni talab
qiladi, ammo parchalanish usuli bilan ishlab chiqilgan rekursiv algoritmlar
yaxshiroq asimptotik baholarga ega. Bu shuni anglatadiki, ma'lum bir kirish
uzunligidan boshlab, ko'pincha amaliy foydalanish sohasiga to'g'ri keladi, rekursiv
algoritmning dasturiy ta'minotini amalga oshirish vaqt samaradorligini oshiradi.
Ammo umuman olganda, xulosa o'zini ko'rsatadi - rekursiya ko'plab muammolarni
hal qilish uchun juda qulay vosita bo'lishiga qaramay, iloji bo'lsa, yuqori
samaradorlik talab qilinadigan hollarda rekursiv mexanizmlardan foydalanishdan
qochish yaxshiroqdir, chunki rekursiv algoritmlar talab qiladi. ko'proq bajarilish
vaqti va ularning bajarilishi qo'shimcha xotira xarajatlari bilan bog'liq.
9

1.4 Aniqroq tushuntirish uchun, rekursiv yondashuv orqali yechilgan bir
nechta masalalar bilan birlikda C++ da dasturiy modullarni yaratishni ko'rib
chiqamiz.
Faktorial hisoblash:
#include <iostream>
using namespace std;
int fact(int n);
int nain(){
int n, faktorial;
cout <<"n="; cin>>n;
faktorial=fact(n);
cout<<n<<"faktorial:"<<faktorial;
return 0;
int fact(int n){
if(n<0) {
return(-1); }
if (n==0) {
return1; }
else
return n*fact(n-1);
10

$} #natija n=5; kirtganimda javobi 120 ; 3. Soni to'plami: #include <iostream> int sum_of_numbers(int n) { if (n <= 0) return 0; else return n + sum_of_numbers(n - 1); } int main() { int n = 5; std::cout << "Soni to'plami: " << sum_of_numbers(n) << std::endl; return 0; } Ushbu masalalar C++ tilida rekursiv yondashuv orqali yechilgan. Dasturiy modullar esa shu masalalarni alohida fayllarga joylash va ularga kerakli funksiyalarni yozish orqali yaratiladi. Masalan, yuqorida ko'rsatilgan masalalarni alohida fayllarga joylash va ularga mos dasturiy modullarni yaratish mumkin. Bu modullarni boshqa dasturlar ichida chaqirish orqali ularga foydalanish mumkin. 1.5 Rekursiya va uning dasturlashda ishlatilishi. Rekursiv funksiya. Rekursiya deb funksiya tanasida shu funksiyaning o‘zini chaqirishiga aytiladi. Rekursiya ikki xil bo‘ladi: 1. oddiy – agar funksiya o‘z tanasida o‘zini chaqirsa; 11$

2. vositali – agar birinchi funksiya ikkinchi funksiyani chaqirsa, ikkinchisi esa o‘z
navbatida birinchi funksiyani chaqiradi.
Odatda rekursiya matematikada keng qo‘llaniladi. Chunki aksariyat
matematik formulalar rekursiv aniqlanadi. Misol tariqasida faktorialni hisoblash
formulasini va sonning butun darajasini hisoblashni ko‘rishimiz mumkin: N!
=1*2*…*N
Ko’rinib turibdiki, navbatdagi qiymatni hisoblash uchun funksiyaning
«oldingi qiymati» ma’lum bo‘lishi kerak. C++ tilida rekursiya matematikadagi
rekursiyaga o‘xshash. Buni yuqoridagi misollar uchun tuzilgan fuiksiyalarda
ko‘rish mumkin. Faktorial uchun:
#include <iostream>
unsigned long long factorial(int n) {
if (n == 0 || n == 1)
return 1;
else
return n * factorial(n - 1);}
int main() {
int n;
std::cout << "Istalgan son uchun faktorialni hisoblash: ";
std::cin >> n;
if (n < 0)
std::cout << "Manfiy son uchun faktorial mavjud emas." << std::endl;
12

else
std::cout << n << " ning faktoriali: " << factorial(n) << std::endl;
return 0;}
Agar faktorial funksiyasiga n>0 qiymat berilsa, quyidagi holat ro’y beradi:
shart operatorining else shoxidagi qiymati (n qiymati) stekda eslab qolinadi.
Noma’lumlarni hisoblash uchun shu funksiyaning o’zi «oldingi» qiymat (n-1
qiymati) bilan bilan chaqiriladi. O‘z navbatida, bu qiymat ham eslab qolinadi
(stekka joylanadi) va yana funksiya chaqiriladi va hakoza. Funksiya n=0 qiymat
bilan chaqirilganida if operatorining sharti ()!n rost bo‘ladi va «return 1;» amali
bajarilib, ayni shu chaqirish bo‘yicha 1 qiymati qaytariladi, Shundan keyin
«teskari» jarayon boshlanadi - stekda saqlangan qiymatlar ketma-ket olinadi va
ko‘paytiriladi: oxirgi qiymat aniqlangandan keyin (1), u undan oldingi saqlangan
qiymatga 1 qiymatiga ko‘paytirib F(1) qiymati hisoblanadi, bu qiymat 2 qiymatiga
ko‘paytirish bilan F(2) topiladi va hakoza. Jarayon F(n) qiymatini hisoblashgacha
«ko‘tarilib» boradi.
Namuna. Rekursiv funksiyadan foydalangan holda ikkita sondan raqamlari
yig‘indisi katta bo‘lgan sonni topuvchi dastur tuzing.
#include <iostream>
int findLargestSum(int a, int b) {
if (a == 0 && b == 0)
return 0;
else {
int lastDigitA = a % 10;
13

int lastDigitB = b % 10;
return std::max(lastDigitA + findLargestSum(a / 10, b), lastDigitB +
findLargestSum(a, b / 10)); }
}
int main() {
int num1, num2;
std::cout << "Ikkita son kiriting: ";
std::cin >> num1 >> num2;
int result = findLargestSum(num1, num2);
std::cout << "Ikki sondan raqamlari yig'indisi katta bo'lgan son: " << result
<< std::endl;
return 0;}
Kompilyator ishlashi natijasida har bir funksiya mashina kodi ko‘rinishida
bo‘ladi. Agar programmada funksiyani chaqirish ko‘rsatmasi bo‘lsa, shu joyda
funksiyani adresi bo‘yicha chaqirishning mashina kodi shakllanadi. Odatda
funksiyani chaqirish protsessor tomonidan qo‘shimcha vaqt va xotira resurslarini
talab qiladi. SHu sababli, agar chaqiriladigan funksiya hajmi unchalik katta
bo‘lmagan hollarda, kompilyatorga funksiyani chaqirish kodi o‘rniga funksiya
tanasini o‘zini joylashtirishga ko‘rsatma berish mumkin. Bu ish funksiya
prototipini inline kalit so‘zi bilan e’lon qilish orqali amalga oshiriladi. Natijada
hajmi oshgan, lekin nisbatan tez bajariladigan programma kodi yuzaga keladi.
14

Odatda rekursiya matematikada keng qo‘llaniladi. CHunki aksariyat
matematik formulalar rekursiv aniqlanadi. Misol tariqasida faktorialni hisoblash
formulasini va sonning butun darajasini hisoblashni ko‘rishimiz mumkin.
Rekursiv funksiyalarni to‘g‘ri amal qilishi uchun rekursiv chaqirishlarning
to‘xtash sharti bo‘lishi kerak. Aks holda rekursiya to‘xtamasligi va o‘z navbatida
funksiya ishi tugamasligi mumkin. Faktorial hisoblashida rekursiv tushishlarning
to‘xtash sharti funksiya parametri n=0 bo‘lishidir (shart operatorining rost shoxi).
Har bir rekursiv murojaat qo‘shimcha xotira talab qiladi - funksiyalarning
lokal ob’ektlari (o‘zgaruvchilari) uchun har bir murojaatda stekdan yangidan joy
ajratiladi. Masalan, rekursiv funksiyaga 100 marta murojaat bo‘lsa, jami 100 lokal
ob’ektlarning majmuasi uchun joy ajratiladi. Ayrim hollarda, ya’ni rekursiyalar
soni etarlicha katta bo‘lganda, stek o‘lchami cheklanganligi sababli (real rejimda
64Kb o‘lchamgacha) u to‘lib ketishi mumkin. Bu holatda programma o‘z ishini
«Stek to‘lib ketdi» xabari bilan to‘xtadi.
Yana bir qiziq ma'lumot, shunday dasturlash tillari borki ularda umuman
takrorlanish operatorlari yo'q va bu borada butunlay rekursiyaga tayanadi. Haskell
va Erlang shular jumlasidan.
Albatta, bularning barchasi rekursiyani takrorlash operatorlaridan butunlay
ustunligini anglatmaydi. Aslida, ko'p hollarda dasturchilar rekursiya ishlatishdan
qochishadi. Buning asosiy sabablari esa:
Rekursiya har doim xotiradan qo'shimcha joy talab qiladi. Bu haqida Call
stack mavzumizda gaplashamiz.
Rekursiv yechimda xato qilib ehtimoli yuqori. Avval ham aytganimizdek,
rekursiya juda ham chalg'ituvchi. Shu sababli, uni ishlatishda osongina xato qilib
qo'yish mumkin.
15

$Rekursiv yechimni xatosini topish qiyin. Bunday masalalarda xato qilib qo'yish ehtimoli yuqori bo'lishi bilan birga uni topib to'g'irlash ham qiyin bo'lishi mumkin. Buning asosiy sababi, bunday yechimlarni tasavvur qilib olish (hayolan debug qilish) juda qiyin. Rekursiv algoritmning murakkabligini hisoblash ko'pincha juda murakkab. Hattoki, ba'zan to'g'ri yechimni yozishning o'zi ham kam bo'lib qolishi mumkin. Chunki, uni iterativ yechim bilan solishtirishda uning murakkabligini hisoblash kerak bo'ladi. Rekursiv algoritmlarda bu ko'pincha juda murakkab va yaxshigina matematika talab qiladi. Namuna: Rekursiv funksiyadan foydalangan holda ikkita sondan raqamlari yig‘indisi katta bo‘lgan sonni topuvchi dastur tuzing. #include <iostream> using namespace std; int sum_of_digits(int n) { if (n == 0) { return 0;} return n % 10 + sum_of_digits(n / 10);} int main() { int num; cout << "Ikkita sondan raqamlari yig'indisi katta bo'lgan sonni kiriting: "; cin >> num; int sum = sum_of_digits(num); 16$

cout << "Raqamlari yig'indisi: " << sum << endl;
return 0;}
XULOSA
Tadqiqot asosida bir nechta xulosalar chiqarish mumkin:
-birinchidan, rekursiv algoritmlar turli algoritmik masalalarni yechishning
universal vositasidir. Bunday turdagi echiladigan har qanday masala rekursiv
yechimga ega bo'lib, u o'zining nafisligi va inson idroki uchun soddaligi bilan
ajralib turadi;
-ikkinchidan, rekursiv algoritmlar ko'pincha ularning ekvivalent
iterativlariga qaraganda kamroq asimptotik murakkablikka ega. Ya'ni, ba'zi
hollarda ular tezroq ishlaydi;
-uchinchidan, zamonaviy dasturiy ta'minotning rivojlanishi rekursiyadan
amaliy foydalanishni ancha soddalashtirdi va yangi tushunchalar va dasturlash
texnologiyalari ko'p sonli protseduralarni chaqirish zarurati bilan yaratilgan
rekursiv dasturlarning past samaradorligi muammosini bartaraf etdi.
Rekursiya turli xil ilovalarda (matematika, tahlil qilish va tarjima qilish,
daraxtlarni saralash va dinamik tuzilishga ega ma'lumotlarni qayta ishlash, shaxmat
masalalari va boshqalar) paydo bo'ladigan mavhum fikrlash xususiyatini aks
ettiradi. Aynan shu turdagi muammolarda rekursiv algoritmlardan foydalanish
yaxshiroqdir, chunki ular jarayonlarni ketma-ket tavsiflash zaruratini yo'q qiladi va
bundan tashqari, deyarli barcha mavjud dasturlash tillari rekursiyani qo'llab-
quvvatlaydi.
Ammo shuni aytish kerakki, rekursiyani davra algoritmlari bilan
almashtirish haqida o'ylash har doim foydalidir. Biroq, ba'zi hollarda, muammoni
rekursiyasiz hal qilish juda qiyin bo'lishi mumkin va unumdorlik yutuqlari kuchga
arzimasligi mumkin.
17

Kurs ishining vazifalarini hal qilish jarayonida amaliy dasturlash tizimlari
va zarur yechim usullaridan foydalanilgan. Dasturiy dastur ishlab chiqildi. Ishlab
chiqish vositasi sifatida C++ Builder platformasi tanlangan.
Tadqiqot o'tkazish va berilgan muammolarni hal qilish natijasida kurs
davomida olingan quyidagi ko'nikmalar mustahkamlandi:
-kursning nazariy ma'lumotlarini o'rganish va amaliy masalalarni yechishda
qo'llash;
-muammoni bayon qilish va uni yechish algoritmini ishlab chiqish;
-amaliy dasturlash tizimlaridan foydalanish;
-asosiy dasturiy hujjatlarni ishlab chiqish;
-zamonaviy ob'ektga yo'naltirilgan dasturlash tizimlari bilan ishlash;
-obyektga yo'naltirilgan yuqori darajadagi C++ dasturlash tilidagi dasturiy
ta'minot dasturlarini ishlab chiqish va disk raskadrovka qilish.
FOYDALANILGAN ADABIYOTLAR RO'YXATI
1. Barron D. Dasturlashda rekursiv usullar - M.: Williams, 2017. - 221 b.
2. Bronitskaya N.A., Darmosyuk V.N., Berezhetskaya V.G.
KOMBINATORIY USULLAR: REKURSIYA VA DİNAMIK DASTURLASH //
Zamonaviy dunyoda tabiiy va matematika fanlari: to'plam. Art. ona tomonidan VI
xalqaro ilmiy-amaliy konf. - Novosibirsk: SibAK, 2013. - 12-15-betlar
3. Wirth N. Algoritmlar + ma'lumotlar tuzilmalari = dasturlar:
monografiya. - M.: Uilyams, 2015. - 707 b.
4. Golitsyna, O.L. Dasturlash tillari: Darslik / O.L. Golitsyna, T.L. Partyka,
I.I. Popov. - M.: Forum, SIC INFRA-M, 2013. - 400 b.
5. Green D., Knuth D. Algoritmlarni tahlil qilishning matematik usullari -
M.: Williams, 2015. - 398 p.
6. Cutland, N. Hisoblash qobiliyati. Rekursiv funksiyalar nazariyasiga
kirish / N. Katlend. - M.: Uilyams, 2015. - 952 b.
7. Knuth D. E. Dasturlash san'ati, 4-jild, A. Kombinatorial algoritmlar, 1-
qism = Kompyuter dasturlash san'ati, 4A-jild: Kombinatorial algoritmlar, 1-qism /
ed. Yu. V. Kozachenko. -- 1. -- M.: Uilyams, 2013. -- T. 4. -- 960 b.
18

8. Kolmogorov A.N. Axborot nazariyasi va algoritmlar nazariyasi - M.:
Uilyams, 2017. - 240 b.
9. Korotkov M.A., Stepanov E.O. Algoritmlar nazariyasi asoslari - M.:
Uilyams, 2016. - 174 b.
10. Maltsev, A.I. Algoritmlar va rekursiv funktsiyalar: monografiya. / A.I.
Maltsev. - M.: Uilyams, 2016. - 346 b.
11. Meyers S. Samarali va zamonaviy C++: C++11 va C++14 dan
foydalanish bo'yicha 42 ta tavsiyalar - M. Williams, 2016. - 304 p.
12. Orlov S. Dasturlash tillari nazariyasi va amaliyoti: Universitetlar uchun
darslik. 3-avlod standarti. (ruscha) - Sankt-Peterburg: Peter, 2013 - 688 b.
13. Pirs B. Dasturlash tillaridagi turlari. - Dobrosvet, 2012. - 680 p.
14. Straustup, B. C++ dasturlash tili. Maxsus nashr / B. Straustup. - M.:
Binom, 2015. - 1136 b.
15. Wetherell C. Dasturchilar uchun eskizlar - M .: Williams, 2015. - 801 p.
16. Fridman, A.L. C++ tilida ob'ektga yo'naltirilgan dasturlash asoslari /
A.L. Fridman. -- M .: Gor. Line-Telecom, 2012. -- 234 b.
19

REKURSIV FUNKSIYA VA ISHLATILISHI MUNDARIJA I.KIRISH………………………………………………………………………..3 1.1Rekursiv funksilari…………………………………………….………..…. . 4 1.2 Rekursiya tushunchasi va uning turlari…………………………..……... . 6 1.3 Rekursiv chaqiruv mexanizmi……………………………………….…... .. 9 1.4 Aniqroq tushuntirish uchun, rekursiv yondashuv orqali yechilgan bir nechta masalalar bilan birlikda C++ da dasturiy modullarni yaratishni ko'rib chiqamiz................................................................................ .............................. 11 1.5 Rekursiya va uning dasturlashda ishlatilishi………………………….13 III.XULOSA…………………………………………………………………...19 IV.FOYDALANILGAN ADABIYOTLAR RO'YXATI…………………....21 Kirish.

Kompyuterlarning kuchayib borishi va hal qilinayotgan muammolarning murakkabligi ushbu mashinalarning algoritmlarini boshqarishning samarali usullarini topishni talab qiladi. Dasturni o'zgartirish va unga xizmat ko'rsatish jarayonini soddalashtirish uchun dastur kodining tushunarliligini ta'minlash kerak. Bunday muammolarni hal qilishning eng samarali va qulay usullaridan biri rekursiv protseduralarni ilovalarni amalga oshirishga kiritishdir, ularning amalga oshirish mexanizmlari ko'pgina zamonaviy kompilyatorlar va ilovalarni ishlab chiqish muhitlariga kiritilgan. Tadqiqot muammosining dolzarbligi rekursiv mexanizmlarni amaliy qo'llash sohasining kengligi bilan belgilanadi. Jumladan, rekursiya sonli tahlilning murakkab masalalarini yechish, tarjima algoritmlarini qurish va ro yxatlar bo yichaʻ ʻ har xil turdagi operatsiyalarni bajarish uchun qo llaniladi, bu esa o z navbatida ʻ ʻ zamonaviy avtomatlashtirilgan boshqaruv tizimlarini ishlab chiqishda zarurdir. Rekursiyaning ahamiyatini ortiqcha baholab bo'lmaydi. Rekursiya eng kuchli usullardan biri bo'lib, ilmiy bilimlarning eng umumiy mexanizmi hisoblanadi. Rekursiya nafaqat ko'plab amaliy masalalarni yechishda samarali qo'llanilishini topdi, balki nazariy tabiatshunoslik fanlarining ajralmas qismiga aylandi. Ushbu kurs ishisi doirasida olib borilgan tadqiqotning maqsadi C++ yuqori darajadagi dasturlash tilida dasturlarni ishlab chiqish va amalga oshirishdan iborat. Ushbu kurs ishisining o'rganish ob'ekti yuqori darajadagi dasturlash tillaridir. Ushbu kurs ishisining mavzusi rekursiv protseduralar va funktsiyalar, shuningdek, rekursiv chaqiruvlar mexanizmi va turlari. Tadqiqot maqsadlari: 1) tadqiqot ob’ektini tahlil qilish; 2) tadqiqot mavzusi bo'yicha nazariy ma'lumotlarni tahlil qilish; 3) amaliy misollarni o'rganish; 4) tadqiqot davomida olingan bilim va ko‘nikmalarni amaliyotda qo‘llash, shu jumladan rekursiv mexanizmlardan foydalangan holda dasturiy modulni ishlab chiqish; 2

5) o'tkazilgan tadqiqot va yuklangan vazifalarni hal qilish bo'yicha hisobotni shakllantirish, shu jumladan ishlab chiqilgan dasturiy modul tavsifi, shuningdek xulosalarni shakllantirish. Muammoni hal qilish uchun C++ dasturlash tili sifatida uning quyidagi afzalliklarini hisobga olgan holda tanlandi: -tushunish imkoniyati (shu jumladan tuzilmalarning mazmunli nomlari); -ko'lamlilik; -xotira, portlar va past darajadagi adreslash bilan o'zaro aloqa qilish qobiliyati -har xil turdagi ma'lumotlarning umumiy algoritmlarini ishlab chiqish, ularning ixtisoslashuvi va kompilyatsiya bosqichida hisob-kitoblarni shablonlardan foydalangan holda ishlab chiqish qobiliyati. 1.1.Rekursiv funksiya Rekursiv funksiya, o'zini takrorlash imkoniyatiga ega bo'lgan funksiya. Bu funksiyalar boshqa funksiyalarni o'z ichiga olgan holda chaqirish orqali takrorlanadi. Rekursiya boshqa funksiyani o'z ichiga olgan holda chaqirish orqali amalga oshiriladi. Rekursiv funksiyalar quyidagi asosiy xususiyatlarga ega: 1. O'zini chaqirish: Rekursiv funksiya o'zini takrorlash imkoniyatiga ega bo'lgani uchun, ular o'zlarini chaqirish orqali amalga oshiriladi. 2. O'zgaruvchilarning o'zgarishi: Rekursiv funksiya o'z ichida o'zgaruvchilarni ishlatadi, va har bir chaqiruvda ularning qiymati o'zgaradi. 3. Base case: Rekursiv funksiyaning chaqirilishi vaqti o'zgaruvchilar qiymati o'zgarmasini ta'minlovchi shartni qo'yilishi kerak. Bu shart, funksiya takrorlanishini to'xtatadi. 4. Oxirgi tikish sharti: Har bir rekursiv funksiya oxirgi o'qishida funksiya ish bajarishini to'xtatish uchun oxirgi tikish sharti mavjud bo'lishi kerak. 3

Rekursiv funksiyalardan to'g'ri foydalanish juda kuchli algoritmlar yaratishda va dasturlashda yordam beradi. Masalan, faktorial hisoblash, Fibonacci ketma- ketligi, qatlam qiyoslash, va h.k. amallar rekursiv funksiyalar orqali yaxshi yechimlar topish mumkin.Rekursiv funksiyalar, dasturlashda takrorlanuvchi vazifalarni yechish uchun juda foydali bo'lib, ularga misollar ko'rsatilishi mumkin: 1. Faktorial hisoblash: Faktorialni hisoblashda, n! = n * (n-1)! formula yordamida rekursiv funksiya ishlatiladi. 2. Fibonacci ketma-ketligi: Fibonacci ketma-ketligi, har bir sonning o'zidan oldingi ikki son yig'indisiga teng bo'lgan birinchi son 0 va ikkinchi son 1 bilan boshlanadi. Bunday rekursiv funksiya orqali Fibonacci ketma-ketligi hisoblanadi. 3. Soni to'plamining hisoblanishi: Soni to'plami, berilgan sonning o'zidan avvalgi barcha sonlarni qo'shuvchi funksiya yordamida hisoblanadi. Rekursiv funksiya yordamida ushbu amal bajariladi. Rekursiv funksiyalarni yaxshi tushunish uchun bir nechta misollarga e'tibor beraylik: Faktorial hisoblash: def factorial(n): return ; else: trturn n*factorial(n-1) print(factorial(5)) #Natija: 120 1. Fibanachi ketma-ketligi: 4

def factorial(n): if n<=1: return n else: return fiboncci(n-2) print(fiboncci(6)) #Natija: 8 Ushbu misollarda, har bir funksiya o'zining takrorlash jarayonini o'rnatadi va rekursiv ravishda ishlatiladi. Muhimdirki, har bir funksiya takrorlashni to'xtatish uchun shartlar mavjud bo'lsin. 1.2 Rekursiya tushunchasi va uning turlari Rekursiya dasturlashda o'zini takrorlashning amaliyoti uchun ishlatiladi. Rekursiya tushunchasi, funksiya yoki algoritmni boshqarish usulini ifodalaydi, bu usulda funksiya o'zini o'z ichiga olgan holda chaqirish orqali takrorlanadi. Rekursiv funksiyalar o'zining takrorlanishida ishlatiladigan funksiyalardir. Bu funksiyalar o'zlarini o'z ichiga olgan holda chaqirish orqali bajariladi. Rekursiv funksiyalar turli turdagi vazifalarni bajarishda foydalaniladi. Masalan, faktorial hisoblash, Fibonacci ketma-ketligi hisoblash, binar qidirish algoritmi, graf yaratish va qayta o'rganish kabi vazifalarni bajarishda rekursiv funksiyalar keng qo'llaniladi. Rekursiv funksiyalar quyidagi turlarga bo'linadi: Oddiy (sirtdan qaytadan) : Bu turdagi rekursiv funksiyalar o'zlarini o'z ichiga olgan holda chaqirish orqali takrorlanadi. 5

REKURSIV FUNKSIYA VA ISHLATILISHI

20.11.2024

0

35.275390625 KB

Похожие