Mustaqil ish-5 Mavzu: Shablonfunksiyalardafunksiyalarniqaytayuklashmexanizmi

8-§. REKURSIYA
8.1. Rekursiya tushunchasi
109

hodisasi ro‘y bermoqda. C ho‘kish jarayoni boshlang‘ich holat sodir 

b o ‘lgunga qadar, y a’ni 1! gacha davom etadi. Shundan keyin, “ch o‘- 
kish” jarayoni to‘xtaydi, 1!=1 ekanligi haqida k o ‘rsatma olgan kom ­
pyuter yuqoriga qarab “suzib” chiqish bosqichini boshlaydi. Y a’ni, 
2!=1, 2!=l-2=2, 3 !=2!-3=6 va hokazo. Bu holat to N\ hisoblan- 
maguncha davom etaveradi.
Yuqorida keltirilgan jarayon dasturi quyidagicha yoziladi:
# include  
longfak(int m)
{ longf;
i f ( m = = l ) f —1; elsef=fak(m -l)*m ; 
return f;
}
void main()
{
int n;
cout «  “Butun sonni kiriting ”■
c i n » n ;
c o u t« fa k (n );
return;
}
N=4 uchun “cho‘kish” va “suzib chiqish” jarayoni quyidagicha:
N  ning 
qiymatlari
4
4 
3 
2 
1
Rekursiyadan 
chiqishdagi oraliq 
qiymatlar
N= 1 
sharti 
natijasi
Y o‘q 
yo‘q yo‘q 
ha
\ f a k (  3)*4 
\ f a k (  2)*3 
\
fak( 1)*2 
1
p : = p * 4=24 A 
p := p * 3 = 6  
p : = p * 2=2 
^ .= 1
no

Demak, EHM N=4 bo ‘lgan hoi uchun 24 natijani beradi.

Shunday m asalalar sinfi mavjudki, ularni rekursiyadan foydaian- 
may turib yechishning boshqa usullari yo‘q.
Masala. f ( n )  funksiyaning qiymatlari /(0 ) = 1 , f(2 n )= f{n ) va 
f (2 n + \)= f (ri)+\ ifodalar yordamida topiladi. Berilgan A: natural soni 
uchun f(k) ni toping.