Rekursiv algoritmlar. Rekursiya haqida tushincha

double

expo(double a, intzn)  

{ifz(n==0) return 1;  

ifz(a==0.0)zreturnz0;  

intzk=(n>0)?zn:-n;  

for(doublezs=1.0,int i=0;i 

ifz(n>0)zreturnzszelse return 1/s;  

}  <>

Rekursiyaga misol sifatida sonni satr shaklida chiqarish masalasini ko’rib 

chiqamiz. Son raqamlari teskari tartibda hosil bo’ladi. Birinchi usulda raqamlarni 

massivda saqlab so’ngra teskari tartibda chiqarishdir.  

Rekursiv usulda funktsiya har bir chaqiriqda bosh raqamlardan nusxa olish 

uchun o’z o’ziga murojaat qiladi, so’ngra oxirgi raqamni bosib chikaradi.  

printd(n) 

int n;  

(  

int i;  

if (n < 0)  

cout<<'-';  

n = -n;  

if ((i = n/10) != 0)  


printd(i);  

cout<<="" b=""> 

)  

printd(123) chaqirishda birinchi funktsiya printd N = 123 qiymatga ega. U 12 

qiymatni ikkinchi printd ga uzatadi, boshqarish o’ziga qaytganda 3 ni chikaradi.  

Na’muna misol:  

#include  

using namespace std;  

float f1(float z)  

{ float a=3.246;  

cout<<" formula 1 ";  

return z*z-a;  

}  

float f2(float z)  

{ float b= 6.46;  

cout<<" formula 2 ";  

return z*z*z-b;  

}  

float ffor(float xn,float xk,float h)  

{ float x,y;  

for(x=xn;x<=xk;x+=h)  

{ if (x<3.0) y=f1(x);else y=f2(x);  

cout<< x<<” “<< y<<"\n" ; }  

return 0;  

}  

void fwhile(float xn,float xk,float h)  

{ float x,y;  

x=xn;  

while(x<=xk)  

{ if (x<3.0) y=f1(x);else y=f2(x);  

cout< 

x+=h;}  

}  

void fdo(float xn,float xk,float h)  

{ float x,y;  

x=xn;  

do  

{  

if (x<3.0) y=f1(x);else y=f2(x);  

cout<< x<<” “<< y<<"\n" ;  

x+=h;  

}  

while(x<=xk);  

}  

int main()  



{float xn,xk,h,y;  

int n;  

xn=1.7; xk=5.3; h=0.4;  

clrscr(); puts("vvedi--1,esli for");  

puts("vvedi--2,esli while");  

puts("vvedi--3,esli do");  

cin>>n;cout<<"\n";  

if (n== 1) ffor(xn,xk,h); //sikl s parametrom  

if (n== 2) fwhile(xn,xk,h); //sikl s predusloviem  

if (n== 3) fdo(xn,xk,h); //sikl s postusloviem  

getch();  

}        

Rekursiv triada.

• 
  Rekursiya bazasi (asosi) – masala yechimi aniq bo’lgan trivial holat aniqlanadi, ya’ni bu holatda funksiyani o’ziga murojat qilishi talab etilmaydi.;
  
• 
  Dekompozitsiya – umumiy holatni nisbatan ancha oddiy bo’lgan o’zgargan parametrli qisim masalalar orqali ifodalaydi.
  
• 
  Parametrizatsiya qilish – masala shartini tasniflash va uni hal etish uchun parametrlar aniqlanadi;
  

Izoh: Rekursiv yoki interatsion usul samaradorligi berilgan masalani hal qiluvchi dasturni turli boshlang’ich qiymatlarda tahlil etish orqali aniqlaydi.

Rekursiv algoritmlarni samaradorligini oshirish ko’pincha triada bosqichlarini qayta ko’rib chiqish natijasida amalga oshirish mumkin.

Faktorialini xisoblash:


Rekursiv triada:

Parametrizatsiya:

n – номанфий бутун сон.

Rekursiya bazasi:

n =0 ва n =1 учун факториал 1 га тенг.

Dekompozitsiya:

n!=(n-1)!*n.

n!=1*2*…*n=n*(n-1)!

int i,m,N; double long fact;

void factorial(int m);

void main()

{

clrscr();

cin>>N;

fact=1; factorial(N);

}

void factorial(int m)

{ if(m==1)

{cout<

getch();

exit(1); }

fact*=m; factorial(m-1); }

Daraxt tushunchasi.

Daraxt-bu chiziqsiz bog’langan ma’lumotlar.



Daraxt o’zining quyidagi belgilari bilan tasniflanadi:

• 
  Daraxtda shunday bitta element borki, unga boshqa elementlardan murojat yo’q. Mazkur elementga daraxt ildizi deyiladi;
  
• 
  Daraxtda ixtiyoriy elementga chekli sondagi ko’rsatgichlar yordamida murojat qilish mmkin;
  

Daraxtning har bir elementi faqatgina o’zidan oldingi kelgan bitta element bilan bog’langan. Daraxtning har bir tuguni orqali yoki terminal (barg) bo’lishi mumkin.

Daraxt bosqichlari soniga daraxt balandligi deyiladi

Chiqish darajalari :



Tugunlardan chiqayotgan shohlar soni tugundan chiqish darajasi deyiladi.

Daraxtlarni tavsiflash

Mantiqiy tasvirlashda daraxtlar bog’langan ro’yhatlar ko’rinishda ifodalanadi. Bunda ro’yhat elementi tugun qiymati va chiqish darajasini o’z ichiga oluvchi informatsion maydonga hamda chiqish darajasiga teng bo’lgan ko’rsatkichlar maydoniga ega bo’ladi.


Daraxt grafik va chiziqsiz ro’yhat shaklidagi tasvirlanishi.
Xulosa: Algoritm va dasturlarni tuzishda rekursiyadan foydalanish vaqtni tejaydi, hajmi kichik bo’ladi, lekin interaksion usulga nisbatan dastur sekinroq ishlaydi hamda ko’proq hotira talab qiladi.

Aslini olganda, har qanday rekursiv ishlangan masalani iterativ usulda ishlash

mumkin va buning aksi ham to'g'ri. Buning ustiga rekursiv yechim har doim

xotiradan qo'shimcha joy talab qiladi.

Shunday ekan, nima uchun unda rekursiya kerak? Albatta, buning yetarlicha

sabablari bor: Rekursiya deyarli hamma joyda ishlatiladi. Ya'ni, lo'nda qilib

aytganda undan qochib qutilishning iloji yo'q. Harakat qilib ko'rish esa qimmatga

tushishi aniq. 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.

Foydalanilgan adabiyotlar:

1. 
   A. M. Polatov ALGORITMLAR VA C++ TILIDA DASTURLASH ASOSLARI (O‘quv qo‘llanma) Toshkent “Universitet” 2017 yil;
   
2. 
   M.O‘. ASHUROV, SH.A. SATTAROVA, SH.U. USMONQULOV ALGORITMLAR TOSHKENT 2018 yil;
   
3. 
   A.R. AZAMATOV ALGORITMLASH VA DASTURLASH ASOSLARI To‘rtinchi nashri Cho 'lpon nomidagi nashriyot-matbaa ijodiy uyi Toshkent — 2013 yil;
   
4. 
   www.ziyouz.com kutubxonasi.