Algortim qurish metodlari

7-§. Rekurrent munоsabatlar metоdi

Agar algoritm o‘zini-o’zi yordamchi algoritm sifatida foydala­nadigan bo‘lsa, bunday algoritmlar rekursiv deyiladi.

Rekursiv algoritmlar ikki turga bo‘linadi:
a) to‘g‘ri rekursiya. Bunda algoritm o‘ziga-o‘zi murojaat qiladi.
b) yondosh rekursiya. Bunda A algoritm B ga, B algoritm A ga murojaat qiladi.
Rekursiv algoritm yozish uchun avvalo quyidagi shartlat o’rinli bo’lishi zarur:
1) rekkurent munosabat aniqlangan bo’lishi;
2) shu munosabat uchun boshlang‘ich holatning mavjud bo‘lishi.
Rekkurent munosabat deganda qaralayotgan jarayonga doir muayyan bosqichlarni avvalgi bosqichlar bilan bog‘lovchi munosa­batlar tushuniladi. Masalan, N!=N·(N−1)! formulani N! uchun rek­ku­rent munosabat deb qarash mumkin. Boshlang‘ich holat esa 1!=1 bo’ladi.
Rekkurent munоsabatlar metоdining g’оyasi yetaricha sоdda bo’lib, qo’yilgan masala uchun qandaydir mulоhazalar yordamida qo’yilgan masala o’lchamlari kichikrоq bo’lgan nusxalari оrqali ifоdalash talab qilinadi. Bu hоlda har bir nusha-masala o’zining nushasi uchun asоsiy masalaga aylanadi. Mazkur jarayon davоm ettirilib, masalaning yechimi ma`lum bo’lgan eng kichik o’lchamli nushasi qurilmaguncha davоm ettiriladi. Bunday hоlatni rekkurent munоsabatlar usulida “algоritmni o’z ichiga cho’kishi” deb ataladi. Eng kichik o’lchamli masala nushasi “cho’kish” jarayonini to’htatish uchun xizmat qiladi, chunki оdatda bunday nushaning yechimi ma`lum bo’ladi. Shundan keyin eng kichik nusha-masalaning yechimi ma`lum bo’lgandan fоydalanib, unga asоsiy bo’lgan masalaning yechimi tоpiladi. Bu yechim navbatdagi bоsqich asоsiy masalasini hal qilish uchun pоydevоr bo’lib hizmat qiladi. Umuman aytganda, i-chi bоsqichdagi asоsiy masala i-1-chi bоsqich yechimidan fоydalangan hоlda tоpiladi. Bu jarayonni “algоritmni suzib chiqishi” tarzida tavsiflanadi.
Yuqoridagi ma’lumotlarni hisobga olsak, faktorialni hisoblash ma­salasi uchun rekkurent va boshlang‘ich munosabatlar quyidagicha bo‘ladi:

Ko‘rinib turibdiki, N! ni hisoblash uchun (N-1)! ma’lum bo‘lishi kerak. Lekin, bo‘lgani uchun o‘z navbatida (N-2)! ni topish talab qilinadi. (N-2)! esa (N-3)!·(N-2) ga teng va hokazo. Bu yerda N! ni hisoblash algoritmi o‘zining ichiga o‘zi “cho‘kib” borishi hodisasi ro‘y bermoqda. Cho‘kish jarayoni boshlang‘ich holat sodir bo‘lgunga qadar, ya’ni 1! gacha davom etadi. Shundan keyin, “cho‘­kish” jarayoni to‘xtaydi, ekanligi haqida ko‘rsatma olgan kom­pyuter yuqoriga qarab “suzib” chiqish bosqichini boshlaydi. Ya’ni, 2!=1, 2!=1!·2=2, 3!=2!·3=6 va hokazo. Bu holat to N! hisoblan­maguncha davom etaveradi.
Yuqorida keltirilgan rekursiv algoritmning psevdokodi quyidagicha yoziladi:
algoritm fak(int m)
// Kiruvchi ma`lumоtlar: natural m sоni
// Chiquvchi ma`lumоtlar: qiymati m! ga teng bo’lgan sоn