“Rekursiv algoritmlar. Rekursiya ta’rifi. Bevosita (oddiy) va bilvosita (murakkab) rekursiya sxemalari. Rekursiv algoritmlarga misollar
![Mavzu: “Rekursiv algoritmlar. Rekursiya ta’rifi. Bevosita (oddiy) va
bilvosita (murakkab) rekursiya sxemalari. Rekursiv algoritmlarga
misollar”
Reja:
1. Kirish
2. Asosiy qism
A) Rekursiv algoritmlar haqida
B) Rekursiya ta’rifi
C) Bevosita va bilvosita rekursiya sxemalari
D) Rekursiv algoritmlarga misollar
3. Xulosa
4. Amaliy ish
5. Foydalangan Adobiyotlar](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_1.png)
![Kirish
Rekursiv algoritmlar Rekursiyaning mohiyati
Hisoblash jarayonida ba’zi bir algoritmlarning o‘ziga qayta murojaat qilishga to‘g‘ri
keladi. O‘ziga–o‘zi murojaat qiladigan algoritmlarga rekkurent algoritmlar yoki rekursiya
deb ataladi. Biron bir masalani yechishda, agar uni bir xil kichik yoki sodda masalaraga
bo‘lib bajarish mumkin bo‘lsa, bunday hollarda rekursiv algoritm qo‘llash
mumkin.Hayotda uchrovchi ba’zi masalalarni hal etish rekursiv algoritmlarni qo‘llash
orqali oson va intutitiv tarzda kechadi. Misol sifatida Fibonachi sonlari ketma-ketligi,
factorial hisoblash. Protsedura yoki funksiya boshqa protsedura yoki funksiyalarga
qo‘ng'iroqlarni o‘z ichiga olishi mumkin. Jumladan, protsedura o‘zini chaqirishi mumkin.
Bu erda hech qanday paradoks yo‘q - kompyuter faqat dasturda duch kelgan buyruqlarni
ketma-ket bajaradi va agar protsedura chaqiruviga duch kelsa, u shunchaki ushbu
protsedurani bajarishni boshlaydi. Buni amalga oshirish uchun qanday buyruq
berilganligi muhim emas. Rekursiv protseduraga misol: Procedure Rec(a: integer); a>
bo‘lsa boshlang Keling, asosiy dasturga, masalan, Rec(3) ko‘rinishdagi qo‘ng'iroqni
qo‘ysak nima bo‘lishini ko‘rib chiqamiz. Quyida bayonotlar bajarilish ketma-ketligini
ko‘rsatadigan oqim diagrammasi keltirilgan. Guruch. 1. Rekursiv protseduraning blok
diagrammasi. Rec protsedurasi a = 3 parametri bilan chaqiriladi. Unda a = 2 parametrli
Rec protsedurasiga qo‘ng'iroq mavjud. Oldingi qo‘ng'iroq hali tugallanmagan, shuning
uchun siz boshqa protsedura yaratilayotganini tasavvur qilishingiz mumkin va birinchisi
amalga oshiriladi. ishi tugaguniga qadar ishini tugatmaslik. Qo‘ng'iroq jarayoni parametr
a = 0 bo‘lganda tugaydi. Hozirgi vaqtda protseduraning 4 ta nusxasi bir vaqtning o‘zida
bajarilmoqda. Bir vaqtning o‘zida bajariladigan protseduralar soni chaqiriladi rekursiya
chuqurligi. (Rec(0)) deb nomlangan to‘rtinchi protsedura 0 raqamini chop etadi va
chiqadi. Shundan so‘ng, boshqaruv uni chaqirgan protseduraga qaytadi (Rec(1)) va 1
raqami chop etiladi va barcha protseduralar tugaguncha davom etadi. Dastlabki
qo‘ng'iroqning natijasi to‘rtta raqamni chop etadi: 0, 1, 2, 3. Nima sodir bo‘layotganining
yana bir vizual tasviri rasmda ko‘rsatilgan. 2. Guruch. 2. 3-parametr bilan Rec
protsedurasini bajarish 2-parametr bilan Rec protsedurasini bajarish va 3-raqamni chop
etishdan iborat. hokazo. O‘z-o‘zidan mashq sifatida, Rec(4) ga qo‘ng'iroq qilganingizda](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_2.png)
![nima sodir bo‘lishini ko‘rib chiqing. Quyida tasvirlangan Rec2(4) protsedurasini
chaqirganingizda nima sodir bo‘lishini ham ko‘rib chiqing, bu erda operatorlar teskari.
Protsedura Rec2(a: butun son); yozishni boshlash (a); agar a>0 bo‘lsa, Rec2(a-1); oxiri;
E'tibor bering, yuqoridagi misollarda rekursiv qo‘ng'iroq shartli bayonot ichida
joylashgan. bu zarur shart rekursiya abadiy tugashi uchun. Shuni ham yodda tutingki,
protsedura o‘zini chaqirilganidan boshqa parametr bilan chaqiradi. Agar protsedura
global o‘zgaruvchilardan foydalanmasa, bu rekursiya cheksiz davom etmasligi uchun
ham kerak. Biroz murakkabroq sxema bo‘lishi mumkin: A funktsiyasi B funktsiyasini
chaqiradi, bu esa o‘z navbatida A ni chaqiradi. Bu deyiladi murakkab rekursiya. Ma'lum
bo‘lishicha, birinchi bo‘lib tasvirlangan protsedura hali tasvirlanmaganini chaqirishi
kerak. Buning mumkin bo‘lishi uchun siz dan foydalanishingiz kerak. Protsedura A(n:
butun son); (Birinchi protseduraning oldinga tavsifi (sarlavhasi)) B protsedurasi (n: butun
son); (Ikkinchi protseduraning oldinga tavsifi) protsedura A(n: butun son); (To‘liq
protsedura tavsifi A) begin writeln(n); B(n-1); oxiri; B protsedurasi (n: butun son); (B
protsedurasining to‘liq tavsifi) begin writeln(n); ifn B protsedurasining oldinga e'lon
qilinishi uni A protsedurasidan chaqirish imkonini beradi. A protsedurasining oldinga
e'lon qilinishi bu misolda talab qilinmaydi va estetik sabablarga ko‘ra qo‘shilgan. Agar
oddiy rekursiyani uroborosga qiyoslash mumkin bo‘lsa (3-rasm), unda “Bo‘rilar qo‘rqib
bir-birini yeb qo‘ygan” nomli mashhur bolalar she’ridan murakkab rekursiya tasvirini
olish mumkin. Ikki bo‘ri bir-birini yeyayotganini tasavvur qiling va siz murakkab
rekursiyani tushunasiz. Guruch. 3. Ouroboros - o‘z dumini yutib yuboradigan ilon.
Teodor Pelekanosning "Sinoziy" alkimyoviy risolasidan olingan rasm (1478). Guruch. 4.
Murakkab rekursiya. 3. Rekursiya yordamida sikl ishini simulyatsiya qiling Agar
protsedura o‘zini o‘zi chaqirsa, unda, aslida, bu uning tarkibidagi ko‘rsatmalarning
takroriy bajarilishiga olib keladi, bu tsiklning ishlashiga o‘xshaydi. Ba'zi dasturlash
tillarida aylanma konstruktsiyalar umuman mavjud emas, bu esa dasturchilarni
rekursiyadan foydalangan holda takrorlashni tashkil qilishni qoldiradi (masalan, Prolog,
bu erda rekursiya asosiy dasturlash texnikasi). Masalan, for siklining ishini simulyatsiya
qilaylik. Buning uchun bizga, masalan, protsedura parametri sifatida amalga oshirilishi
mumkin bo‘lgan qadam hisoblagichi o‘zgaruvchisi kerak. 1-misol Protsedura](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_3.png)
![LoopImitation(i, n: integer); (Birinchi parametr - qadamlar soni, ikkinchi parametr -
qadamlarning umumiy soni) begin writeln("Salom N ", i); //Bu erda i bo‘lsa
takrorlanadigan har qanday gaplar LoopImitation(1, 10) kabi qo‘ng'iroq natijasi
hisoblagichni 1 dan 10 gacha o‘zgartirish bilan ko‘rsatmalarning o‘n marta bajarilishi
bo‘ladi. Bu holda u chop etadi: Salom N1 Salom N2 … Salom N 10 Umuman olganda,
protsedura parametrlari hisoblagich qiymatlarining o‘zgarishi chegaralari ekanligini
ko‘rish qiyin emas. Quyidagi misolda bo‘lgani kabi takrorlanadigan qo‘ng'iroq va
ko‘rsatmalarni almashtirishingiz mumkin. 2-misol Protsedura LoopImitation2(i, n:
integer); agar men boshlasam Bunday holda, ko‘rsatmalar bajarilishidan oldin protsedura
rekursiv chaqiriladi. Protseduraning yangi nusxasi, shuningdek, birinchi navbatda,
hisoblagichning maksimal qiymatiga erishgunimizcha, boshqa misolni chaqiradi va
hokazo. Shundan keyingina oxirgi chaqirilgan protseduralar o‘z ko‘rsatmalarini bajaradi,
so‘ngra oxirgisi o‘z ko‘rsatmalarini bajaradi va hokazo. LoopImitation2(1, 10) ni
chaqirish natijasi salomlashishni teskari tartibda chop etishdir: Salom N 10 … Salom N1
Agar biz rekursiv deb ataladigan protseduralar zanjirini tasavvur qilsak, u holda 1-
misolda biz undan oldingi protseduralardan keyingilariga o‘tamiz. 2-misolda, aksincha,
keyinroqdan oldingiga. Nihoyat, rekursiv qo‘ng'iroqni ikkita ko‘rsatmalar bloki orasiga
qo‘yish mumkin. Masalan: Protsedura LoopImitation3(i, n: integer); begin
writeln("Salom N", i); (Bu bayonotlarning birinchi bloki bo‘lishi mumkin) agar i Bu
yerda, birinchi navbatda, birinchi blokdagi ko‘rsatmalar ketma-ket bajariladi, keyin
ikkinchi blokning ko‘rsatmalari teskari tartibda bajariladi. LoopImitation3(1, 10) ga
qo‘ng'iroq qilganda biz quyidagilarni olamiz: Salom N1 … Salom N 10 Salom N 10 …
Salom N1 Rekursiyasiz xuddi shunday qilish uchun bir vaqtning o‘zida ikkita tsikl kerak
bo‘ladi. Xuddi shu protsedura qismlarini bajarish vaqt oralig'ida joylashganligidan
foydalanishingiz mumkin. Masalan: 3-misol: Sonni ikkilik sistemaga aylantirish. Ikkilik
sonning raqamlarini olish, ma'lumki, sanoq sistemasining asosiga qoldiqga bo‘lish yo‘li
bilan sodir bo‘ladi 2. Agar raqam bo‘lsa, uning ikkilik ko‘rinishidagi oxirgi raqami teng
bo‘ladi. 2 ga bo‘lishning butun qismini olish: biz bir xil ikkilik ko‘rinishga ega bo‘lgan,
ammo oxirgi raqamsiz raqamni olamiz. Shunday qilib, keyingi bo‘linish maydonida 0 ga
teng butun son bo‘lguncha yuqoridagi ikkita amalni takrorlash kifoya. Rekursiyasiz u](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_4.png)
![quyidagicha ko‘rinadi: x>0 esa c:=x mod 2 boshlanadi; x:=x div 2; yozish (c); oxiri; Bu
erda muammo shundaki, ikkilik vakillikning raqamlari teskari tartibda hisoblanadi (oxirgi
birinchi). Raqamni oddiy shaklda chop etish uchun siz massiv elementlaridagi barcha
raqamlarni eslab qolishingiz va ularni alohida tsiklda chiqarishingiz kerak bo‘ladi.
Rekursiya bilan massiv va ikkinchi siklsiz kerakli tartibda chiqishni olish oson. Aynan:
Protsedura BinaryRepresentation(x: integer); var c, x: integer; start (Birinchi blok.
Protsedura chaqiruvi tartibida bajariladi) c:= x mod 2; x:=x div 2; (Rekursiv chaqiruv)
agar x>0 bo‘lsa, BinaryRepresation(x); (Ikkinchi blok. Teskari tartibda ishlaydi)
yozish(c); oxiri; Umuman olganda, biz hech qanday yutuq olmadik. Ikkilik tasvirning
raqamlari mahalliy o‘zgaruvchilarda saqlanadi, ular rekursiv protseduraning har bir
ishlayotgan misoli uchun farq qiladi. Ya'ni xotirani saqlab bo‘lmadi. Aksincha, biz ko‘p
mahalliy o‘zgaruvchilarni saqlash uchun qo‘shimcha xotira sarflaymiz x. Shunga
qaramay, bunday yechim menga chiroyli ko‘rinadi. 4. Takroriy munosabatlar. Rekursiya
va iteratsiya Aytishlaricha, vektorlar ketma-ketligi, agar boshlang'ich vektor va keyingi
vektorning oldingisiga funktsional bog'liqligi berilsa, takrorlanish munosabati bilan
beriladi. Qaytalanish munosabatlari yordamida hisoblangan miqdorning oddiy misoli
faktorialdir Keyingi faktorialni avvalgisidan quyidagicha hisoblash mumkin: Belgini
kiritish orqali biz quyidagi munosabatni olamiz: Formula (1) vektorlari o‘zgaruvchan
qiymatlar to‘plami sifatida talqin qilinishi mumkin. Keyin ketma-ketlikning kerakli
elementini hisoblash ularning qiymatlarini qayta-qayta yangilashdan iborat bo‘ladi.
Xususan, faktorial uchun: X:= 1; i:= 2 uchun n do x:= x * i; writeln(x); Har bir bunday
yangilanish (x:= x * i) chaqiriladi iteratsiya, va takroriy takrorlash jarayoni iteratsiya.
Biroq, e'tibor bering, (1) munosabat ketma-ketlikning sof rekursiv ta'rifi va n-elementni
hisoblash aslida f funktsiyasini o‘zidan takroriy olishdir: Xususan, faktorial uchun
quyidagilarni yozish mumkin: Function Factorial(n: integer): integer; start agar n > 1
bo‘lsa, unda Faktorial:= n * Faktorial(n-1) else Faktorial:= 1; oxiri; Shuni tushunish
kerakki, funktsiya chaqiruvlari qo‘shimcha xarajatlarni talab qiladi, shuning uchun
faktorialni hisoblashning birinchi varianti biroz tezroq bo‘ladi. Umuman olganda, iterativ
echimlar rekursivlarga qaraganda tezroq ishlaydi. Rekursiya foydali bo‘lgan holatlarga
o‘tishdan oldin, uni ishlatmaslik kerak bo‘lgan yana bir misolni ko‘rib chiqaylik. Ketma-](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_5.png)
![ketlikdagi keyingi qiymat bitta emas, balki bir vaqtning o‘zida bir nechta oldingi
qiymatlarga bog'liq bo‘lganda, takrorlanish munosabatlarining alohida holatini ko‘rib
chiqing. Misol sifatida taniqli Fibonachchi ketma-ketligi bo‘lib, unda har bir keyingi
element oldingi ikkita elementning yig'indisidir: "Frontal" yondashuv bilan siz
quyidagilarni yozishingiz mumkin: Fib(n: integer): integer; boshlang, agar n > 1 bo‘lsa,
Fib:= Fib(n-1) + Fib(n-2) boshqa Fib:= 1; oxiri; Fibga har bir qo‘ng'iroq bir vaqtning
o‘zida ikkita nusxasini yaratadi, nusxalarning har biri yana ikkitasini yaratadi va hokazo.
Operatsiyalar soni ko‘payib boradi n eksponensial ravishda, garchi iterativ yechim uchun,
chiziqli n operatsiyalar soni. Aslida, yuqoridagi misol bizga buni o‘rgatmaydi QACHON
rekursiya ishlatilmasligi kerak va QANDAY undan foydalanmaslik kerak. Axir, agar tez
iterativ (loop-asosli) yechim mavjud bo‘lsa, u holda bir xil tsiklni rekursiv protsedura
yoki funksiya yordamida amalga oshirish mumkin. Masalan: // x1, x2 – boshlang‘ich
shartlar (1, 1) // n – kerakli Fibonachchi soni funksiyasining soni Fib(x1, x2, n: integer):
butun son; varx3: butun son; boshlang, agar n > 1 bo‘lsa, unda x3 boshlanadi:= x2 + x1;
x1:=x2; x2:=x3; Fib:= Fib(x1, x2, n-1); end else Fib:= x2; oxiri; Shunga qaramay, iterativ
echimlarga afzallik beriladi. Savol shundaki, qachon rekursiyadan foydalanish kerak?
O‘zlariga faqat bitta rekursiv qo‘ng'iroqni o‘z ichiga olgan har qanday rekursiv
protseduralar va funktsiyalar iterativ tsikllar bilan osongina almashtiriladi. Oddiy
rekursiv bo‘lmagan hamkasbi bo‘lmagan narsani olish uchun o‘zlarini ikki yoki undan
ortiq marta chaqiradigan protseduralar va funktsiyalarga murojaat qilish kerak. Bunday
holda, chaqirilgan protseduralar to‘plami endi rasmdagi kabi zanjir hosil qilmaydi. 1,
lekin butun daraxt. Hisoblash jarayoni shu tarzda tashkil etilishi kerak bo‘lgan
muammolarning keng sinflari mavjud. Faqat ular uchun rekursiya hal qilishning eng
oddiy va eng tabiiy usuli bo‘ladi. 5. Daraxtlar O‘zini bir necha marta chaqiradigan
rekursiv funktsiyalarning nazariy asosi bo‘limdir diskret matematika daraxtlarni
o‘rganish. 5.1. Asosiy ta'riflar. Daraxtlarni tasvirlash usullari Ta'rif: biz chekli to‘plamni
chaqiramiz T, bir yoki bir nechta tugunlardan iborat bo‘lib, shunday qilib: a) Bu
daraxtning ildizi deb ataladigan bitta maxsus tugun mavjud. b) Qolgan tugunlar (ildizdan
tashqari) har biri o‘z navbatida daraxt bo‘lgan juft-juft ajratilgan kichik to‘plamlarda
joylashgan. Daraxtlar deyiladi pastki daraxtlar bu daraxtdan. Ushbu ta'rif rekursivdir.](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_6.png)
![Xulosa qilib aytganda, daraxt - bu ildiz va unga biriktirilgan pastki daraxtlardan tashkil
topgan to‘plam bo‘lib, ular ham daraxtlardir. Daraxt o‘zi orqali aniqlanadi. Biroq bu ta'rif
mantiqiy, chunki rekursiya cheklangan. Har bir pastki daraxt o‘z ichiga olgan daraxtga
qaraganda kamroq tugunlarni o‘z ichiga oladi. Oxir-oqibat, biz faqat bitta tugunni o‘z
ichiga olgan pastki daraxtlarga kelamiz va bu nima ekanligi allaqachon aniq. Guruch. 3.
Daraxt. Shaklda. 3-rasmda etti tugunli daraxt ko‘rsatilgan. Oddiy daraxtlar pastdan
yuqoriga o‘sgan bo‘lsa-da, ularni boshqa tomonga chizish odatiy holdir. Diagrammani
qo‘lda chizishda, bu usul yanada qulayroq ekanligi aniq. Ushbu nomuvofiqlik tufayli,
ba'zida tugunlardan biri boshqasidan yuqori yoki pastroq deb aytilganda chalkashlik
paydo bo‘ladi. Shu sababli, shajarani tavsiflashda, tugunlarni ildiz ajdodlariga yaqinroq
va uzoqroq avlodlarni chaqirishda ishlatiladigan atamalardan foydalanish qulayroqdir.
Grafik jihatdan, daraxtni boshqa yo‘llar bilan tasvirlash mumkin. Ulardan ba'zilari
rasmda ko‘rsatilgan. 4. Ta'rifga ko‘ra, daraxt ichki to‘plamlar tizimi bo‘lib, bu to‘plamlar
kesishmaydi yoki bir-birining ichida butunlay joylashadi. Bunday to‘plamlarni
tekislikdagi hududlar sifatida tasvirlash mumkin (4a-rasm). Shaklda. 4b, ichki o‘rnatilgan
to‘plamlar tekislikda joylashgan emas, balki bitta chiziqda cho‘zilgan. Guruch. 4b ni
ichki qavslarni o‘z ichiga olgan ba'zi algebraik formulalarning diagrammasi sifatida ham
ko‘rish mumkin. Guruch. 4c daftar ro‘yxati sifatida daraxt tuzilishini ko‘rsatishning yana
bir mashhur usulini beradi. Guruch. 4. Daraxt tuzilmalarini ifodalashning boshqa usullari:
(a) ichki to‘plamlar; (b) ichki qavslar; (c) berilgan ro‘yxat. Led ro‘yxati kodni formatlash
usuliga aniq o‘xshaydi. Darhaqiqat, tuzilgan dasturlash paradigmasi doirasida yozilgan
dastur ichki o‘rnatilgan tuzilmalardan iborat daraxt sifatida ifodalanishi mumkin.
Shuningdek, siz kitoblar ro‘yxati va mundarijalarning ko‘rinishi o‘rtasida o‘xshashlikni
chizishingiz mumkin, bu erda bo‘limlar kichik bo‘limlarni o‘z ichiga oladi, ular o‘z
navbatida kichik bo‘limlarni o‘z ichiga oladi va hokazo. Bunday bo‘limlarni
raqamlashning an'anaviy usuli (1-bo‘lim, 1.1 va 1.2-kichik bo‘limlar, 1.1.2-kichik
bo‘limlar va boshqalar) Dewey o‘nlik tizimi deb ataladi. Shakldagi daraxtga
qo‘llanganidek. 3 va 4 ushbu tizim quyidagilarni beradi: 1.A; 1,1B; 1,2C; 1.2.1D; 1.2.2E;
1.2.3F; 1.2.3.1G; 5.2. o‘tayotgan daraxtlar Daraxt tuzilmalari bilan bog'liq bo‘lgan barcha
algoritmlarda bir xil g'oya doimo yuzaga keladi, ya'ni g'oya. o‘tish yoki daraxtning](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_7.png)
![o‘tishi. Bu har bir tugun bir martadan o‘tgan daraxt tugunlariga tashrif buyurishning bir
usuli. Bu daraxt tugunlarining chiziqli joylashishiga olib keladi. Xususan, uchta usul
mavjud: tugunlarni oldinga, orqaga va orqaga qarab o‘tkazishingiz mumkin. Oldinga
o‘tish algoritmi: Ildizga boring Barcha pastki daraxtlarni ko‘rsatilgan. 5. Guruch. 5.
TTree yozuvining sxematik tasviri. Yozuv uchta maydonga ega: Inf - ba'zi raqamlar,
LeftSubTree va RightSubTree - bir xil TTree tipidagi yozuvlarga ko‘rsatgichlar. Bunday
yozuvlardan tuzilgan daraxt misoli 6-rasmda keltirilgan. Guruch. 6. TTree tipidagi
yozuvlardan tuzilgan daraxt. Har bir yozuv o‘z ichiga olishi mumkin bo‘lgan raqam va
ikkita ko‘rsatgichni saqlaydi nol, yoki bir xil turdagi boshqa yozuvlar manzillari. Agar siz
ilgari bir xil turdagi yozuvlarga havolalarni o‘z ichiga olgan yozuvlardan iborat
tuzilmalar bilan ishlamagan bo‘lsangiz, unda material bilan tanishib chiqishingizni
tavsiya qilamiz. 6. Rekursiv algoritmlarga misollar 6.1. daraxt chizish Shaklda
ko‘rsatilgan daraxtni chizish algoritmini ko‘rib chiqing. 6. Agar har bir chiziq tugun deb
hisoblansa, u holda bu rasm oldingi bobda berilgan daraxt ta'rifini to‘liq qondiradi.
Guruch. 6. Daraxt. Rekursiv tartib aniq bir chiziq chizadi (magistraldan birinchi
vilkagacha) va keyin ikkita pastki daraxt chizish uchun o‘zini chaqiradi. Subdaraxtlar o‘z
ichiga olgan daraxtdan boshlang'ich nuqtasi koordinatalari, burilish burchagi, magistral
uzunligi va ulardagi novdalar soni (bitta kam) bilan farqlanadi. Bu farqlarning barchasi
rekursiv protsedura parametrlari bo‘lishi kerak. Delphida yozilgan bunday
protseduraning namunasi quyida ko‘rsatilgan: Protsedura daraxti(Canvas: TCanvas;
//Daraxt chiziladigan tuval x,y: kengaytirilgan; //Ildiz koordinatalari Burchak:
kengaytirilgan; //Daraxt o‘sadigan burchak TrunkLength: kengaytirilgan; //Magistral
uzunligi n: butun son / /vilkalar soni (qancha rekursiv qo‘ng'iroqlar hali amalga
oshirilishi kerak)); var x2, y2: kengaytirilgan; //Magistralning oxiri (tarmoq nuqtasi)
boshlanadi x2:= x + TrunkLength * cos(Burchak); y2:= y - TrunkLength * sin(Burchak);
Canvas.MoveTo(round(x), round(y)); Canvas.LineTo(round(x2), round(y2)); agar n > 1
bo‘lsa, daraxtni boshlang (Canvas, x2, y2, Angle+Pi/4, 0,55*TrunkLength, n-1);
Daraxt(Canvas, x2, y2, Angle-Pi/4, 0,55*TrunkLength, n-1); oxiri; oxiri; Rasmni olish
uchun. 6 ushbu protsedura quyidagi parametrlar bilan chaqirildi: Daraxt(Image1.Canvas,
175, 325, Pi/2, 120, 15); E'tibor bering, chizma rekursiv chaqiruvlardan oldin amalga](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_8.png)
![oshiriladi, ya'ni daraxt to‘g'ridan-to‘g'ri tartibda chiziladi. 6.2. Xanoy minoralari
Afsonaga ko‘ra, Benaras shahridagi Buyuk ibodatxonada, dunyoning o‘rtasini
ko‘rsatadigan sobor ostida bronza disk joylashgan bo‘lib, unga 3 ta olmos tayoq
o‘rnatilgan, balandligi bir tirsak va ari kabi qalin. Qadim zamonlarda, eng boshida, bu
monastirning rohiblari Brama xudosi oldida aybdor edilar. G'azablangan Brahma uchta
baland tayoq o‘rnatdi va ulardan biriga 64 ta sof oltin disklarni qo‘ydi va har bir kichik
disk kattaroqqa yotadi. Barcha 64 ta disk dunyoni yaratishda Xudo Brahma ularni
qo‘ygan tayoqdan boshqa tayoqqa o‘tkazilishi bilanoq, minora ma'bad bilan birga
changga aylanadi va dunyo momaqaldiroq ostida halok bo‘ladi. Jarayonda kattaroq disk
hech qachon kichikroqning ustiga qo‘yilmasligi talab qilinadi. Rohiblar qiyinchilikda,
siljishlar qanday ketma-ketlikda amalga oshirilishi kerak? Ularni ushbu ketma-ketlikni
hisoblash uchun dasturiy ta'minot bilan ta'minlash talab qilinadi. Bramaga qaramasdan,
bu jumboq 19-asrning oxirida frantsuz matematigi Eduard Lukas tomonidan taklif
qilingan. Sotilgan versiyada odatda 7-8 disk ishlatilgan (7-rasm). Guruch. 7. “Xanoy
minoralari” boshqotirmasi. Buning yechimi bor deylik n-1 disk. Keyin tarjima qilish
uchun n disklar quyidagicha bajarilishi kerak: 1) Biz almashtiramiz n-1 disk. 2) Biz
almashtiramiz n th diskni qolgan bo‘sh pinga o‘tkazing. 3) to‘plamini siljiting n(1)
bandda olingan -1 disk n th disk. Ish uchun beri n= 1 o‘zgartirish algoritmi aniq, keyin
induksiya yo‘li bilan (1) - (3) amallarni bajarib, biz disklarning ixtiyoriy sonini
o‘zgartirishimiz mumkin. Berilgan disklar soni uchun siljishlarning butun ketma-ketligini
chop etadigan rekursiv protsedura yarataylik. Bunday protsedura har bir qo‘ng'iroq bilan
bir smena (algoritmning 2-bosqichidan) haqida ma'lumotni chop etishi kerak. (1) va (3)
nuqtalardan siljishlar uchun protsedura disklar soni bittaga kamaygan holda o‘zini
chaqiradi. //n – disklar soni //a, b, c – pin raqamlari. Shift a pinidan, //b piniga yordamchi
pin c bilan amalga oshiriladi. protsedura Xanoy(n, a, b, c: butun son); agar n > 1 bo‘lsa,
Xanoyni boshlang (n-1, a, c, b); writeln(a, " -> ", b); Xanoy (n-1, c, b, a); end else
writeln(a, " -> ", b); oxiri; E'tibor bering, bu holda rekursiv chaqirilgan protseduralar
to‘plami teskari tartibda kesib o‘tilgan daraxtni hosil qiladi. 6.3. Arifmetik ifodalarni
tahlil qilish Tahlil qilish vazifasi ifoda qiymatini hisoblash uchun arifmetik ifodani va
unga kiritilgan o‘zgaruvchilarning ma'lum qiymatlarini o‘z ichiga olgan mavjud satrdan](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_9.png)
![foydalanishdir. Arifmetik ifodalarni hisoblash jarayoni ikkilik daraxt sifatida ifodalanishi
mumkin. Darhaqiqat, arifmetik operatorlarning har biri (+, -, *, /) ikkita operandni talab
qiladi, ular ham arifmetik ifodalar bo‘ladi va shunga ko‘ra, pastki daraxtlar sifatida ko‘rib
chiqilishi mumkin. Guruch. 8 ifodaga mos keladigan daraxt misoli ko‘rsatilgan: Guruch.
8. Arifmetik ifodaga mos sintaksis daraxti (6). Bunday daraxtda barg tugunlari har doim
o‘zgaruvchan bo‘ladi (bu erda x) yoki raqamli doimiylar va barcha ichki tugunlar
arifmetik operatorlarni o‘z ichiga oladi. Operatorni bajarish uchun avvalo uning
operandlarini baholash kerak. Shunday qilib, rasmdagi daraxt oxirgi tartibda o‘tishi
kerak. Tegishli tugunlar ketma-ketligi chaqirdi teskari jilo belgisi arifmetik ifoda.
Sintaksis daraxtini qurishda siz e'tibor berishingiz kerak keyingi xususiyat. Agar,
masalan, ifoda mavjud bo‘lsa va biz chapdan o‘ngga qo‘shish va ayirish amallarini
o‘qiymiz, keyin to‘g'ri sintaksis daraxti ortiqcha o‘rniga minusni o‘z ichiga oladi (9a-
rasm). Aslida bu daraxt ifodaga mos keladi.(8) ifodani teskari, o‘ngdan chapga qarab
tahlil qilsak, daraxtni tuzishni osonlashtirish mumkin. Bunday holda, shaklda
ko‘rsatilgan daraxt. 9b, bu 8a daraxtiga teng, ammo belgini almashtirishni talab qilmaydi.
Xuddi shunday, o‘ngdan chapga ko‘paytirish va bo‘lish operatorlarini o‘z ichiga olgan
ifodalarni tahlil qilish kerak. Guruch. 9. Ifoda uchun sintaksis daraxtlari a – b + c
chapdan o‘ngga (a) va o‘ngdan chapga (b) o‘qiyotganda. Ushbu yondashuv rekursiyani
butunlay yo‘q qilmaydi. Biroq, bu o‘zingizni rekursiv protseduraga faqat bitta qo‘ng'iroq
bilan cheklash imkonini beradi, agar motiv maksimal ishlash uchun tashvish bo‘lsa, bu
etarli bo‘lishi mumkin. 7.3. Daraxt tugunini uning soni bo‘yicha aniqlash Ushbu
yondashuvning g'oyasi rekursiv qo‘ng'iroqlarni oddiy tsikl bilan almashtirishdan iborat
bo‘lib, u daraxtda rekursiv protseduralar natijasida hosil bo‘lgan tugunlar qanchalik ko‘p
bo‘lsa, shuncha marta bajariladi. Har bir qadamda aniq nima qilinishini qadam raqami
bilan aniqlash kerak.Qadam raqami va kerakli harakatlarni taqqoslash ahamiyatsiz ish
emas va har bir holatda uni alohida hal qilish kerak bo‘ladi. Misol uchun, qilmoqchisiz
deylik k o‘rnatilgan halqalar yoqilgan n Har bir bosqichda: i1:= 0 dan n-1 gacha i2 uchun
bajaring:= 0 dan n-1 gacha i3 uchun bajaring:= 0 dan n-1 gacha bajaring… Agar a k
oldindan ma'lum emas, keyin yuqorida ko‘rsatilgandek, ularni aniq yozish mumkin emas.
6.5-bo‘limda ko‘rsatilgan texnikadan foydalanib, siz rekursiv protsedura yordamida](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_10.png)
![kerakli miqdordagi o‘rnatilgan halqalarni olishingiz mumkin: Procedure
NestedCycles(Indekslar: integer massivi; n, k, chuqurlik: integer); var i: integer;
chuqurlikdan boshlang Rekursiyadan xalos bo‘lish va hamma narsani bitta tsiklga
qisqartirish uchun, agar biz sanoq sistemasidagi qadamlarni baza bilan raqamlasak,
e'tibor bering. n, keyin har bir qadam i1, i2, i3, ... raqamlaridan yoki Indekslar
massividagi mos qiymatlardan iborat raqamga ega. Ya'ni, raqamlar tsikl
hisoblagichlarining qiymatlariga mos keladi. Odatiy o‘nlik sanoq sistemasidagi qadam
raqami: Jami qadamlar bo‘ladi nk. O‘nlik sanoq sistemasida ularning sonlarini saralab,
ularning har birini asosli tizimga aylantirgandan so‘ng n, biz indeks qiymatlarini olamiz:
M:=round(IntPower(n,k));
Rekursiya ta’rifi
Rekursiya — Funksiya o ziga o zi to g ridan-to g ri yoki qandaydir vosita orqaliʻ ʻ ʻ ʻ ʻ ʻ
murojaat qilish jarayoniga rekursiya deyiladi va bunday funksiya rekursiv funksiya deb
ataladi . Rekursiv funksiya o zini
ʻ — o zi chaqirgani uchun dasturchilar orasida quyidagi ʻ
jumla mashhur: „Rekursiya nimaligini tushunish uchun oldin rekursiya nimagligini
tushunish kerak“ — Stephen Hawking. Rekursiya funksional dasturlashning asosiy
elementlaridan hisoblanadi. Rekursiya deyarli hamma joyda ishlatiladi. Ba zi
ʼ
masalalarning iterativ yechimi juda ham uzun bo lib ketishi mumkin. Rekursiya esa
ʻ
kodni bir necha barobar qisqartirib berishi mumkin. Aksariyat tuzilmalar va algoritmlarni
rekursiyasiz tasavvur qilib bo lmaydi. Tree, Graph, Heap, Quick Sort,Merge Sort, Bu
ʻ
ro‘yhatni juda uzoq davom ettirish mumkin. Ayniqsa, murakkab tuzilmalar bo lgan Tree
ʻ
va Graphlarda rekursiya har qadamda uchraydi.](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_11.png)
![Kamchiligi
Rekursiya har doim xotiradan qo shimcha joy talab qiladi.ʻ
Rekursiv yechimda xato qilish ehtimoli yuqori, chunki rekursiya juda ham
chalg ituvchi.
ʻ
Rekursiv yechimni xatosini topish qiyin.
Murakkab algoritmni hisoblash qiyin.
Algoritmi
Qutilar ichma-ich ixtiyoriy joylashtirilgan, qaysidir quti ichida kalit bor. Siz kalitni
topish algoritmini tuzishingiz kerak
Rekursiyaga qo yish uchun ushbu ikki shartni yozib olamiz
ʻ
Ishlash sharti: Quti ichida ichki quti chiqsa, uni ochib ko r. Agar ichki qutidan
ʻ
kalit chiqmasa tashqi qutining kelgan joyidan davom et.
To xtash sharti: Quti ichidan kalit topilsa to xta.
ʻ ʻ
Dasturi
Fibonachchi ketma ketligining n — hadini rekursiya qism dastur orqali hisoblovchi
dastur
#include <iostream.h>
int fib(int); // fib() degan funksiya yaratib olamiz
int main()
{
int n;
cout << "n="; cin >> n; // cin orqali o`zgaruvchini qiymatini kiritib olamiz
cout << fib(n) << endl; // fib() funksiyani chaiqirib olamiz
return 0;](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_12.png)
![}
int fib(int k) // fib() funksiyamizga k o`zgaruvchini taminlab olamiz
{
if (k == 0 || k == 1) return 1; //shart agar k miz o ga yoki 1 ga teng bo`lsa bajar
else return fib(k - 1) + fib(k - 2); // aks holda buni bajar
}
Nima uchun rekursiya kerak
Aslini olganda, har qanday rekursiv ishlangan masalani iterativ usulda ishlash
mumkin va buning aksi ham to‘g'ri. Buning ustiga rekursiv yechim har doim xotiradan
qo‘shimcha joy talab qiladi .Shunday ekan, nima uchun unda rekursiya kerak? Albatta,
buning yetarlicha sabablari bor: Rekursiya deyarli hamma joyda ishlatiladi. Ya'ni, lo‘nda
qilib aytganda undan qochib qutilishning iloji yo‘q. Harakat qilib ko‘rish esa qimmatga
tushishi aniq ) Ba'zi holatlarda rekursiv yechim ancha soddaroq. Ayniqsa, ba'zi
masalalarning iterativ yechimi juda ham uzun bo‘lib ketishi mumkin. Rekursiya esa
kodni bir necha barobar qisqartirib berishi mumkin. Aksariyat tuzilmalar va algoritmlarni](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_13.png)
![rekursiyasiz tasavvur qilib bo‘lmaydi. Tree, Graph, Heap, QuickSort, MergeSort, Bu
ro‘yhatni juda uzoq davom ettirish mumkin. Ayniqsa, murakkab tuzilmalar bo‘lgan Tree
va Graphlarda rekursiya har qadamda uchraydi. Dasturchilikni esa ularsiz tasavvur qilib
bo‘lmaydi, bu esa o‘z o‘rnida rekursiya qanchalik muhimligini belgilab beradi. Rekursiya
funksional dasturlashning asosiy elementlaridan hisoblanadi. Hali funksional dasturlash
haqida eshitmagan bo‘lsangiz u haqida ma'lumot axtarib o‘qib ko‘rishni maslahat
beraman. Bir so‘z bilan aytganda, hozirda dasturlash sohasi jadallik bilan funksional
dasturlash paradigmasi tomon ketmoqda (Go va Scala yorqin namunalar). Yana bir qiziq
ma'lumot , shunday dasturlash tillari borki ularda umuman takrorlanish operatorlari yo‘q
va bu borada butunlay rekursiyaga tayanadi. Haskell va Erlang shular jumlasidan.Albatta,
bularning barchasi rekursiyani takrorlash operatorlaridan butunlay ustunligini
anglatmaydi. Aslida, ko‘p hollarda dasturchilar rekursiya ishlatishdan qochishadi. Buning
asosiy sabablari esa: Rekursiya har doim xotiradan qo‘shimcha joy talab qiladi. Bu haqida
Call stack mavzumizda gaplashamiz. Rekursiv yechimda xato qilib ehtimoli
yuqori. Avval ham aytganimizdek, rekursiya juda ham chalg'ituvchi. Shu sababli, uni
ishlatishda osongina xato qilib qo‘yish mumkin. Rekursiv yechimni xatosini topish
qiyin. Bunday masalalarda xato qilib qo‘yish ehtimoli yuqori bo‘lishi bilan birga uni
topib to‘g'irlash ham qiyin bo‘lishi mumkin. Buning asosiy sababi, bunday yechimlarni
tasavvur qilib olish (hayolan debug qilish) juda qiyin. Rekursiv algoritmning
murakkabligini hisoblash ko‘pincha juda murakkab. Hattoki, ba'zan to‘g'ri yechimni
yozishning o‘zi ham kam bo‘lib qolishi mumkin. Chunki, uni iterativ yechim bilan
solishtirishda uning murakkabligini hisoblash kerak bo‘ladi. Rekursiv algoritmlarda bu
ko‘pincha juda murakkab va yaxshigina matematika talab qiladi.
Bevosita va bilvosita rekursiya sxemalari.
To‘g'ridan-to‘g'ri rekursiya
Usul tanasida xuddi shu usulga chaqiruv mavjud bo‘lganda, biz usul to‘g'ridan-
to‘g'ri rekursiv deb aytamiz. Bu shuni anglatadiki, to‘g'ridan-to‘g'ri rekursiya usul o‘zini
chaqirganda sodir bo‘ladi.Bilvosita rekursiya yoki o‘zaro rekursiv.Agar A usuli B usulini
chaqirsa, B usuli C usulini va C usuli A usulini chaqirsa, biz A, B va C usullarini
bilvosita rekursiv yoki o‘zaro rekursiv deb ataymiz.Bilvosita rekursiya usul boshqa](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_14.png)
![usulni chaqirganda yuzaga keladi va natijada asl usul yana chaqiriladi.Bilvosita
rekursiyadagi qo‘ng'iroqlar zanjiri bir nechta usullarni, shuningdek, filiallarni o‘z ichiga
olishi mumkin, ya'ni bitta shart mavjud bo‘lganda bir usul chaqirilishi kerak va boshqa
shart boshqa chaqirilishi kerak.Bilvosita chuqurlik har xil bo‘lishi mumkin.Bilvosita
rekursiya asosiy holatlarga bir xil e'tiborni talab qiladi.To‘g'ridan-to‘g'ri rekursiya
Bilvosita rekursiyaTo‘g'ridan-to‘g'ri rekursiyada faqat bitta funktsiya o‘z-o‘zidan
chaqiriladi. Bilvosita rekursiyada bir nechta funksiya boshqa funktsiyaga va marta soniga
bog'liq.To‘g'ridan-to‘g'ri rekursiya yukni amalga oshiradi. Bilvosita rekursiya to‘g'ridan-
to‘g'ri rekursiya sifatida hech qanday ortiqcha yuk qilmaydiTo‘g'ridan-to‘g'ri rekursiya
xuddi shu funktsiya tomonidan chaqirilgan bo‘lsa, bilvosita funktsiya boshqa funktsiya
tomonidan chaqiriladiTo‘g'ridan-to‘g'ri funktsiyada, funktsiya keyingi safar
chaqirilganda, mahalliy o‘zgaruvchining qiymati saqlanadi, lekin bilvosita rekursiyada,
boshqa har qanday funktsiya mahalliy o‘zgaruvchi deb atalganda, qiymat avtomatik
ravishda yo‘qoladi.
Rekursiv algoritmlarga misollar
Rekursiya - hayotdan misol va undan unumli foydalanish](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_15.png)
![Rekursiya - funksiya(protsedura)ni shu funksiyani ichida chaqirilishi deb qarasak
eng tushunarli ko‘rinish bo‘ladi.
Dasturchilar orasida shunday gap bor: "Rekursiyani bilish uchun, avval uni bilish
kerak". Rekursivgap-a?Rekursiya bajarilishi uchun ikkita narsa bolishi kerak.Hech
oyingiz sizga uyga kirda karobkani ichidan biror nimani olib chiq deganlami? Siz esa
karobkalani kovlab-kovlab 1 soatda topgansiz/yoki umuman topolmagansiz.
Chunki siz korobkani ko‘rib chiqish ketma-ketligini to‘g'ri qo‘ymagansizMasala:
korobkalar ichma-ich ixtiyoriy joylashtirilgan, qaysidir korobka ichida kalit bor. Siz
kalitni topish dasturini tuzing.Rekursiv funksiyaning to‘xtash chegarasi bo‘lmasa esa,
amallarcheksizbajarilaveradi, Funksiya ishga tushganda keyingi chaqirilayotgan funksiya
STACKka qo‘shib borilaveradi. Rekursiv funksiya ishlaganda o‘zi o‘zi chaqirishini
ayttim, aynan chaqiruvchi funksiya esa chaqirilgan funksiyani natijasini kutib turadi, u
esa o‘zi chaqirgan funksiya natijasiga bog'liq bo‘ladi .... va hokazo toki to‘xtash
nuqtasidagi funksiyaga borgunicha. Oxirgi nuqtadagi funksiya ishlaganda esa, stackdan
chiqib ketib undan oldingisi bajarilib, undan oldingisiga javob yetib boradi ... va hokazo
eng birinchi chaqirilganfunksiyaengoxiridayopiladi.Ushbu stack to‘lib qolsa yoki
to‘xtash chegasi noto‘g'ri qo‘yilishi oqibatida Stack Overflow error olasiz.Keling buni
printFun funksiya misolida ko‘ramiz.](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_16.png)
![Quyidagi Rasmda e'tibor bering printFun funksiyasi 3 argumenti bilan chaqirilganda to 1
ga bormagunga qadar 3, 2, bilan chaqirilgan funksiyalar kutib turibdi. Va nihoyat 1 bilan
chaqirilgan element yopilgach, teskari ketma-ketlikda 2, 3 bilan chaqirilgan funksiyalar
ham yopildi.
NATIJA:
3 2 1 1 2 3](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_17.png)
![Ko‘p rekursiv masalalarni oddiy siklda ham bajarsa bo‘ladi degan fikr bor, buni keyingi
postlarda ko‘ramiz Yana bir misol N sonining Faktorialini aniqlash:
int fact (int n) { //funksiyaga qiymat taminladi masalan 5
if (n == 1)](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_18.png)
![return 1;
else
return x*fact(n- 1 ) // 5* fact(4), 4*fact(3), 3*fact(2), 2*fact(1) fact(1) = 1 ga
teng demak fact(2) = 2, fact(3) = 3, fact(4) = 4 ga teng endilikada natija
1 * 2 * 3 * 4 * 5 = 120 ga tengligi kelib chiqadi
}
Bu yerda ikkita shart sifatida:
1. Rekursiya sharti: o‘zidan kichik sonni chaqirish
2. to‘xtash sharti: 1 ga borganda to‘xtash
Ishlash stacki esa tepadagi rasmda keltirilgandek.
fact(3) chaqirilganda fact(3)->fact(2) ni chaqiradi va natijasini kutib ishini
tagatmay turadi, xuddi shunday fact(2) fact(1) chaqirdi, fact(1) yopilgacha esa
stack teskarisiga bo‘shab boradi.
Amaliy ish
#include <iostream>
using namespace std;
int fibonnaci( int x) {
if ((x == 1 ) || (x == 0 )) {
return (x);
} else {
return (fibonnaci(x - 1 ) + fibonnaci(x - 2 ));
}
}
int main() {
int x , i = 0 ;](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_19.png)
![cout << " Seriya shartlari sonini kiriting :: " ;
cin >> x;
cout << " \n Fibonnaci seriyasi : " ;
while (i < x) {
cout << " " << fibonnaci(i);
i ++ ;
}
return 0 ;
}](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_20.png)
![#include <iostream>
using namespace std;
int fact( int n);
int main()
{
int n;
cout << " Musbat butun son kiriting:" ;
cin >> n;
cout << "Faktorial " << n << " = " << fact(n);
return 0 ;
}
int fact( int n)
{
if (n > 1 )
return n * fact(n - 1 );
else
return 1 ;
}](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_21.png)
![](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_22.png)
![Xulosa
Xulosa qilib aytganda Algoritm bilan ishlash barcha turdagi dasturlash tillarida
ishlash imkoniyatini yengillashtirib beradi. Har bir dasturning dastlab algaritmini yaratib
olgan maqul. Agar biz dasturimizning ketma ketligini bilmasak, u dastur biz o‘ylagandan
ko‘proq hajmni egallashi mumkin ekan. Men C++ dasturi strukturasi haqida, belgilar
bayoni, algoritm va rekursiv funksiya tushunchasi, ma’lumotlarni kiritish va chiqarish
operatorlari hamda dasturda ishlatiladigan toifalar, ifodalar va ko‘nikmalarga ega
bo`ldim. Algoritmlash va dasturlash tillari bo‘yicha yozilgan bir necha kitoblar bilan
tanishib chiqdim va ulardan o‘zimga kerakli malumotlarni oldim. Kurs ishimda
programmalash texnologiyalari rekursiv algoritm, rekursiya ta’rifi, bevosita va bilvosita
sxemalar masalalari qaralgan. Hisoblash jarayonida ba’zi bir algoritmlarning o‘ziga qayta
murojaat qilishga to‘g‘ri keladi. O‘ziga–o‘zi murojaat qiladigan algoritmlarga rekkurent
algoritmlar yoki rekursiya deb ataladi. Biron bir masalani yechishda, agar uni bir xil
kichik yoki sodda masalaraga bo‘lib bajarish mumkin bo‘lsa, bunday hollarda rekursiv
algoritm qo‘llash mumkin.Hayotda uchrovchi ba’zi masalalarni hal etish rekursiv
algoritmlarni qo‘llash orqali oson va intutitiv tarzda kechadi. Misol sifatida Fibonachi
sonlari ketma-ketligi, factorial hisoblash. Funksiya o ziga o zi to g ridan-to g ri yokiʻ ʻ ʻ ʻ ʻ ʻ
qandaydir vosita orqali murojaat qilish jarayoniga rekursiya deyiladi va bunday funksiya
rekursiv funksiya deb ataladi . Rekursiv funksiya o zini
ʻ — o zi chaqirgani uchun ʻ
dasturchilar orasida quyidagi jumla mashhur: „Rekursiya nimaligini tushunish uchun
oldin rekursiya nimagligini tushunish kerak“ — Stephen Hawking. Rekursiya funksional
dasturlashning asosiy elementlaridan hisoblanadi. Rekursiya deyarli hamma joyda
ishlatiladi. Ba zi masalalarning iterativ yechimi juda ham uzun bo lib ketishi mumkin.
ʼ ʻ
Rekursiya esa kodni bir necha barobar qisqartirib berishi mumkin. Aksariyat
tuzilmalar va algoritmlarni rekursiyasiz tasavvur qilib bo lmaydi. Tree, Graph, Heap,
ʻ
Quick Sort,Merge Sort, Bu ro‘yhatni juda uzoq davom ettirish mumkin. Ayniqsa,
murakkab tuzilmalar bo lgan Tree va Graphlarda rekursiya har qadamda uchraydi.
ʻ Aslini
olganda, har qanday rekursiv ishlangan masalani iterativ usulda ishlash mumkin va
buning aksi ham to‘g'ri.Buning ustiga rekursiv yechim har doim xotiradan qo‘shimcha](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_23.png)
![joy talab qiladi.Shunday ekan, nima uchun unda rekursiya kerak? Albatta, buning
yetarlicha sabablari bor:Rekursiya deyarli hamma joyda ishlatiladi. Ya'ni, lo‘nda qilib
aytganda undan qochib qutilishning iloji yo‘q. Harakat qilib ko‘rish esa qimmatga
tushishi aniq )Ba'zi holatlarda rekursiv yechim ancha soddaroq. Ayniqsa, ba'zi
masalalarning iterativ yechimi juda ham uzun bo‘lib ketishi mumkin. Rekursiya esa
kodni bir necha barobar qisqartirib berishi mumkin.Aksariyat tuzilmalar va algoritmlarni
rekursiyasiz tasavvur qilib bo‘lmaydi.](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_24.png)
![Foydalangan Adabiyotlar
1. Markushevich A. I. Teoriya analiticheskix funktsiy. V 2-x t. – M.: Nauka, 1968.
T.
2. – 624s 2. Goluzin G.M. Geometricheskaya teoriya funktsii kompleksnogo
peremennogo. – M. : Nauka, 1976.– 540 s.
3. B. V. SHabat. Vvedenie v kompleksnıy analiz. 1–chast. M.N. 1989.
4. G. Xudayberganov, A. Vorisov, X. Mansurov. Kompleks analiz. Toshkent,
«Universitet», 1998.
5. G. Xudayberganov, A. Vorisov, X. Mansurov. Kompleks analiz.Karshi.
«Nasaf», 2003.
6. Virt N. Algoritmı strukturı dannıx programmı.-M.:Mir, 1985.-405s.
7. Aripov M.M., Imomov T., Irmuxamedov Z.M. va boshqalar. Informatika.
Axborot texnologiyalari. Toshkent, 1-qism. 2002, 2-qism. 2003
8. http://ziyonet.uz
9. www.google.uz](/data/documents/d3c51ac2-9f90-4dfd-a88f-1648086dc410/page_25.png)
Mavzu: “Rekursiv algoritmlar. Rekursiya ta’rifi. Bevosita (oddiy) va bilvosita (murakkab) rekursiya sxemalari. Rekursiv algoritmlarga misollar” Reja: 1. Kirish 2. Asosiy qism A) Rekursiv algoritmlar haqida B) Rekursiya ta’rifi C) Bevosita va bilvosita rekursiya sxemalari D) Rekursiv algoritmlarga misollar 3. Xulosa 4. Amaliy ish 5. Foydalangan Adobiyotlar
Kirish Rekursiv algoritmlar Rekursiyaning mohiyati Hisoblash jarayonida ba’zi bir algoritmlarning o‘ziga qayta murojaat qilishga to‘g‘ri keladi. O‘ziga–o‘zi murojaat qiladigan algoritmlarga rekkurent algoritmlar yoki rekursiya deb ataladi. Biron bir masalani yechishda, agar uni bir xil kichik yoki sodda masalaraga bo‘lib bajarish mumkin bo‘lsa, bunday hollarda rekursiv algoritm qo‘llash mumkin.Hayotda uchrovchi ba’zi masalalarni hal etish rekursiv algoritmlarni qo‘llash orqali oson va intutitiv tarzda kechadi. Misol sifatida Fibonachi sonlari ketma-ketligi, factorial hisoblash. Protsedura yoki funksiya boshqa protsedura yoki funksiyalarga qo‘ng'iroqlarni o‘z ichiga olishi mumkin. Jumladan, protsedura o‘zini chaqirishi mumkin. Bu erda hech qanday paradoks yo‘q - kompyuter faqat dasturda duch kelgan buyruqlarni ketma-ket bajaradi va agar protsedura chaqiruviga duch kelsa, u shunchaki ushbu protsedurani bajarishni boshlaydi. Buni amalga oshirish uchun qanday buyruq berilganligi muhim emas. Rekursiv protseduraga misol: Procedure Rec(a: integer); a> bo‘lsa boshlang Keling, asosiy dasturga, masalan, Rec(3) ko‘rinishdagi qo‘ng'iroqni qo‘ysak nima bo‘lishini ko‘rib chiqamiz. Quyida bayonotlar bajarilish ketma-ketligini ko‘rsatadigan oqim diagrammasi keltirilgan. Guruch. 1. Rekursiv protseduraning blok diagrammasi. Rec protsedurasi a = 3 parametri bilan chaqiriladi. Unda a = 2 parametrli Rec protsedurasiga qo‘ng'iroq mavjud. Oldingi qo‘ng'iroq hali tugallanmagan, shuning uchun siz boshqa protsedura yaratilayotganini tasavvur qilishingiz mumkin va birinchisi amalga oshiriladi. ishi tugaguniga qadar ishini tugatmaslik. Qo‘ng'iroq jarayoni parametr a = 0 bo‘lganda tugaydi. Hozirgi vaqtda protseduraning 4 ta nusxasi bir vaqtning o‘zida bajarilmoqda. Bir vaqtning o‘zida bajariladigan protseduralar soni chaqiriladi rekursiya chuqurligi. (Rec(0)) deb nomlangan to‘rtinchi protsedura 0 raqamini chop etadi va chiqadi. Shundan so‘ng, boshqaruv uni chaqirgan protseduraga qaytadi (Rec(1)) va 1 raqami chop etiladi va barcha protseduralar tugaguncha davom etadi. Dastlabki qo‘ng'iroqning natijasi to‘rtta raqamni chop etadi: 0, 1, 2, 3. Nima sodir bo‘layotganining yana bir vizual tasviri rasmda ko‘rsatilgan. 2. Guruch. 2. 3-parametr bilan Rec protsedurasini bajarish 2-parametr bilan Rec protsedurasini bajarish va 3-raqamni chop etishdan iborat. hokazo. O‘z-o‘zidan mashq sifatida, Rec(4) ga qo‘ng'iroq qilganingizda
nima sodir bo‘lishini ko‘rib chiqing. Quyida tasvirlangan Rec2(4) protsedurasini chaqirganingizda nima sodir bo‘lishini ham ko‘rib chiqing, bu erda operatorlar teskari. Protsedura Rec2(a: butun son); yozishni boshlash (a); agar a>0 bo‘lsa, Rec2(a-1); oxiri; E'tibor bering, yuqoridagi misollarda rekursiv qo‘ng'iroq shartli bayonot ichida joylashgan. bu zarur shart rekursiya abadiy tugashi uchun. Shuni ham yodda tutingki, protsedura o‘zini chaqirilganidan boshqa parametr bilan chaqiradi. Agar protsedura global o‘zgaruvchilardan foydalanmasa, bu rekursiya cheksiz davom etmasligi uchun ham kerak. Biroz murakkabroq sxema bo‘lishi mumkin: A funktsiyasi B funktsiyasini chaqiradi, bu esa o‘z navbatida A ni chaqiradi. Bu deyiladi murakkab rekursiya. Ma'lum bo‘lishicha, birinchi bo‘lib tasvirlangan protsedura hali tasvirlanmaganini chaqirishi kerak. Buning mumkin bo‘lishi uchun siz dan foydalanishingiz kerak. Protsedura A(n: butun son); (Birinchi protseduraning oldinga tavsifi (sarlavhasi)) B protsedurasi (n: butun son); (Ikkinchi protseduraning oldinga tavsifi) protsedura A(n: butun son); (To‘liq protsedura tavsifi A) begin writeln(n); B(n-1); oxiri; B protsedurasi (n: butun son); (B protsedurasining to‘liq tavsifi) begin writeln(n); ifn B protsedurasining oldinga e'lon qilinishi uni A protsedurasidan chaqirish imkonini beradi. A protsedurasining oldinga e'lon qilinishi bu misolda talab qilinmaydi va estetik sabablarga ko‘ra qo‘shilgan. Agar oddiy rekursiyani uroborosga qiyoslash mumkin bo‘lsa (3-rasm), unda “Bo‘rilar qo‘rqib bir-birini yeb qo‘ygan” nomli mashhur bolalar she’ridan murakkab rekursiya tasvirini olish mumkin. Ikki bo‘ri bir-birini yeyayotganini tasavvur qiling va siz murakkab rekursiyani tushunasiz. Guruch. 3. Ouroboros - o‘z dumini yutib yuboradigan ilon. Teodor Pelekanosning "Sinoziy" alkimyoviy risolasidan olingan rasm (1478). Guruch. 4. Murakkab rekursiya. 3. Rekursiya yordamida sikl ishini simulyatsiya qiling Agar protsedura o‘zini o‘zi chaqirsa, unda, aslida, bu uning tarkibidagi ko‘rsatmalarning takroriy bajarilishiga olib keladi, bu tsiklning ishlashiga o‘xshaydi. Ba'zi dasturlash tillarida aylanma konstruktsiyalar umuman mavjud emas, bu esa dasturchilarni rekursiyadan foydalangan holda takrorlashni tashkil qilishni qoldiradi (masalan, Prolog, bu erda rekursiya asosiy dasturlash texnikasi). Masalan, for siklining ishini simulyatsiya qilaylik. Buning uchun bizga, masalan, protsedura parametri sifatida amalga oshirilishi mumkin bo‘lgan qadam hisoblagichi o‘zgaruvchisi kerak. 1-misol Protsedura
LoopImitation(i, n: integer); (Birinchi parametr - qadamlar soni, ikkinchi parametr - qadamlarning umumiy soni) begin writeln("Salom N ", i); //Bu erda i bo‘lsa takrorlanadigan har qanday gaplar LoopImitation(1, 10) kabi qo‘ng'iroq natijasi hisoblagichni 1 dan 10 gacha o‘zgartirish bilan ko‘rsatmalarning o‘n marta bajarilishi bo‘ladi. Bu holda u chop etadi: Salom N1 Salom N2 … Salom N 10 Umuman olganda, protsedura parametrlari hisoblagich qiymatlarining o‘zgarishi chegaralari ekanligini ko‘rish qiyin emas. Quyidagi misolda bo‘lgani kabi takrorlanadigan qo‘ng'iroq va ko‘rsatmalarni almashtirishingiz mumkin. 2-misol Protsedura LoopImitation2(i, n: integer); agar men boshlasam Bunday holda, ko‘rsatmalar bajarilishidan oldin protsedura rekursiv chaqiriladi. Protseduraning yangi nusxasi, shuningdek, birinchi navbatda, hisoblagichning maksimal qiymatiga erishgunimizcha, boshqa misolni chaqiradi va hokazo. Shundan keyingina oxirgi chaqirilgan protseduralar o‘z ko‘rsatmalarini bajaradi, so‘ngra oxirgisi o‘z ko‘rsatmalarini bajaradi va hokazo. LoopImitation2(1, 10) ni chaqirish natijasi salomlashishni teskari tartibda chop etishdir: Salom N 10 … Salom N1 Agar biz rekursiv deb ataladigan protseduralar zanjirini tasavvur qilsak, u holda 1- misolda biz undan oldingi protseduralardan keyingilariga o‘tamiz. 2-misolda, aksincha, keyinroqdan oldingiga. Nihoyat, rekursiv qo‘ng'iroqni ikkita ko‘rsatmalar bloki orasiga qo‘yish mumkin. Masalan: Protsedura LoopImitation3(i, n: integer); begin writeln("Salom N", i); (Bu bayonotlarning birinchi bloki bo‘lishi mumkin) agar i Bu yerda, birinchi navbatda, birinchi blokdagi ko‘rsatmalar ketma-ket bajariladi, keyin ikkinchi blokning ko‘rsatmalari teskari tartibda bajariladi. LoopImitation3(1, 10) ga qo‘ng'iroq qilganda biz quyidagilarni olamiz: Salom N1 … Salom N 10 Salom N 10 … Salom N1 Rekursiyasiz xuddi shunday qilish uchun bir vaqtning o‘zida ikkita tsikl kerak bo‘ladi. Xuddi shu protsedura qismlarini bajarish vaqt oralig'ida joylashganligidan foydalanishingiz mumkin. Masalan: 3-misol: Sonni ikkilik sistemaga aylantirish. Ikkilik sonning raqamlarini olish, ma'lumki, sanoq sistemasining asosiga qoldiqga bo‘lish yo‘li bilan sodir bo‘ladi 2. Agar raqam bo‘lsa, uning ikkilik ko‘rinishidagi oxirgi raqami teng bo‘ladi. 2 ga bo‘lishning butun qismini olish: biz bir xil ikkilik ko‘rinishga ega bo‘lgan, ammo oxirgi raqamsiz raqamni olamiz. Shunday qilib, keyingi bo‘linish maydonida 0 ga teng butun son bo‘lguncha yuqoridagi ikkita amalni takrorlash kifoya. Rekursiyasiz u
quyidagicha ko‘rinadi: x>0 esa c:=x mod 2 boshlanadi; x:=x div 2; yozish (c); oxiri; Bu erda muammo shundaki, ikkilik vakillikning raqamlari teskari tartibda hisoblanadi (oxirgi birinchi). Raqamni oddiy shaklda chop etish uchun siz massiv elementlaridagi barcha raqamlarni eslab qolishingiz va ularni alohida tsiklda chiqarishingiz kerak bo‘ladi. Rekursiya bilan massiv va ikkinchi siklsiz kerakli tartibda chiqishni olish oson. Aynan: Protsedura BinaryRepresentation(x: integer); var c, x: integer; start (Birinchi blok. Protsedura chaqiruvi tartibida bajariladi) c:= x mod 2; x:=x div 2; (Rekursiv chaqiruv) agar x>0 bo‘lsa, BinaryRepresation(x); (Ikkinchi blok. Teskari tartibda ishlaydi) yozish(c); oxiri; Umuman olganda, biz hech qanday yutuq olmadik. Ikkilik tasvirning raqamlari mahalliy o‘zgaruvchilarda saqlanadi, ular rekursiv protseduraning har bir ishlayotgan misoli uchun farq qiladi. Ya'ni xotirani saqlab bo‘lmadi. Aksincha, biz ko‘p mahalliy o‘zgaruvchilarni saqlash uchun qo‘shimcha xotira sarflaymiz x. Shunga qaramay, bunday yechim menga chiroyli ko‘rinadi. 4. Takroriy munosabatlar. Rekursiya va iteratsiya Aytishlaricha, vektorlar ketma-ketligi, agar boshlang'ich vektor va keyingi vektorning oldingisiga funktsional bog'liqligi berilsa, takrorlanish munosabati bilan beriladi. Qaytalanish munosabatlari yordamida hisoblangan miqdorning oddiy misoli faktorialdir Keyingi faktorialni avvalgisidan quyidagicha hisoblash mumkin: Belgini kiritish orqali biz quyidagi munosabatni olamiz: Formula (1) vektorlari o‘zgaruvchan qiymatlar to‘plami sifatida talqin qilinishi mumkin. Keyin ketma-ketlikning kerakli elementini hisoblash ularning qiymatlarini qayta-qayta yangilashdan iborat bo‘ladi. Xususan, faktorial uchun: X:= 1; i:= 2 uchun n do x:= x * i; writeln(x); Har bir bunday yangilanish (x:= x * i) chaqiriladi iteratsiya, va takroriy takrorlash jarayoni iteratsiya. Biroq, e'tibor bering, (1) munosabat ketma-ketlikning sof rekursiv ta'rifi va n-elementni hisoblash aslida f funktsiyasini o‘zidan takroriy olishdir: Xususan, faktorial uchun quyidagilarni yozish mumkin: Function Factorial(n: integer): integer; start agar n > 1 bo‘lsa, unda Faktorial:= n * Faktorial(n-1) else Faktorial:= 1; oxiri; Shuni tushunish kerakki, funktsiya chaqiruvlari qo‘shimcha xarajatlarni talab qiladi, shuning uchun faktorialni hisoblashning birinchi varianti biroz tezroq bo‘ladi. Umuman olganda, iterativ echimlar rekursivlarga qaraganda tezroq ishlaydi. Rekursiya foydali bo‘lgan holatlarga o‘tishdan oldin, uni ishlatmaslik kerak bo‘lgan yana bir misolni ko‘rib chiqaylik. Ketma-