Mavzu : Rekursiya va daraxtlar. Mavzu asoslari. Ma’lumotlar tarkibi tushunchasi

Mavzu : Rekursiya va daraxtlar. Mavzu asoslari. Ma’lumotlar tarkibi tushunchasi.

R E J A:

1. 
   Rekursiya haqida tushuncha
   
2. 
   Rekursiya misoli
   
3. 
   Daraxt haqida tushuncha
   
4. 
   Xulosa
   
5. 
   Foydalanilgan adabiyotlar
   

Lat recursio-dan (qaytish). Umuman olganda, bu elementlarni "o'ziga o'xshash tarzda" takrorlash jarayonining nomi.

Rekursiyaning yorqin namunasi - matryoshka qo'g'irchoqlari. Rekursiv ta'rifi: "Matryoshka - ichi kichikroq matryoshka bo'lgan, bo'linib ketgan ichi bo'sh yog'och qo'g'irchoq". Mana rus tilidagi rekursiya. Agar magistrlarning imkoniyatlari chegarasi bo'lmaganida edi, ideal matryoshka atom darajasiga qadar chuqur kirib borar edi. Va undan ham chuqurroq. Shunchaki, Lefty etarli kuchga ega emas edi. Yuqori chegara nazariy jihatdan ham cheklanmagan, ammo tegishli o'lchamdagi baobablar bizning sayyoramizda o'smaydi. Umuman olganda, texnik sabablarga ko'ra rekursiya cheklangan bo'lishi kerak.

