Типографияга 23-12 алгоритмлар ва С++

Rekursiyaga oid algoritmlar

Hisoblash jarayonida ba’zi bir algoritmlarning o‘ziga qayta murojaat qilishiga to‘g‘ri keladi. O‘ziga–o‘zi murojaat qiladigan algoritmlarga rekurrent algoritmlar yoki rekursiya deb ataladi.

1. 
   misol. Bunday algoritmga misol sifatida Fibonachchi sonlarini keltirish mumkin [2, 59 b.]. Ma’lumki, Fibonachchi sonlari quyidagicha aniqlangan: a₀=a₁=1, a_i=a_i-1+a_i-2, i=2,3,4,…. Bu rekurrent ifoda algoritmiga mos keluvchi blok-sxema 1.23-rasmda keltirilgan. Eslatib o‘tamiz, bu erda formuladagi i- indeksga hojat yo‘q, lekin agar Fibonachchi sonining nomerini ham aniqlash zarur bo‘lsa, birorta qo‘shimcha parametr kiritish kerak bo‘ladi.
   

1.23-rasm. Fibonachchi sonlarining n- hadini hisoblash blok-sxemasi.

2. 
   misol.
   

n

x
S  _ ⁱ
munosabatni hisoblang.

_i1 (2i  i)!
Bunda i indeksning har bir qiymatida faktorial va yig‘indini hisoblash taqozo etiladi. Shuning uchun avval faktorialni hisoblashni alohida ko‘rib chiqamiz. Quyidagi rekkurent ifoda faktorialni kam amal sarflab qulay usulda hisoblash imkonini beradi:
(1) R=1; (2) R=R*2i*(2i+1).

Haqiqatan ham, i=1da 3! ni, i=2 da R=3!*4*5=5! ni va hokazo tarzda (2i1)! ni yuqoridagi rekkurent formula yordamida hisoblash mumkin bo‘ladi. Bu misolga mos keluvchi blok-sxemasi 1.24-rasmda keltirilgan.