Înțelegerea modernă a recursiunii: definirea funcționalității și accesul la ea din exterior și din această funcționalitate. Se crede că recursiunea s-a născut de matematicieni: calcul factorial, serii infinite, fractali, fracții continuate… Cu toate acestea, recursiunea poate fi găsită peste tot. Legile naturale obiective „consideră” recursiunea drept algoritmul și forma lor principală de exprimare (existență), nu atât a obiectelor lumii materiale, ci, în general, algoritmul principal al mișcării.
Oameni de diverse specialități în diverse domenii ale științei și tehnologiei folosesc algoritmul recursiv f (x), unde „x ~/=f (x)”. O funcție care se numește singură este o soluție puternică, dar formarea și înțelegerea acestei soluții este, în cele mai multe cazuri, o sarcină foarte dificilă.
În antichitate, recursiunea era folosită pentru a mări spațiul palatului. Printr-un sistem de oglinzi îndreptate una spre alta, puteți crea efecte spațiale tridimensionale uimitoare. Dar este atât de ușor de înțeles cumregla aceste oglinzi? Este și mai dificil să determinați unde se află un punct din spațiu, reflectat prin mai multe oglinzi.
Recursiune, algoritmi recursivi: sens și sintaxă
Problema, care este formulată prin repetarea unei secvențe de operații, poate fi rezolvată recursiv. Un algoritm simplu (calcularea unei ecuații pătratice, un script pentru a popula o pagină web cu informații, citirea unui fișier, trimiterea unui mesaj…) nu necesită recursivitate.
Principalele diferențe ale algoritmului care permite o soluție recursivă:
- există un algoritm care trebuie executat de mai multe ori;
- algoritmul are nevoie de date care se modifică de fiecare dată;
- algoritmul nu trebuie să se schimbe de fiecare dată;
- există o condiție finală: algoritmul este recursiv - nu infinit.
În general, nu se poate argumenta că execuția unică este o condiție necesară pentru absența unui motiv pentru recursivitate. De asemenea, nu puteți solicita o condiție finală obligatorie: recursiunile infinite au propriul domeniu de aplicare.
Algoritmul este recursiv: atunci când o secvență de operații este efectuată în mod repetat, pe date care se modifică de fiecare dată și dă un rezultat nou de fiecare dată.
Formula recursiunii
Înțelegerea matematică a recursiunii și analogul său în programare sunt diferite. Matematică, deși există semne de programare, dar programarea este matematică de un ordin mult mai în alt.
Un algoritm bine scris este ca o oglindă a intelectului autorului său. Generalformula recursiunii în programare este „f(x)”, unde „x ~/=f(x)” are cel puțin două interpretări. Aici „~” este asemănarea sau absența rezultatului, iar „= este prezența rezultatului funcției.
Prima opțiune: dinamica datelor.
- funcția „f(x)” are un algoritm recursiv și imuabil;
- "x" și rezultatul "f(x)" au valori noi de fiecare dată, rezultatul "f(x)" este noul parametru "x" al acestei funcții.
A doua opțiune: dinamica codului.
- funcția „f(x)” are mai mulți algoritmi care rafinează (analizează) datele;
- analiza datelor - o parte a codului și implementarea algoritmilor recursivi care efectuează acțiunea dorită - a doua parte a codului;
- rezultatul funcției „f(x)” nu este.
Niciun rezultat nu este normal. Programarea nu este matematică, aici rezultatul nu trebuie să fie prezent în mod explicit. O funcție recursivă poate pur și simplu analiza site-uri și popula baza de date sau poate instanția obiecte în funcție de intrarea.
Date și recursivitate
Programarea algoritmilor recursivi nu se referă la calcularea unui factorial, în care funcția primește de fiecare dată o valoare dată care este una mai mult sau mai mică decât unu - opțiunea de implementare depinde de preferința dezvoltatorului.
Nu contează cât de factorial „8!”,algoritm care urmează cu strictețe această formulă.
Procesarea informațiilor este „matematică” cu totul diferită. Funcțiile recursive și algoritmii de aici operează pe litere, cuvinte, fraze, propoziții și paragrafe. Fiecare nivel următor îl folosește pe cel anterior.
Fluxul de date de intrare este analizat într-o gamă largă de condiții, dar procesul de analiză este în general recursiv. Nu are sens să scrieți algoritmi unici pentru toate variantele fluxului de intrare. Ar trebui să existe o singură funcționalitate. Aici, algoritmii recursivi sunt exemple despre cum se formează un flux de ieșire care este adecvat pentru intrare. Aceasta nu este rezultatul algoritmului recursiv, dar este soluția dorită și necesară.
Abstracție, recursivitate și OOP
Programarea orientată pe obiecte (OOP) și recursiunea sunt entități fundamental diferite, dar se completează perfect. Abstracția nu are nimic de-a face cu recursiunea, dar prin prisma OOP creează posibilitatea implementării recursiunii contextuale.
De exemplu, informațiile sunt analizate și literele, cuvintele, frazele, propozițiile și paragrafele sunt evidențiate separat. Evident, dezvoltatorul va asigura crearea de instanțe de obiecte de aceste cinci tipuri și va oferi o soluție de algoritmi recursivi la fiecare nivel.
Între timp, dacă la nivelul literelor „nu are rost să cauți sens”, atunci apare semantica la nivelul cuvintelor. Puteți împărți cuvintele în verbe, substantive, adverbe, prepoziții… Puteți merge mai departe și defini cazuri.
La nivel de frază, semantica este completată de semne de punctuație și logicăcombinații de cuvinte. La nivelul propozițiilor, se găsește un nivel mai perfect de semantică, iar un paragraf poate fi considerat un gând complet.
Dezvoltarea orientată pe obiect predetermina moștenirea proprietăților și metodelor și propune începerea ierarhiei obiectelor cu crearea unui strămoș complet abstract. În același timp, fără îndoială, analiza fiecărui descendent va fi recursivă și nu va diferi prea mult la nivel tehnic în multe poziții (litere, cuvinte, fraze și propoziții). Paragrafele, ca și gândurile complete, pot ieși în evidență din această listă, dar nu sunt esența.
Este important ca partea copleșitoare a algoritmului să poată fi formulată la nivel de strămoș abstract, rafinându-l la nivelul fiecărui descendent cu date și metode numite de la nivel abstract. În acest context, abstractizarea deschide noi orizonturi pentru recursivitate.
Funcții istorice ale OOP
OOP a venit de două ori în lumea software-ului, deși unii experți ar putea evidenția apariția cloud computingului și a ideilor moderne despre obiecte și clase ca o nouă rundă în dezvoltarea tehnologiilor IT.
Termenii „obiect” și „obiectiv” în contextul modern OOP sunt de obicei atribuiți anilor 50 și 60 ai secolului trecut, dar sunt asociați cu 1965 și apariția Simula, Lisp, Algol, Smalltalk.
În acele vremuri, programarea nu era deosebit de dezvoltată și nu putea răspunde în mod adecvat la conceptele revoluționare. Lupta dintre idei și stiluri de programare (C/C++ și Pascal - în mare parte) era încă departe, iar bazele de date erau încă formate conceptual.
La sfârșitul anilor 80 și începutul anilor 90, obiectele au apărut în Pascal și toată lumea și-a amintit clasele în C / C ++ - aceasta a marcat o nouă rundă de interes pentru OOP și atunci instrumentele, în primul rând limbaje de programare, au devenit nu. acceptă numai idei orientate pe obiecte, dar evoluează în consecință.
Bineînțeles, dacă algoritmii recursivi anteriori erau doar funcții utilizate în codul general al programului, acum recursiunea ar putea deveni parte a proprietăților unui obiect (clasă), care oferea oportunități interesante în contextul moștenirii.
Funcția OOP modernă
Dezvoltarea OOP a declarat inițial obiectele (clasele) ca colecții de date și proprietăți (metode). De fapt, era vorba despre date care au sintaxă și sens. Dar apoi nu a fost posibil să se prezinte POO ca instrument de gestionare a obiectelor reale.
OOP a devenit un instrument de gestionare a obiectelor din „natura computerului”. Un script, un buton, un element de meniu, o bară de meniu, o etichetă într-o fereastră de browser este un obiect. Dar nu o mașină, un produs alimentar, un cuvânt sau o propoziție. Obiectele reale au rămas în afara programării orientate pe obiecte, iar instrumentele computerizate au căpătat o nouă încarnare.
Datorită diferențelor dintre limbajele de programare populare, au apărut multe dialecte ale POO. Din punct de vedere semantic, ele sunt practic echivalente, iar concentrarea lor pe sfera instrumentală, și nu pe cea aplicată, face posibilă ducerea dincolo de descrierea obiectelor reale.algoritmi și asigură „existența” acestora pe mai multe platforme și mai multe limbi.
Stive și mecanisme de apelare a funcției
Mecanismele de apelare a funcțiilor (proceduri, algoritmi) necesită transmiterea de date (parametri), returnarea unui rezultat și amintirea adresei operatorului care trebuie să primească control după finalizarea funcției (procedura).
De obicei, stiva este folosită în acest scop, deși limbajele de programare sau dezvoltatorul însuși pot oferi o varietate de opțiuni pentru transferul controlului. Programarea modernă admite că numele unei funcții poate fi nu doar un parametru, ci poate fi format în timpul execuției algoritmului. Un algoritm poate fi creat și în timpul executării unui alt algoritm.
Conceptul de algoritmi recursivi, când numele și corpurile lor pot fi determinate în momentul formării sarcinii (alegerea algoritmului dorit), extinde recursivitatea nu numai la modul de a face ceva, ci și la cine anume ar trebui Fă-o. Alegerea unui algoritm după numele său „cu sens” este promițătoare, dar creează dificultăți.
Recursivitate pe un set de funcții
Nu poți spune că un algoritm este recursiv atunci când se numește singur și atât. Programarea nu este o dogmă, iar conceptul de recursivitate nu este o cerință exclusivă pentru a te numi din corpul propriului algoritm.
Aplicațiile practice nu oferă întotdeauna o soluție curată. Adesea, datele inițiale trebuie pregătite, iar rezultatul apelului recursiv trebuie analizat în contextul întregii probleme (întregul algoritm) înîn general.
De fapt, nu numai înainte ca o funcție recursivă să fie apelată, ci și după ce aceasta a fost finalizată, un alt program poate sau ar trebui apelat. Dacă nu există probleme speciale cu apelul: funcția recursivă A() apelează funcția B(), care face ceva și apelează A(), atunci imediat apare o problemă cu revenirea controlului. După ce a finalizat apelul recursiv, funcția A() trebuie să primească control pentru a-l reapela pe B(), care o va apela din nou. Revenirea controlului așa cum ar trebui să fie în ordine pe stivă înapoi la B() este soluția greșită.
Programatorul nu este limitat în alegerea parametrilor și îi poate completa cu nume de funcții. Cu alte cuvinte, soluția ideală este să treci numele lui B() lui A() și să lași A() însuși să numească B(). În acest caz, nu vor fi probleme cu returnarea controlului, iar implementarea algoritmului recursiv va fi mai transparentă.
Înțelegerea și nivelul recursiunii
Problema cu dezvoltarea algoritmilor recursivi este că trebuie să înțelegeți dinamica procesului. Când utilizați recursiunea în metodele obiect, în special la nivelul unui strămoș abstract, există o problemă de înțelegere a propriului algoritm în contextul timpului său de execuție.
În prezent, nu există restricții privind nivelul de imbricare a funcțiilor și capacitatea stivei în mecanismele de apel, dar există o problemă de înțelegere: în ce moment din timp ce nivel de date sau ce loc în algoritmul general numit recursiv funcția și pe ce număr de apeluri se află ea însăși.
Instrumentele de depanare existente sunt adesea neputincioasespuneți programatorului soluția potrivită.
Bucle și recursivitate
Se consideră că execuția ciclică este echivalentă cu recursiunea. Într-adevăr, în unele cazuri, algoritmul recursiv poate fi implementat în sintaxa constructelor condiționale și ciclice.
Cu toate acestea, dacă există o înțelegere clară a faptului că o anumită funcție trebuie implementată printr-un algoritm recursiv, orice utilizare externă a unei bucle sau a instrucțiunilor condiționate ar trebui abandonată.
Semnificația aici este că o soluție recursivă sub forma unei funcții care se folosește pe sine va fi un algoritm complet, complet funcțional. Acest algoritm va cere programatorului să-l creeze cu efort, înțelegând dinamica algoritmului, dar va fi soluția finală care nu necesită control extern.
Orice combinație de operatori condiționali și ciclici externi nu ne va permite să reprezentăm algoritmul recursiv ca o funcție completă.
Consensul recursiunii și OOP
În aproape toate variantele de dezvoltare a unui algoritm recursiv, apare un plan pentru a dezvolta doi algoritmi. Primul algoritm generează o listă de obiecte (instanțe) viitoare, iar al doilea algoritm este de fapt o funcție recursivă.
Cea mai bună soluție ar fi să aranjați recursiunea ca o singură proprietate (metodă) care conține de fapt algoritmul recursiv și să puneți toată munca pregătitoare în constructorul de obiecte.
Un algoritm recursiv va fi soluția potrivită numai atunci când funcționeazănumai de unul singur, fără control și management extern. Un algoritm extern poate da doar un semnal pentru a funcționa. Rezultatul acestei lucrări ar trebui să fie soluția așteptată, fără suport extern.
Recursiunea ar trebui să fie întotdeauna o soluție completă de sine stătătoare.
Înțelegere intuitivă și completitudine funcțională
Când programarea orientată pe obiecte a devenit standardul de facto, a devenit evident că pentru a codifica eficient, trebuie să vă schimbați propria gândire. Programatorul trebuie să treacă de la sintaxa și semantica limbajului la dinamica semanticii în timpul execuției algoritmului.
Caracteristica recursiunii: se poate aplica la orice:
- web scraping;
- operații de căutare;
- parsing text information;
- citirea sau crearea de documente MS Word;
- eșantionarea sau analizarea etichetelor…
Caracteristică POO: face posibilă descrierea unui algoritm recursiv la nivelul unui strămoș abstract, dar prevede ca acesta să se refere la descendenți unici, fiecare având propria paletă de date și proprietăți.
Recursiune este ideală deoarece necesită completitudinea funcțională a algoritmului său. OOP îmbunătățește performanța unui algoritm recursiv, oferindu-i acces tuturor copiilor unici.
