Oʻzbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xozazmiy nomidagi toshkent axborot texnologiyalari

Rekursiv protseduralar

Faktorial

Rekursiv protseduraning klassik namunasi - hisoblash uchun ishlatiladigan funktsiya faktorial a tabiiy son:

Psevdokod (rekursiv):

funktsiya faktorial: kiritish: tamsayı n shu kabi n >= 0 chiqish: [n × (n-1) × (n-2) × … × 1] 1. agar n 0 ga teng, qaytish 1 2. aks holda, qaytish [ n × faktorial (n-1) ] oxiri faktorial

Funksiyani a shaklida ham yozish mumkin takrorlanish munosabati:

Takrorlanish munosabatini ushbu baholash yuqoridagi psevdokodni baholashda amalga oshiriladigan hisob-kitoblarni namoyish etadi:

N = 4 uchun takrorlanish munosabatini hisoblash:

b4 = 4 * b3 = 4 * (3 * b2) = 4 * (3 * (2 * b.)1)) = 4 * (3 * (2 * (1 * b.)0))) = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24

Ushbu faktorial funktsiyani, shuningdek, majburiy dasturlash tillarida mavjud bo'lgan odatiy tsikl konstruktsiyalaridan foydalangan holda rekursiyadan foydalanmasdan tasvirlash mumkin:

Psevdokod (iterativ):

funktsiya faktorial: kiritish: tamsayı n shu kabi n >= 0 chiqish: [n × (n-1) × (n-2) × … × 1] 1. yaratmoq deb nomlangan yangi o'zgaruvchi ishlaydigan_jami qiymati 1 ga teng 2. boshlash pastadir 1. agar n 0 ga teng, Chiqish halqa 2. o'rnatilgan ishlaydigan_jami ga (ishlaydigan_jami × n) 3. kamayish n 4. takrorlang pastadir 3. qaytish ishlaydigan_jami oxiri faktorial

Yuqoridagi majburiy kod akkumulyator o'zgaruvchisi yordamida ushbu matematik ta'rifga tengdir t:
Yuqoridagi ta'rif to'g'ridan-to'g'ri tarjima qilingan funktsional dasturlash tillari kabi Sxema; bu rekursiv ravishda amalga oshiriladigan iteratsiyaning misoli.

Eng katta umumiy bo'luvchi

The Evklid algoritmi, hisoblaydigan eng katta umumiy bo'luvchi ikki tamsayıdan, rekursiv yozish mumkin.
Funktsiyaning ta'rifi:

Psevdokod (rekursiv):

funktsiya gcd:kiritish: tamsayı x, tamsayı y shu kabi x > 0 va y >= 0 1. agar y 0 ga teng, qaytish x 2. aks holda, qaytish [gcd ( y, (qolgan qismi x/y) ) ] oxiri gcd

Takrorlanish munosabati eng katta umumiy bo'luvchi uchun qaerda  ifodalaydi qoldiq ning  :
agar 

X = 27 va y = 9 uchun takrorlanish munosabatlarini hisoblash:

gcd (27, 9) = gcd (9, 27% 9) = gcd (9, 0) = 9

X = 111 va y = 259 uchun takrorlanish munosabatlarini hisoblash:

gcd (111, 259) = gcd (259, 111% 259) = gcd (259, 111) = gcd (111, 259% 111) = gcd (111, 37) = gcd (37, 111% 37) = gcd ( 37, 0) = 37

Yuqoridagi rekursiv dastur quyruq-rekursiv; u iterativ algoritmga teng va yuqorida ko'rsatilgan hisoblash dumaloq qo'ng'iroqlarni bartaraf qiladigan til tomonidan amalga oshiriladigan baholash bosqichlarini ko'rsatadi. Quyida xuddi shu algoritmning aniq iteratsiyadan foydalangan holda versiyasi keltirilgan, bu dumaloq qo'ng'iroqlarni bartaraf etmaydigan til uchun mos keladi. O'z holatini butunlay o'zgaruvchilarda saqlab turish orqali x va y va ilmoqli konstruktsiyadan foydalanib, dastur rekursiv qo'ng'iroqlar qilishdan va qo'ng'iroqlar to'plamini ko'paytirishdan qochadi.

Psevdokod (iterativ):

funktsiya gcd: kiritish: tamsayı x, tamsayı y shu kabi x >= y va y >= 0 1. yaratmoq deb nomlangan yangi o'zgaruvchi qoldiq 2. boshlash pastadir 1. agar y nolga teng, Chiqish halqa 2. o'rnatilgan qoldiq x / y 3 ning qolgan qismiga. o'rnatilgan x dan y 4 gacha. o'rnatilgan y dan qoldiq 5. takrorlang pastadir 3. qaytish x oxiri gcd

Takrorlanuvchi algoritm vaqtinchalik o'zgaruvchini talab qiladi va hatto Evklid algoritmi haqida bilimga ega bo'lsak ham, oddiy tekshirish orqali jarayonni tushunish qiyinroq bo'ladi, garchi ikkala algoritm o'z bosqichlarida juda o'xshash.

Xanoy minoralari

Xanoy minoralari
Asosiy maqola: Xanoy minoralari
Xanoy minoralari - bu matematik jumboq bo'lib, uning echimi rekursiyani aks ettiradi.^[7][8] Har xil diametrdagi disklar to'plamini ushlab turadigan uchta qoziq mavjud. Kattaroq disk hech qachon kichkinagina ustiga qo'yilmasligi mumkin. Bilan boshlanadi n disklar bitta qoziqqa, ularni birma-bir boshqa qoziqqa o'tkazish kerak. Stekni siljitish uchun eng kichik qadamlar soni qanday?
Funktsiyaning ta'rifi:

Hanoy uchun takrorlanish munosabati: