|
Quyidagi misolni ko’raylik:
#include
void f1(int a);
void f1(int a, int b);
void f1(int a);
{cout<<”bitta argumetli”<
void f1(int a, int b);
{cout<<”2ta argumentli”<
int main ()
{f1(10); f1(10;20);}
Rekursiya
Funktsiya o’z - o’zini chaqirishi rekursiya deyiladi. U ikki xil - to’g’ri
rekursiya va bilvosita rekursiya bo’lishi mumkin. Agarda funktsiya o’zini-o’zi
chaqirsa bu to’g’ri rekursiya deyiladi. Agarda funktsiya boshqa bir funktsiyani
chaqirsa va u funktsiya o’z navbatida birinchisini chaqirish esa bilvosita rekursiya
deyiladi.
Ayrim muammolar rekursiya yordamida osonroq echiladi. Agarda
ma`lumotlar ustida biror protsedura ishlatilsa va uning natijasi ustida ham xuddi shu
protsedura bajarilsa, bunday hollarda rekursiyani ishlatish lozim. Rekursiya ikki xil
natija bilan yakunlanadi: u yoki oxir - oqibat albatta tugaydi va biror natija qaytaradi,
ikkinchisi hech qachon tugallanmaydi va xatolik qaytaradi.
Agarda funktsiya o’zini-o’zi chaqirsa bu funktsiyani nusxasi chaqirilishini
aytib o’tish lozim. Rekursiya yordamida echiladigan muammo sifatida Fibonachchi
qatorini ko’rsatish mumkin.
1, 1, 2, 3, 5, 8, 13, 21, 34 ...
Bu qatorning har bir soni (ikkinchisidan keyin) o’zidan oldiigi ikki sonning
yig’indisiga teng. Masala quyidagidan iborat: Fibonachchi qatorini 12 - a`zosi
nechaga tengligini aniqlang. Bu muammoni echishning usullaridan biri qatorni
batafsil tahlil qilishdan iboratdir. Qatorning oldingi ikki soni birga teng. Har bir
navbatdagi son oldingi ikkita sonning yig’indisiga teng. Ya`ni, o’n ettinchi son o’n
oltinchi va o’n beshinchi sonlar yig’indisiga teng. Umumiy holda n - soniing
yig’indisi (n -2)- va (n -1) - sonlarning yig’indisiga teng (n >2 hol uchun).
Rekursiv funktsiyalar uchun rekursiyani to’xtatish shartini berish zarur.
Fibonachchi qatori uchun to’xtatish sharti n <3 shartidir. Bunda quyidagi algoritm
qo’llaniladi:
1. Foydalanuvchidan Fibonachchi qatorining qaysi a`zosini hisoblashini
ko’rsatiishni so’raymiz.
2 fib() funktsiyasini chaqiramiz va unga foydalanuvchi tomonidan berilgan
Fibonachchi qatori a`zosi tartib nomerini argument sifatida uzatamiz.
3. fib() funktsiyasi (n) argumentni tahlil qiladi. Agarda n <3 bo’lsa, funktsiya 1
qiymat qaytaradi; aks holda fib() funktsiyasi o’zini-o’zi chaqiradi va unga argument
sifatida n - 2 qiymatni beradi, keyin yana o’z-o’zini chaqiradi va bu funktsiyaga n -
1 ni qiymat sifatida beradi. Bundan keyin esa ularning yig’indisini qiymat sifatida
uzatadi.
Agarda fib(l) funktsiyasi chaqirilsa u 1 qiymatni qaytaradi. Agarda fib(2)
funktsiyasi chaqirilsa u ham 1 qiymatni qaytaradi. Agarda fib(3) funktsiyasi
chaqirilsa u fib(1) va fib(2) funktsiyalarini yig’indisini qaytaradi, fib(2) va fib(l)
funktsiyalari 1 qiymatni qaytarganligi sababli fib(3) funktsiyasi qiymati 2 ga teng
bo’ladi.
Agarda fib(4) funktsiyasi chaqirilsa, bunda u fib(3) va fib(2) funktsiyalari
yig’indisini qiymat sifatida qaytaradi. fib(3) funktsiyasi 2 va fib(2) funktsiyasi 1
qiymat qaytarishidan fib(4) funktsiyasi 3 ni qiymat sifatida qaytarishi kelib chiqadi.
Demak, Fibonachchi qatorining to’rtinchi a`zosi 3 ga teng ekan.
Yuqorida, tavsiflangan usul bu masalani echishda unchalik samarali usul
emas. fib(20) funktsiyasi chaqirilsa, u tomonidan fib() funktsiyasi 13529 marta
chaqiriladi. Bunday hollarda ehtiyot bo’lish lozim. Agarda Fibonachchi qatorining
juda katta nomerini bersak xotira etishmasligi mumkii. Fib() funktsiyasini har safar
chaqirilishida xotiradan ma`dum bir soha zahiralanadi. Funktsiyadan qaytish bilan
xotira bo’shatiladi. Lekin, rekursiv tarzda funktsiya chaqirilsa xotiradan uning uchun
int main ()
{
Intx=fib(6)
}
Return fib4+5
Return fib3+4
Return fib2+3
Return fib2+1
Return fib2+3
Return1
Return fib1+2
Return1
Return fib1+2
Return1
Return1
Return1
Return1
Return1
Return1
yangi joy ajratiladi va toki ichki funktsiya o’z ishini tugatmaguncha uni chaqirgan
funktsiya egallagan joy bo’shatilmaydi. Shuning uchun xotirani etishmay qolish
xavfi bor. Fib() funktsiyasining ishlatilishi quyidagi misolda ko’rsatilgan.
Misol. Fibonachchi qatori a`zosining qiymatini topish uchun rekursiyani
qo’llanilishiga misol.
# include
int fib(int n) ;
int main( )
{
int n, javob;
cout « "Izlanayotgan nomerni kiriting:";
cin » n;
cout « "\n\n";
javob=fib(n);
cout«"Fibonachchi qatorining"« n «”nomeri qiymati " «javob«”ga teng \n";
return 0; }
int fib(int n)
{
cout « "fib("« n « "; jarayoni..';
if (n <3)
{
cout« "1 qiymatni qaytarayapti ! "\n;
return (1) ; }
else
{
cout« "fib(" « n-2 « ") va fib(" «n-1
cout« ") funktsiyalari chaqirayapti . \n";
return(fib(n-2)+fib(n-1)); } }
Dastur bajarilishidan keyingi natija:
Izianayotgan nomerni kiriting: 5
fib(6) ... fib(4) va fib(5) funktsiyalarini chaqirayapti.
fib(4) ... fib(2) va fib(3) funktsiyalarini chaqirayapti.
fib(2)…1 qiymatni qaytarayapti!
fib( 3)…fib(2) va fib(l) funktsiyalarini chaqirayapti.
fib(2)…1 qiym'atni qaytarayapti!
fib(2)….1 qiymatni qaytarayapti
fib(5) … fib(3) va fib(4) funktsiyalarini chaqirayapti.
fib(3)…. fib (2) va fib(l) funktsiyalarini chaqirayapti.
fib(l) … 1 qiymatni qaytarayapti!
fib(2) ... 1 qiymatni qaytarayapti
fib(4) … fib(2) va fib(3) funktsiyalarini chaqirayapti.
fib (2) ... 1 qiymatni qaytarayapti
fib(3) ... fib (2) va fib(1) funktsiyalarini chaqirayapti.
fib(1) ... 1 qiymatni qaytarayapti!
fib (2) ... 1 qiymatni qaytarayapti.
Fibonachchi qatorining 6 nomeri qiymati 8 ga teng.
Ayrim kompilyatorlar cout ob`ekti qatnashgan ifodalarda operatorlarni qo’llashda
ba`zi qiyinchiliklar paydo bo’ladi. Agarda kompilyator 28 satrdagi ifoda haqida
ogohlantirsh bersa ayirish operatsiyasini qavs ichiga oling, bu qator quyidagi
ko’rinishga ega bo’lsin:
cout « "Call fib(" <<(n-2)«") and fib(" «(n-2)« " ) \n” ;
Do'stlaringiz bilan baham: | 
