Kompyuter injinering

int fact(int k) 
 { 
 if (k==1) 
return 1; 
 else 
return k * fact(k-1); 
 // 5*fact(4); 
 // fact(4) = 4* fact(3); 
 // fact(3) = 3 * fact(2); 
 // fact(2) = 2 * fact(1); 
 // fact(1) = 1
 } 
Matematikada rekursiya. 
Matematikada rekursiya funksiyalar va sonli qatorlarning aniqlanish 
metodlariga nisbatan qo’llaniladi: rekursiv ravishda berilgan funksiya o'z qiymatini 
boshqa argumentlar bilan chaqirish orqali aniqlanadi. Bundan holda ikkita variant 
mavjud: 
- Tugallangan (sonli) rekursiv funksiyalar. Bunday funksiyalar chekli sondagi 
rekursiv murojaat (chaqiruv) uchun ixtiyoriy sonli argumentda rekursiyasiz 
hisoblanadigan alohida aniqlanuvchi xususiy hollardan biriga olib kelish orqali 
beriladi. Klassik misol: manfiy bo’lmagan butun sonning rekursiv aniqlanishi: 
 
Bu yerda har bir keyingi rekursiv chaqiruvda argument bir birlikka 
kichiklashadi. Ya’ni, aniqlanishi bo’yicha manfiy bo’lmagan butun sonning 
faktorialini hisoblovchi funksiya argumenti n ga rekursiv murojaat qilishi 0!=1 
xususiy holatga kelganda hisoblashni to’xtatadi. Shunday qilib, rekursiv 
aniqlanishiga qaramasdan, ixtiyoriy argument uchun bu funksiya aniqlanish 
sohasida tugallangan funksiya bo’ladi. 
- Cheksiz rekursiv funksiyalar. Bunday funksiyalar barcha hollarda (hech 
bo’lmaganda ba’zi argumentlar uchun) o’z-o’ziga murojaat ko’rinishida beriladi. 
Misol sifatida cheksiz sonli qatorlar, cheksiz davomli kasrlar va boshqalarni olish 
mumkin. Amaliyotda bunday hollarda aniq qiymatni hisoblashning tabiiyki imkoni 
yo’q, ya’ni cheksiz vaqt talab etadi. Talab qilingan natijalar analitik usullarda 
topiladi. Shunga qaramay, agar absolyut aniq qiymatni olish haqida emas, balki 
kerakli (talab qilingan) qiymatning berilgan yaqinligini hisoblash haqida 

---

gapiradigan bo'lsak, unda ba'zi hollarda to'g'ridan-to'g'ri rekursiya ta'rifidan 
foydalanish mumkin: bunday holda kerakli (talab qilingan) aniqlikka 
erishmaguncha hisoblash davom ettiriladi. Bu kabi funksiyaga misol sifatida Eyler 
sonining matematik yoyilmasini olish mumkin: 
Bu yerda 
Yuqoridagi formuladan foydalangan holda to'g'ridan-to'g'ri hisoblash cheksiz 
rekursiyani keltirib chiqaradi, lekin n ning o’sib borishi bilan f(n) ning qiymati birga 
yaqinlashishi (intilishi)ni isbotlash mumkin (shuning uchun qatorning cheksizligiga 
qaramay, Eyler sonining qiymati chekli bo’ladi). Eyler soni e-ning qiymatini 
taxminiy hisoblash uchun rekursiya chuqurligini oldindan ma'lum bir songa sun'iy 
ravishda cheklash va unga erishilganda f(n)-ning qiymatiga birni ta’minlash yetarli 
bo’ladi. 
Matematikada rekursiyaga yana bir misol sifatida rekurrent formula bilan 
berilgan sonli qatorlarni olish mumkin. Bunday qatorlarning har bir keyingi hadi 
o’zidan oldingi n ta hadga bog’liq funksiya natijasi bilan aniqlanadi. 
Shunday qilib, cheklangan ifoda yordamida cheksiz qator aniqlanishi mumkin 
(bu ketma-ketlikning birinchi n hadlari uchun takrorlanadigan (rekurrent) formula 
va qiymatlar to'plamining kombinatsiyasi bo’ladi). 
Matematik induksiya rekursiya bilan chambarchas bog'liq: bu natural sonlar 
bo'yicha o’zining kichik qiymatlari orqali berilgan rekursiv funksiya xususiyatlarini 
isbotlashning tabiiy usuli hisoblanadi.