Dasturlash I 12-hafta mavzu: Rekursiv funksiyalar

14.2. Misol: Faktoriallar
Key Point. Rekursiv funksiya – o`zini-o`zi chaqiruvchi yagona funksiya.
Ko`pgina matematik funksiyalar rekursiyadan foydalangan holda hisoblanadi. Demak, ishni rekursiyani o`zida ifodalovchi, oddiy bir misolni ko`rib chiqishdan boshlaymiz. n sonining faktorialini quyidagicha ko`rinishda, rekursiv hisoblash mumkin:
0! = 1;
n! = n × (n - 1)!; n > 0
Berilgan n, soni uchun, n! ni qanday hisoblash mumkin? Bilamizki, 1! Ni topish juda oson. Chunki, 0! = 1 va 1! = 1x0!. (n-1)! ni inobatga olib, n! ni n*(n-1)! Deb hisoblashimiz mumkin bo`ladi. Shu tarzda hisoblash qadamlarini (n-1)! ga kamaytiramiz. (n-1)! ni hisoblashni barcha qadamlar uchun, n 0 ga teng bo`lgunga qadar, rekursiv ko`rinishda qo`llashimiz mumkin.
Keling, factorial(n) – n! ni hisoblash funksiyasi bo`lsin. Agar funksiyani n=0 bilan chaqirsak, u birdaniga natija qaytaradi. Chunki, funksiya asosiy qism yoki to`xtash shartlarini ifodalovchi oddiy hollar uchun masalani qanday yechish kerakligini yaxshi biladi. Agar funksiyani n=0 bilan chaqirsak, u n-1 ning faktorialini hisoblash uchun quyi pog`onali masala deb tavsiflanuvchi qismni yechishga o`tadi. Quyi pog`onali masala ham alohida masala hisoblanadi, biroq u originaliga qaraganda biroz kichikroq va soddaroq bo`ladi. Har qanday quyi pog`onali masalaning ham o`z xususiyatlari mavjud bo`ladi. Biz bunday funksiyalarni rekursiv chaqiriluvchi, turli argumentlarga ega funksiya deb atashimiz mumkin.
factorial(n) ni hisoblash uchun rekursiv algoritmni soddagina qilib, quyidagicha yozishimiz mumkin:
if(n == 0)
return 1;
else
returnn * factorial(n - 1);
Rekursiv chaqirish bir qancha rekursiv chaqirishlarni sodir etishi mumkin, chunki, funksiya quyi pog`onali masalani bir nechta quyi pog`onali masalalarni hisoblash orqali hisoblaydi. Rekursiv funksiya ishini to`xtatishi uchun masala so`nggi hisoblash holatiga qadar qayta ko`rib chiqilaverishi kerak. So`nggi hisoblash holatida funksiya uning chaqiruvchisiga qiymat qaytaradi, qiymatni qabul qilib olgan funksiya esa, o`zining chaqiruvchisiga qiymat yuboradi. Bu jarayon original (asosiy) masalaga qiymat yuborilguncha davom etadi. Va nihoyat, original masala