Šiuolaikinis rekursijos supratimas: funkcionalumo apibrėžimas ir prieiga prie jo iš išorės ir iš šios funkcijos. Manoma, kad rekursiją pagimdė matematikai: faktorinis skaičiavimas, begalinės eilutės, fraktalai, tęstinės trupmenos… Tačiau rekursiją galima rasti visur. Objektyvūs gamtos dėsniai rekursiją „laiko“savo pagrindiniu algoritmu ir išraiškos (egzistencijos) forma ne tiek materialaus pasaulio objektų, kiek apskritai pagrindiniu judėjimo algoritmu.
Įvairių specialybių žmonės įvairiose mokslo ir technologijų srityse naudoja rekursinį algoritmą f (x), kur „x ~/=f (x)“. Funkcija, kuri iškviečia save, yra stiprus sprendimas, tačiau šio sprendimo sudarymas ir supratimas daugeliu atvejų yra labai sudėtinga užduotis.
Senovėje rūmų erdvei padidinti buvo naudojama rekursija. Naudodami veidrodžių sistemą, nukreiptą vienas į kitą, galite sukurti stulbinančius trimačius erdvinius efektus. Bet ar taip lengva suprasti, kaipsureguliuoti šiuos veidrodžius? Dar sunkiau nustatyti, kur yra erdvės taškas, atsispindėjęs per kelis veidrodžius.
Rekursija, rekursiniai algoritmai: reikšmė ir sintaksė
Užduotis, kuri formuluojama kartojant operacijų seką, gali būti išspręsta rekursyviai. Paprastas algoritmas (kvadratinės lygties skaičiavimas, scenarijus, skirtas tinklalapiui užpildyti informacija, failo skaitymas, pranešimo siuntimas…) nereikalauja rekursijos.
Pagrindiniai algoritmo, leidžiančio priimti rekursinį sprendimą, skirtumai:
- yra algoritmas, kurį reikia vykdyti kelis kartus;
- algoritmui reikalingi duomenys, kurie keičiasi kiekvieną kartą;
- algoritmas neturi keistis kiekvieną kartą;
- yra paskutinė sąlyga: algoritmas yra rekursyvus – ne begalinis.
Apskritai negalima teigti, kad vienkartinis vykdymas yra būtina sąlyga, kad nebūtų pasikartojimo priežasties. Taip pat negalite reikalauti privalomos paskutinės sąlygos: begalinės rekursijos turi savo apimtį.
Algoritmas yra rekursyvus: kai operacijų seka atliekama pakartotinai, su duomenimis, kurie kaskart keičiasi ir kaskart duoda naują rezultatą.
Rekursijos formulė
Matematinis rekursijos ir jos analogo supratimas programuojant skiriasi. Matematika, nors yra programavimo požymių, bet programavimas yra daug aukštesnės eilės matematika.
Gerai parašytas algoritmas yra tarsi jo autoriaus intelekto veidrodis. Generolasprogramavimo rekursijos formulė yra „f(x)“, kur „x ~/=f(x)“turi bent dvi interpretacijas. Čia "~" yra rezultato panašumas arba nebuvimas, o "=" yra funkcijos rezultato buvimas.
Pirmoji parinktis: duomenų dinamika.
- Funkcija „f(x)“turi rekursyvų ir nekintamą algoritmą;
- "x" ir rezultatas "f(x)" kiekvieną kartą turi naujas reikšmes, rezultatas "f(x)" yra naujas šios funkcijos "x" parametras.
Antra parinktis: kodo dinamika.
- Funkcija „f(x)“turi kelis algoritmus, kurie patikslina (analizuoja) duomenis;
- duomenų analizė - viena kodo dalis ir rekursinių algoritmų, kurie atlieka norimą veiksmą, įgyvendinimas - antroji kodo dalis;
- funkcijos „f(x)“rezultatas nėra.
Joks rezultatas nėra normalus. Programavimas nėra matematika, čia rezultatas nebūtinai turi būti aiškiai pateiktas. Rekursyvinė funkcija gali tiesiog išanalizuoti svetaines ir užpildyti duomenų bazę arba sukurti objektus pagal gaunamą įvestį.
Duomenys ir rekursija
Rekursinių algoritmų programavimas nėra susijęs su faktorialo skaičiavimu, kai funkcija kiekvieną kartą gauna nurodytą reikšmę, kuri yra viena didesnė arba mažesnė už vieną – diegimo parinktis priklauso nuo kūrėjo pageidavimų.
Nesvarbu, kaip veiks faktorialus „8!“,algoritmas, kuris griežtai laikosi šios formulės.
Informacijos apdorojimas yra visiškai kitos eilės „matematika“. Rekursinės funkcijos ir algoritmai čia veikia raidėmis, žodžiais, frazėmis, sakiniais ir pastraipomis. Kiekviename kitame lygyje naudojamas ankstesnis.
Įvesties duomenų srautas analizuojamas įvairiomis sąlygomis, tačiau analizės procesas paprastai yra rekursyvus. Nėra prasmės rašyti unikalių algoritmų visiems įvesties srauto variantams. Turi būti viena funkcija. Čia rekursiniai algoritmai yra pavyzdžiai, kaip suformuoti išvesties srautą, atitinkantį įvestį. Tai nėra rekursinio algoritmo išvestis, bet tai norimas ir būtinas sprendimas.
Abstrakcija, rekursija ir OOP
Objektinis programavimas (OOP) ir rekursija yra iš esmės skirtingi dalykai, tačiau jie puikiai papildo vienas kitą. Abstrakcija neturi nieko bendra su rekursija, tačiau per OOP objektyvą ji sukuria galimybę įgyvendinti kontekstinę rekursiją.
Pavyzdžiui, informacija analizuojama, o raidės, žodžiai, frazės, sakiniai ir pastraipos paryškinami atskirai. Akivaizdu, kad kūrėjas pateiks galimybę sukurti šių penkių tipų objektų egzempliorius ir pasiūlys rekursinių algoritmų sprendimą kiekviename lygyje.
Tuo tarpu, jei raidžių lygyje „nėra prasmės ieškoti prasmės“, tai semantika atsiranda žodžių lygyje. Galite skirstyti žodžius į veiksmažodžius, daiktavardžius, prieveiksmius, prielinksnius… Galite eiti toliau ir apibrėžti atvejus.
Frazės lygyje semantika papildyta skyrybos ženklais ir logikažodžių junginiai. Sakinių lygyje randamas tobulesnis semantikos lygis, o pastraipą galima laikyti išbaigta mintimi.
Į objektą orientuota plėtra iš anksto nulemia savybių ir metodų paveldėjimą ir siūlo objektų hierarchiją pradėti nuo visiškai abstraktaus protėvio sukūrimo. Tuo pačiu, be jokios abejonės, kiekvieno palikuonio analizė bus rekursyvi ir techniniu lygmeniu per daug nesiskirs daugelyje pozicijų (raidžių, žodžių, frazių ir sakinių). Pastraipos, kaip ir užbaigtos mintys, gali išsiskirti iš šio sąrašo, tačiau jos nėra esmė.
Svarbu, kad didžiąją algoritmo dalį būtų galima suformuluoti abstrakčiųjų protėvių lygmeniu, patikslinant jį kiekvieno palikuonio lygiu, naudojant duomenis ir metodus, iškviečiamus iš abstrakčiojo lygio. Šiame kontekste abstrakcija atveria naujus horizontus rekursijai.
Istorinės OOP ypatybės
OOP du kartus atėjo į programinės įrangos pasaulį, nors kai kurie ekspertai gali išskirti debesų kompiuterijos atsiradimą ir šiuolaikines idėjas apie objektus ir klases kaip naują IT technologijų plėtros ratą.
Sąvokos „objektas“ir „objektyvas“šiuolaikiniame OOP kontekste dažniausiai priskiriamos praėjusio amžiaus 50-60-iesiems, tačiau jie siejami su 1965-aisiais ir Simulo, Lisp, Algol, Smalltalk atsiradimu..
Tais laikais programavimas nebuvo ypač išvystytas ir negalėjo tinkamai reaguoti į revoliucines koncepcijas. Idėjų ir programavimo stilių (C / C ++ ir Pascal - daugiausia) kova dar buvo toli, o duomenų bazės vis dar buvo konceptualiai formuojamos.
Devintojo dešimtmečio pabaigoje ir 90-ųjų pradžioje objektai pasirodė Pascal ir visi prisiminė C / C ++ klases – tai pažymėjo naują susidomėjimo OOP raundą ir būtent tada įrankiai, pirmiausia programavimo kalbos, nebeliko palaiko tik objektines idėjas, bet atitinkamai tobulėja.
Žinoma, jei anksčiau rekursiniai algoritmai tebuvo funkcijos, naudojamos bendrame programos kode, tai dabar rekursija galėjo tapti objekto (klasės) savybių dalimi, o tai suteikė įdomių galimybių paveldėjimo kontekste.
Šiuolaikinio OOP funkcija
OOP kūrimas iš pradžių deklaravo objektus (klases) kaip duomenų ir savybių (metodų) rinkinius. Tiesą sakant, tai buvo apie duomenis, kurie turi sintaksę ir prasmę. Tačiau tada nebuvo įmanoma pateikti OOP kaip realių objektų valdymo įrankio.
OOP tapo „kompiuterinės gamtos“objektų valdymo įrankiu. Scenarijus, mygtukas, meniu elementas, meniu juosta, žyma naršyklės lange yra objektas. Bet ne mašina, maisto produktas, žodis ar sakinys. Tikri objektai liko už objektinio programavimo ribų, o kompiuteriniai įrankiai įgavo naują įsikūnijimą.
Dėl populiarių programavimo kalbų skirtumų atsirado daug OOP tarmių. Semantikos požiūriu jie yra praktiškai lygiaverčiai, o jų dėmesys instrumentinei sferai, o ne taikomajai, leidžia realių objektų apibūdinimą peržengti.algoritmus ir užtikrinti jų kelių platformų ir kalbų „egzistavimą“.
Stekų ir funkcijų iškvietimo mechanizmai
Funkcijų (procedūrų, algoritmų) iškvietimo mechanizmai reikalauja perduoti duomenis (parametrus), grąžinti rezultatą ir įsiminti operatoriaus adresą, kuris turi gauti valdymą, kai funkcija (procedūra) bus baigta.
Paprastai šiam tikslui naudojamas kaminas, nors programavimo kalbos arba pats kūrėjas gali pateikti įvairių valdymo perdavimo galimybių. Šiuolaikinis programavimas pripažįsta, kad funkcijos pavadinimas gali būti ne tik parametras: jis gali būti suformuotas vykdant algoritmą. Algoritmą taip pat galima sukurti vykdant kitą algoritmą.
Rekursyvinių algoritmų samprata, kai jų pavadinimus ir elementus galima nustatyti užduoties formavimo metu (pasirinkus norimą algoritmą), išplečia rekursyvumą ne tik kaip ką nors padaryti, bet ir kas tiksliai turėtų daryk. Algoritmo pasirinkimas pagal jo „prasmingą“pavadinimą yra daug žadantis, tačiau sukelia sunkumų.
Funkcijų rinkinio rekursyvumas
Negalima sakyti, kad algoritmas yra rekursyvus, kai išsikviečia save ir viskas. Programavimas nėra dogma, o rekursyvumo sąvoka nėra išskirtinis reikalavimas vadinti save pagal savo algoritmą.
Praktiniai pritaikymai ne visada duoda švarų sprendimą. Dažnai pirminiai duomenys turi būti paruošti, o rekursinio skambučio rezultatas turi būti analizuojamas visos problemos (viso algoritmo) kontekste.apskritai.
Tiesą sakant, ne tik prieš iškviečiant rekursinę funkciją, bet ir jai pasibaigus, galima arba reikia iškviesti kitą programą. Jei iškvietime nėra jokių ypatingų problemų: rekursinė funkcija A() iškviečia funkciją B(), kuri ką nors daro ir iškviečia A(), tada iš karto kyla problemų dėl valdymo grąžinimo. Užbaigus rekursinį skambutį, funkcija A() turi gauti valdymą, kad būtų galima pakartotinai iškviesti B(), kuri ją iškvies dar kartą. Grąžinti valdiklį taip, kaip turėtų būti, atgal į B() yra neteisingas sprendimas.
Programuotojas neriboja parametrų pasirinkimo ir gali juos papildyti funkcijų pavadinimais. Kitaip tariant, idealus sprendimas yra perduoti B() pavadinimą į A() ir leisti pačiam A() paskambinti B(). Tokiu atveju nebus jokių problemų grąžinant valdymą, o rekursinio algoritmo įgyvendinimas bus skaidresnis.
Supratimas ir rekursijos lygis
Rekursinių algoritmų kūrimo problema yra ta, kad reikia suprasti proceso dinamiką. Naudojant rekursiją objekto metoduose, ypač abstrakčiųjų protėvių lygyje, kyla problemų suprasti savo algoritmą jo vykdymo laiko kontekste.
Šiuo metu skambučių mechanizmuose nėra jokių apribojimų funkcijų įdėjimo lygiui ir dėklo talpai, tačiau kyla supratimo problema: kuriuo momentu kuris duomenų lygis ar vieta bendrame algoritme vadinama rekursyviu. funkcija ir kiek ji pati skambina.
Esami derinimo įrankiai dažnai yra bejėgiaipasakykite programuotojui tinkamą sprendimą.
Cilpos ir rekursija
Manoma, kad ciklinis vykdymas prilygsta rekursijai. Iš tiesų, kai kuriais atvejais rekursinis algoritmas gali būti įgyvendintas sąlyginių ir ciklinių konstrukcijų sintaksėje.
Tačiau jei aiškiai suprantama, kad tam tikra funkcija turi būti įgyvendinta naudojant rekursinį algoritmą, bet kokio išorinio ciklo ar sąlyginių teiginių naudojimo reikėtų atsisakyti.
Čia reiškia, kad rekursinis sprendimas funkcijos pavidalu, naudojant save, bus užbaigtas, funkcionaliai užbaigtas algoritmas. Šį algoritmą programuotojas turės sukurti su pastangomis, suprasdamas algoritmo dinamiką, tačiau tai bus galutinis sprendimas, kuriam nereikia išorinės kontrolės.
Bet koks išorinių sąlyginių ir ciklinių operatorių derinys neleis mums pateikti rekursinio algoritmo kaip visos funkcijos.
Recursion Consensus ir OOP
Beveik visuose rekursinio algoritmo kūrimo variantuose kyla planas sukurti du algoritmus. Pirmasis algoritmas sukuria būsimų objektų (pavyzdžių) sąrašą, o antrasis algoritmas iš tikrųjų yra rekursinė funkcija.
Geriausias sprendimas būtų sutvarkyti rekursiją kaip vieną savybę (metodą), kurioje iš tikrųjų yra rekursinis algoritmas, ir įdėti visą parengiamąjį darbą į objekto konstruktorių.
Rekursyvus algoritmas bus tinkamas sprendimas tik tada, kai jis veikstik pats, be išorinės kontrolės ir valdymo. Išorinis algoritmas gali duoti tik signalą veikti. Šio darbo rezultatas turėtų būti laukiamas sprendimas be išorinės paramos.
Rekursija visada turėtų būti visiškai savarankiškas sprendimas.
Intuityvus supratimas ir funkcinis išsamumas
Kai objektinis programavimas tapo de facto standartu, tapo akivaizdu, kad norint efektyviai koduoti, reikia keisti savo mąstymą. Programuotojas, vykdydamas algoritmą, turi pereiti nuo kalbos sintaksės ir semantikos prie semantikos dinamikos.
Rekursijai būdinga: ją galima pritaikyti viskam:
- žiniatinklio grandymas;
- paieškos operacijos;
- analizuojama teksto informacija;
- skaityti arba kurti MS Word dokumentus;
- žymų atrinkimas arba analizavimas…
OOP charakteristika: leidžia apibūdinti rekursinį algoritmą abstrakčiojo protėvio lygmeniu, tačiau numato, kad jis nurodo unikalius palikuonis, kurių kiekvienas turi savo duomenų ir savybių paletę.
Rekursija yra ideali, nes jai reikalingas jos algoritmo funkcinis išsamumas. OOP pagerina rekursinio algoritmo veikimą, suteikdama jam prieigą prie visų unikalių vaikų.
