Algoritm tushunchasi. Hisoblanuvchilik. Primitiv rekursiv funksiyalar. Qisman rekursiv va rekursiv funksiyalar

2.Primitiv (o’ta sodda) rekursiya sxemasi


va funktsiyalar berilgan bo’lsin.
Quyidagi tengliklarni qanoatlantiruvchi yangi f funktsiyani ko’ramiz:
,
(1)
Bu yerda argumentga, - argumentga va - argumentga bog’liq funksiyalar.

5-ta'rif. Agar funktsiya va funktsiyalardan (1) munosabat orqali hosil etilsa, u holda funktsiya va funktsiyalardan primitiv (o’ta sodda) rekursiya sxemasi orqali hosil etilgan deyiladi.
Agar va funktsiyalar intuitiv hisoblanuvchi funktsiyalar bo’lsa, u holda f ham intuitiv hisoblanuvchi funktsiya bo’ladi.
Haqiqatan ham, argumentlarning qiymatlar majmuasi bo’lsin. U vaqtda ketma-ket quyidagilarni topamiz:
,
,
va hokazo.
Ravshanki, agar va funktsiyalar argumentlarning barcha qiymatlarida aniqlangan bo’lsa, u holda f funktsiya ham argumentlarning barcha qiymatlarida aniqlangan bo’ladi.
Endi misollarda primitiv rekursiya sxemasi orqali yangi funktsiyalarni hosil etishni ko’raylik.
1-misol. va bo’lsin hamda funktsiya quyidagi tengliklar orqali aniqlansin:
(2)
funktsiyaning qiymatini argumentlarning , qiymatlarida hisoblab chiqaylik. bo’lganligi uchun (2) formulalarning ikkinchisidan ketma-ket ravishda quyidagilarni hosil qilamiz:

ekanligini osongina ko’rsatish mumkin. Haqiqatan ham, . Bu tenglikda deb qabul qilib, yoki ni hosil qilamiz.
2-misol. funktsiya quyidagi tengliklar bilan berilgan deylik:


(3)
Bu yerda , bo’ladi.
funktsiyaning qiymatini argumentlarning , qiymatlari uchun hisoblaymiz.
bo’lganligi uchun bo’ladi. Funktsiyaning va qiymatlarini ketma-ket topamiz:

Bu misolda ekanligini ko’rsatish mumkin. Haqiqatan ham, . Bu tenglikda deb qabul qilib, yoki ni hosil qilamiz.