Dasturlashda (matematikada bo'lgani kabi) rekursiya - bu funktsiyani o'zi chaqirish jarayoni (to'g'ridan-to'g'ri rekursiya) yoki B funktsiyasining A funktsiyasidan qo'ng'iroq, bu o'z navbatida A funktsiyasiga chaqirishni o'z ichiga oladi (bilvosita yoki o'zaro rekursiya). Albatta, rekursiv qo'ng'iroqlar qoniqarli tugatish shartiga ega bo'lishi kerak, aks holda bunday dastur cheksiz tsikldagidek "osilib" qoladi - lekin cheksiz tsikldan farqli o'laroq, cheksiz rekursiya bilan u stek to'kilishi bilan qulab tushadi.

Rekursiya misoli

Matematik dasturlashda rekursiyaning eng zerikarli misoli bu faktorial hisoblash. Keling, ulug'vor an'analarga xiyonat qilmaylik. Hali qilmaganlar uchun: N! (faktorial N) birdan Ngacha bo'lgan barcha tabiiy sonlarning ko'paytmasi (nol faktoriali 1 ga teng).
Siz loopda 1dan N gacha bo'lgan raqamlarni ahmoqona tarzda ko'paytira olasiz. Yoki siz shartni o'z ichiga oladigan va o'zi chaqiradigan funktsional (n) funktsiyani qurishingiz mumkin. Agar n bitta bo'lsa, u holda funktsiya 1 qiymatini qaytaradi, aks holda u n qiymatini faktorial (n-1) ko'paytirgan qiymatini qaytaradi.
PHP eskiz

Funktsional ($ n) funktsiyasi (if ($ n \u003d\u003d 1) (return 1;) else (return intval ($ n * factorial ($ n - 1));))

Rekursiyadan amaliy foydalanish

"Xo'sh, bu nima uchun bu erda kerak?" - sabrsiz yosh o'quvchi bizdan so'raydi - "Ilmiy bema'nilik, zerikish, har xil faktlar ... Va bu rekursiyani amalda nimaga qo'llash kerak?"
"Veb dasturlashning qora ko'ziga" - biz ikkilanmasdan javob beramiz. Va keyin biz buni oqlaymiz.

Haqiqatan ham veb-dasturlashda rekursiyadan juda ko'p foydalanish bor. Chunki rekursiya har qanday daraxt tuzilishini bosib o'tishning yagona usuli bo'lishi mumkin, uning kattaligi ham, uyalash chuqurligi ham oldindan ma'lum emas. Aytgancha, grafikalar tuzilishi va o'tishi ham bu holda amalga oshirilmaydi. Bu klassik, janoblar - unix katalog daraxtidan kerakli fayllarni qidirish uchun boshqa usul bilan harakat qilib ko'ring va siz rekursiyasiz hech qaerga ketmasligingizni darhol tushunasiz.

Ichki ro'yxatlar ko'rinishidagi bo'limlarning iyerarxik tuzilishi bilan sayt xaritasini yaratish orqali unsiz bajarishga harakat qiling. O'rnatish chuqurligi qancha daraja bilan chegaralanganligini oldindan bilmasangiz, uni qurishdan ko'ra o'zingizni osib qo'yganingiz ma'qul. Va agar siz bilsangiz ham, lekin rekursiyasiz bajarishga harakat qiling, oddiy, shaffof va muammosiz funktsiya o'rniga katta hajmli dasturiy ta'minotni "nima tayoqchalarda" yarating. Tugatganingizdan va terlagan peshonangizni artgandan so'ng, sizga hayotning qorong'u haqiqati keladi: uyalash chuqurligi o'zgarganda, sizning tarqaladigan tuzilishingiz bir zumda to'g'ri ishlashni to'xtatadi. Shuning uchun, siz uni boshqa biron bir joyda qo'llashingiz mumkin emas.

Qidiruv tizimning rekursiyasi

Ha shunday. Qidiruv tizimlarda ham rekursiyadan o'tadigan joy yo'q. Havolalar soni bo'yicha sayt (hujjat) vakolatlarini o'lchash odati o'rnatilgandan buyon qidiruv tizimlari rekursiv tuzoqqa tushib qolishdi va ularni abadiy adashtirishlariga imkon berishdi (bu muallifning samimiy ezgu tilagi). Saytning "og'irligi" havolasi unga bog'langanlarning "og'irligi" ning kichik qismlaridan iborat. B, C va D havolalarida ko'rsatilgan A uchun bu vaznni hisoblash uchun siz ularning vaznini hisoblashingiz kerak, bu esa o'z navbatida har xil boshqalar tomonidan uzatiladi, uning og'irligini ham hisoblash kerak ... va hokazo butun Internet bo'ylab qidiruv tizimida hisobga olinadi. To'liq rekursiv vazifa. Va siz aytasiz - qat'iy nazariya. Eng muhimi, bu ham haqiqiy amaliyot emas.

Google-dan rekursiv PageRank

Google yaratuvchilari PageRankni hisoblash uchun o'zlarining asosiy algoritmlarini ancha oldin nashr etishgan. Va shu vaqtdan beri u qanchalik o'zgargan bo'lsa ham, yaxshilanishlar bilan qancha to'ldirilmasin, asos bir xil bo'lib qolaveradi. PageRank B sahifasi unga bog'langan boshqa barcha sahifalardan qancha pul olganligini hisoblab chiqmagunimizcha, B sahifasining A sahifasiga qancha bog'lanishini bila olmaysiz va bu sahifalarning PageRankini hisoblamagunimizcha buni bilish mumkin emas ... davom etasizmi? Ehtimol endi kerak emas. Bu yana u - Ulug'vor Rekursiya .

Salom Habrahabr!

Ushbu maqolada biz rekursiya muammolari va ularni qanday hal qilish haqida gaplashamiz.

Rekursiya haqida qisqacha

Rekursiya - bu nafaqat ilm-fan sohasida, balki kundalik hayotda ham uchraydigan juda keng tarqalgan hodisa. Masalan, Droste effekti, Sierpinski uchburchagi va hk. Rekursiyani ko'rish imkoniyatlaridan biri bu veb-kamerani kompyuter ekraniga yo'naltirish, albatta, uni yoqgandan keyin. Shunday qilib, kamera kompyuter ekranining tasvirini yozib oladi va uni ushbu ekranda aks ettiradi, yopiq tsiklga o'xshash narsa chiqadi. Natijada, biz tunnelga o'xshash narsani kuzatamiz.

Dasturlashda rekursiya funktsiyalar bilan chambarchas bog'liq, aniqrog'i, dasturlashdagi funktsiyalar tufayli rekursiya yoki rekursiv funktsiya kabi narsalar mavjud. Oddiy so'zlar bilan aytganda, rekursiya - bu funktsiya (usul) qismini o'zi orqali belgilash, ya'ni o'zini to'g'ridan-to'g'ri (tanasida) yoki bilvosita (boshqa funktsiya orqali) chaqiradigan funktsiya.

Rekursiya haqida ko'p narsa aytilgan. Mana ba'zi yaxshi manbalar:

• 
  Rekursiya va rekursiv vazifalar. Rekursiyani qo'llash sohalari
  

O'quvchi rekursiya bilan nazariy jihatdan tanish va uning nima ekanligini biladi deb taxmin qilinadi. Ushbu maqolada biz rekursiya muammolariga ko'proq e'tibor qaratamiz.

 Rekursiya mohiyati

Protsedura yoki funktsiya boshqa protsedura yoki funktsiyalarga qo'ng'iroqlarni o'z ichiga olishi mumkin. Jarayonni o'z ichiga olishi mumkin. Bu erda paradoks mavjud emas - kompyuter dasturda uchraydigan buyruqlarni faqat ketma-ket ravishda bajaradi va agar protsedura chaqirig'iga duch kelsa, shunchaki ushbu protsedurani bajarishni boshlaydi. Qaysi protsedura buyruq bergani muhim emas.

Rekursiv protseduraga misol:

Rec protsedurasi (a: tamsayı); agar\u003e bo'lsa, boshlang

Agar siz asosiy dasturga qo'ng'iroq qilsangiz nima bo'lishini ko'rib chiqing, masalan, Rec (3) shaklida. Quyida bayonotlarni bajarish ketma-ketligini aks ettiruvchi blok-diagramma berilgan.

Shakl: 1. Rekursiv protseduraning blok diagrammasi.

Rec protsedurasi a \u003d 3 parametri bilan chaqiriladi, u tarkibida a \u003d 2 parametri bo'lgan Rec protsedura chaqirig'ini o'z ichiga oladi, avvalgi qo'ng'iroq hali tugamagan, shuning uchun siz boshqa protsedura yaratilayotgani va birinchisi o'z ishini tugatguncha o'z ishini tugatmaganligini tasavvur qilishingiz mumkin. Qo'ng'iroq jarayoni a \u003d 0 parametri bilan tugaydi. Ayni paytda protseduraning 4 ta nusxasi bir vaqtning o'zida bajariladi. Bir vaqtning o'zida bajarilgan protseduralar soni deyiladi rekursiya chuqurligi.

To'rtinchi protsedura (Rec (0)) 0 raqamini chiqaradi va o'z ishini tugatadi. Shundan so'ng, boshqaruv uni chaqirgan protseduraga qaytadi (Rec (1)) va 1 raqami bosiladi va shuning uchun barcha protseduralar tugamaguncha. Dastlabki qo'ng'iroqda to'rtta raqam chop etiladi: 0, 1, 2, 3.

Nima bo'layotganining yana bir vizual tasviri shakl. 2018-04-02 121 2.



Rasm: 2. Rec protsedurasini 3-parametr bilan bajarish Rec protsedurasini 2-parametr bilan bajarishdan va 3-sonni bosib chiqarishdan iborat. O'z navbatida Rec-protseduraning 2-parametridan foydalanish Rec protsedurasini 1-parametr bilan bajarishdan va 2-sonni bosib chiqarishdan iborat.

Daraxt haqida tushuncha

Daraxt ta'rifi tabiatan rekursivdir. Ushbu ma'lumotlar strukturasining elementi deyiladiyuqori . Daraxt - bu cheklangan miqdordagi bog'langan vertex (filiallari , boshqa daraxtlar). Hozirgi tepalik uchun joylashgan daraxtlar deyiladipastki daraxtlar va ularning boshlariavlodlar . Avlodlarga nisbatan hozirgi tepalik deyiladiajdod . Farzandlari bo'lmagan vertikalar barg yoki deyiladiterminal, butun daraxtning bosh tepasi deyiladiildiz .

Daraxtning rekursiv ta'rifi, u bilan ishlash algoritmlari ham rekursiv bo'lishiga olib keladi. Tsiklik algoritmlar aslida mumkin, ammo ular tanlov asosida chiziqli rekursiyaning natijasidir. Birinchi bosqichda biz algoritmning umumiy shaklini aniqlaymiz,daraxtning to'liq rekursiv o'tishi, bu daraxtning vakillik shakliga bog'liq emas. Uning g'oyasi shundaki   , tepada bajarilgan har qanday harakat, shuningdek, uning barcha kichik daraxtlariga nisbatan bajarilishi kerak, ya'ni algoritm ushbu tepalikning barcha avlodlariga nisbatan rekursiv ravishda bajarilishi kerak. Parametr sifatida   joriy tepalikning identifikatori (indeks, ko'rsatgich, havola) talab qilinadi.



Daraxt tuzilmalari haqida gap ketganda, ularning mavhum ta'rifini ularni xotirada amalga oshirishning aniq usulidan ajratish kerak. Ikkinchisi daraxt bilan ishlaydigan algoritmlarning turiga ham bog'liq:

- agar daraxtning ildiz tugunidan ishlay boshlaydigan rekursiv yoki tsiklik algoritm ishlatilsa, u holda faqat ajdoddan avlodlarga to'g'ridan-to'g'ri bog'lanishlar kerak;

- agar algoritm daraxt bo'ylab yuqoriga va pastga (masalan, daraxtga o'xshash katalog tizimida) barcha yo'nalishlarda harakatlanishni nazarda tutsa, u holda avlodlardan ajdodlarga oldinga va orqaga yo'naltirilgan bog'lanishlar mavjud ( katalog tizimi, ota-onalar katalogiga havola);

- Terminal tepalaridan boshlab daraxt bilan ishlaydigan algoritmlar mumkin. Keyinchalik, avlodlardan ajdodlarga bog'lanishdan tashqari, terminal tugunlarini birlashtiradigan ma'lumotlar tuzilishi ham kerak (masalan, ko'rsatgichlar qatori).