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.
Dostları ilə paylaş: |
