Ўзбекистон республикаси ахборот технологиялари ва коммуникацияларини ривожлантириш вазирлиги муҳаммад ал-хоразмий номидаги

РЕКУРСИВ ДАСТУРЛАШНИ ФОРМАЛЛАШТИРИШ 
Р.В. Қобулов (илмий ходим, Муҳаммад ал-Хоразмий номидаги ТАТУ) 
О.М.Бегимов (ассистент, Муҳаммад ал-Хоразмий номидаги ТАТУ) 
Рекурсив дастурлаш механизми замонавий дастурлашда мухим 
ахамиятга эга.Хусусан шаблонли метадастурлаш рекурсия механизмига 

---

399 
асосланган. Ишдан мақсад рекурсив дастурлашни умумлашган холда 
тасвирлашдан иборат. 
Рекурсия. Примитив рекурсив функциялар классик таърифини 
келтирамиз. 
1. Алфавит. 
а) предмет символлар 𝒂, 𝒃, 𝒙, 𝒚, 𝒂
𝟏
, 𝒃
𝟏
, 𝒙
𝟏
, 𝒚
𝟏
; 
б) функционал символлар +, −,∙.
в) техник символлар (, ). 
2. Термлар 
Предмет символлар; 
Агар 𝒕
𝟏
, 𝒕
𝟐
, … , 𝒕
𝒑
термлар ва 
𝝋 функционал символ, у холда 
𝝋(𝒕
𝟏
, 𝒕
𝟐
, … , 𝒕
𝒑
) – терм; 
Бошқа термлар йўқ. 
3. Аксиомалар: 
а1) 𝑺(𝒙) = 𝒙 + 𝟏; 
а2) 𝑶(𝒙) = 𝟎; 
а3) 𝑰 
𝒎
𝒏
(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
) = 𝒙
𝒎
. 
4. Чиқариш қоидалари
в1) 𝒇(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
) = 𝝋(𝒇
𝟏
(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
), … , 𝒇
𝒎
(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
)); 
в2) 𝒇(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
, 𝟎) = 𝒈(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
), 
𝒇(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
, 𝒚 + 𝟏) = 𝒉(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
, 𝒚, 𝑭(𝒙
𝟏
, 𝒙
𝟐
, … , 𝒙
𝒏
, 𝒚)). 
Функциялар 𝑺, 𝑶, 𝑰 
𝒎
𝒏
содда функциялар дейилади. Чиқариш қоидаси 
в2 да 𝒇 функция 𝒈 ва 𝒉 функциялардан примитив рекурсия ёрдамида 
чиқарилади дейилади. Функция 𝒇 чекли сондаги ўрнига қўйиш ва примитив 
рекурсия амаллари ёрдамида 𝑺, 𝑶, 𝑰 
𝒎
𝒏
содда функциялардан келтириб 
чиқарилса примитив рекурсив дейилади.” 
Умумлашган рекурсия.Умумлашган рекурсив функцияларни кўрамиз 
Авваламбор терм тушунчасини кенгайтирамиз: 
Агар 𝒂, 𝒃 терм бўлса қуйидагилар хам терм 
𝒂 + 𝒃, 𝒂 − 𝒃, 𝒂 ∗ 𝒃, 𝒂/𝒃 
Агар 𝒂, 𝒃 терм бўлса қуйидагилар мантиқий терм 
𝒂 < 𝒃, 𝒂 > 𝒃, 𝒂 ≥ 𝒂, 𝒂 ≤ 𝒃, 𝒂 ≡ 𝒃 
Агар 𝒂, 𝒃 мантиқий терм бўлса қуйидагилар мантиқий терм 
𝒂&𝒃, 𝒂 ∨ 𝒃, ~𝒂 
Бундан ташқари шартли терм киритилади 
Агар 𝑹 мантиқий терм 
𝑓, 𝜑
–терм бўлса қуйидаги хам терм 
𝒊𝑓(𝑅(𝑥)) 𝑡ℎ𝑒𝑛 𝑓(𝑥) 𝑒𝑙𝑠𝑒 𝜑(𝑥); 
Шартли терм қуйидаги терм билан алмаштириш мумкин лекин унга 
эквивалент эмас:
𝑅(𝑥) ∗ 𝑓(𝑥) + (1 − 𝑅(𝑥) ∗ 𝜑(𝑥) 
Чунки шартли терм қуйидагича хисобланади: 
{
𝑓(𝑥) 𝑅(𝑥)
𝜑(𝑥) ~𝑅(𝑥)

---

400 
Бундан ташқари вергуль билан ажратилган қуйидаги кетма кетликдан 
фойдаланамиз: 
𝑎
1
= 𝑡
1
(𝑎
0
), … , 𝑎
𝑛
= 𝑡
𝑛
(𝑎
0
, … , 𝑎
𝑛−1
) 
Бундай кетма кетликни ягона термга келтириш мумкин.
Умумлашган рекурсив қоидаси деб қуйидаги қоидага айтилади 
𝜑(𝑥) = 𝑖𝑓(𝑅(𝑥)) 𝑡ℎ𝑒𝑛 𝑓(𝑥) 𝑒𝑙𝑠𝑒 𝜑(𝑡(𝑥)); 
Ёки 
𝑓(𝑥) = 𝑖𝑓(𝑅(𝑥)) 𝑡ℎ𝑒𝑛 𝑓(𝑡(𝑥)) 𝑒𝑙𝑠𝑒 𝜑(𝑥); 
Бу қоидалар ёрдамида аниқланган функция умумлашган рекурсив 
функция дейилади. 
Дихотомия усули учун функция: 
𝑫𝒕(𝒂, 𝒃) = ( 
𝒄 = (𝒂 + 𝒃)/𝟐, 
𝑰𝒇(𝒂𝒃𝒔(𝒇( 𝒄)) < 𝒆𝒑𝒔) 𝒕𝒉𝒆𝒏 𝒄 𝒆𝒍𝒔𝒆
𝒊𝒇(𝒇(𝒂) ∗ 𝒇(𝒄) < 𝟎) 𝒕𝒉𝒆𝒏 𝑫𝒕(𝒂, 𝒄) 𝒆𝒍𝒔𝒆 𝑫𝒕(𝒄, 𝒂) 
); 
Ньютон усули учун функция:
𝑵𝒕(𝒙) = ( 
𝑰𝒇(𝒂𝒃𝒔(𝒇(𝒙)) < 𝒆𝒑𝒔) 𝒕𝒉𝒆𝒏 𝒙 𝒆𝒍𝒔𝒆
𝑵𝒕(𝒙 − 𝒇(𝒙)/𝒇’(𝒙) 
); 
Итерация усули учун функция: 
𝑰𝒕(𝒙) = ( 
𝒊𝒇(𝒂𝒃𝒔(𝒇(𝒙)) < 𝒆𝒑𝒔) 𝒕𝒉𝒆𝒏 𝒙 𝒆𝒍𝒔𝒆
𝑰𝒕(𝒇(𝒙)) 
); 
Метадастурлаш. Шаблонлар инстанционирлаш механизми компиляция 
жараёнида хисоблашни ташкил этишга имкон беради[2-5]. Бундай 
хисоблашлар шаблонли метадастурлаш деб аталади (iterator traits). Шаблонли 
метадастурлашдан фойдаланиб тузилган дастур шаблонли метадастур 
дейилади (template metaprogram).Шаблонли метадастур икки қисмдан иборат. 
Биринчи шаблонда умумий рекурсив қоида жорий этилади. Иккинчи шаблон 
— рекурсия тугатувчи специализация. Унда ўзгарувчи бошланғич қиймати 
берилади.
Қуйидаги дастурда компиляция жараёнида 3 сони берилган даражага 
кўтариш кўрсатилган. 
Мисол: 
Pow3< N> = 3 * Pow3;
//Рекурсия тугатиш
Pow3<0> = 1 ;
Цикл ёйиш учун метадастурлар. Метадастурлаш кенг қўлланиладиган 
амалий масала сонли хисоблашда циклларни ёйиш масаласидир. 

---

401 
Векторларни 
скаляр 
кўпайтмасини 
хисоблаш 
масаласини 
кўрамиз.Скаляр кўпайтмани цикл оператори ёрдамида эмас қуйидаги сумма 
шаклида ҳисоблаш самарали: