logo
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. “Rekursiv algoritmlar. Rekursiya ta’rifi. Bevosita (oddiy) va bilvosita (murakkab) rekursiya sxemalari. Rekursiv algoritmlarga misollar

“Rekursiv algoritmlar. Rekursiya ta’rifi. Bevosita (oddiy) va bilvosita (murakkab) rekursiya sxemalari. Rekursiv algoritmlarga misollar

Yuklangan vaqt:

13.08.2023

Ko'chirishlar soni:

0

Hajmi:

891.439453125 KB
Ko'chirib olish
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- 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. 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 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 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 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 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. 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; } 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 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 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 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. 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 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) 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 ; cout << " Seriya shartlari sonini kiriting :: " ; cin >> x; cout << " \n Fibonnaci seriyasi : " ; while (i < x) { cout << " " << fibonnaci(i); i ++ ; } return 0 ; } #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 ; } 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 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. 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

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-

O'xshashlar

Dinamik dasturlash 2
Algoritmlarni murakkablik darajalasining tahlili, murakkablik darajasini baholash usullari
C++ DASTURLASH TILIDA KO’RSATKICHLAR, FUNKSIYALAR VA REKURSIV FUNKSIYALAR ASOSIDA MURAKKAB JARAYONLARNI DASTURLASH
Oriyentatsiya funksiyasi. Grexem algoritmi. Ajrat va hukmron bo`l algoritmi
Grafikda bog’liq kompenentlarini qidirish algaritmlari