Recursiunea

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 19 octombrie 2021; verificările necesită 8 modificări .

Recursiunea este definiția, descrierea, imaginea unui obiect sau proces în cadrul acestui obiect sau proces însuși, adică situația în care obiectul face parte din el însuși. Termenul „recursiune” este folosit în diverse domenii speciale de cunoaștere - de la lingvistică la logică , dar găsește cea mai largă aplicație în matematică și informatică .

În matematică

În matematică, recursiunea se referă la metoda de definire a funcțiilor și a serii de numere: o funcție dată recursiv își determină valoarea făcând referire la sine cu alte argumente. În acest caz, sunt posibile două opțiuni:

Funcție recursivă finală. Este setat în așa fel încât pentru orice argument finit, după un număr finit de apeluri recursive, să conducă la unul dintre cazurile speciale definite separat care sunt evaluate fără recursivitate. Un exemplu clasic: factorialul definit recursiv al unui întreg nenegativ: . Aici, fiecare apel recursiv ulterior este efectuat cu un argument mai mic de unu. Deoarece n este, prin definiție, un număr întreg nenegativ, după n apeluri recursive, evaluarea funcției este garantată să ajungă într-un caz special în care recursiunea se oprește. Astfel, în ciuda caracterului recursiv al definiției, calculul funcției pentru orice argument din domeniul definiției va fi finit. $n!=\begin{cases}n\cdot(n-1)!,&n>0\\1,&n=0\end{cases}$ $0!=1$
Funcție recursivă infinită. Este dat ca referință la sine în toate cazurile (cel puțin pentru unele dintre argumente). Serii infinite, fracții continue infinite și așa mai departe pot fi specificate într-un mod similar. Calculul practic al valorii exacte aici, desigur, este imposibil, deoarece va necesita timp infinit. Rezultatul cerut este găsit prin metode analitice. Cu toate acestea, dacă nu vorbim despre obținerea unei valori absolut exacte, ci despre calcularea unei aproximări date a valorii dorite, atunci în unele cazuri este posibil să se utilizeze direct definiția recursivă: calculele sunt efectuate pe aceasta până când precizia necesară este realizat. Un exemplu este expansiunea continuă a fracției a numărului e :

e = 2+\cfrac{2}{2+\cfrac{3}{3+\cfrac{4}{4+\ldots}}}\; = 2+f(2)

, Unde

f(n)=\cfrac{n}{n+f(n+1)}

Calculul direct conform formulei de mai sus va provoca recurență infinită, dar se poate dovedi că valoarea lui f (n) tinde spre unitate pe măsură ce n crește (prin urmare, în ciuda infinitității seriei, valoarea numărului Euler este finită) . Pentru un calcul aproximativ al valorii lui e, este suficient să limitați artificial adâncimea recursiunii la un număr prestabilit și, la atingerea acestuia, să folosiți unul.

f(n)

Un alt exemplu de recursivitate în matematică este o secvență de numere , dată de o formulă recursivă , în care fiecare termen succesiv din șir este calculat ca rezultat al unei funcție a n termeni anteriori. Astfel, cu ajutorul unei expresii finite (care este o combinație între o formulă recursivă și un set de valori pentru primii n termeni ai unei serii), poate fi definită o succesiune infinită.

Strâns legată de recursivitate este inducția matematică : este o modalitate naturală de a demonstra proprietățile funcțiilor pe numere naturale , date recursiv în ceea ce privește valorile lor mai mici.

În matematică, o clasă de așa-numite funcții „primitiv recursive” este considerată separat. Definiția unei funcții recursive primitive este de asemenea recursivă, definește un set de funcții primitive și un set de reguli; o funcție este recursivă primitivă dacă poate fi reprezentată ca o combinație de funcții recursive primitive formate conform acestor reguli.

Exemple de recursivitate în matematică:

Metoda Gauss-Jordan pentru rezolvarea sistemelor de ecuații algebrice liniare este recursivă.
Factorialul deja menționat al unui număr întreg nenegativ.
Numerele Fibonacci sunt definite folosind relația de recurență : Primul și al doilea număr Fibonacci sunt 1 Pentru , -e numărul Fibonacci este egal cu suma numerelor --lea și --lea Fibonacci $n>2$ $n$ $(n-1)$ $(n-2)$
Aproape toți fractalii geometrici sunt dați sub forma unei recursiuni infinite (de exemplu, triunghiul Sierpinski ).
Un exemplu standard de funcție recursivă calculabilă care nu este recursivă primitivă este funcția Ackermann : pentru numere întregi nenegative și după cum urmează: $m$ $n$

A(m,\;n)=\begin{cases}n+1,&m=0;\\A(m-1,\;1),&m>0,\;n=0;\\A(m -1,\;A(m,\;n-1)),&m>0,\;n>0.\end{cases}

În programare

Funcții

În programare, recursiunea este un apel la o funcție ( procedură ) de la ea însăși, direct ( recursie simplă ) sau prin alte funcții ( recursie complexă sau indirectă ), de exemplu, o funcție apelează o funcție , iar o funcție apelează o funcție . Numărul de apeluri imbricate de funcții sau proceduri se numește adâncimea recursiunii. Un program recursiv vă permite să descrieți un calcul repetat sau chiar potențial infinit și fără repetarea explicită a părților programului și utilizarea buclelor. $A$ $B$ $B$ $A$

O funcție recursivă structural la nivelul superior este întotdeauna o instrucțiune de ramură (selectarea uneia dintre două sau mai multe alternative în funcție de condiția (condițiile), care în acest caz este adecvat să se numească „condiția de terminare a recursiei”), având două sau mai multe ramuri alternative, dintre care, deși cel puțin una este recursivă și cel puțin una este terminală . Ramura recursivă este executată atunci când condiția de terminare a recursiunii este falsă și conține cel puțin un apel recursiv - un apel direct sau indirect al funcției către ea însăși. Ramura terminală este executată când condiția de terminare a recursiunii este adevărată; returnează o anumită valoare fără a efectua un apel recursiv. O funcție recursivă bine scrisă trebuie să se asigure că, după un număr finit de apeluri recursive, este atinsă condiția de terminare a recursiunii, determinând întreruperea și revenirea lanțului de apeluri recursive succesive.

Pe lângă funcțiile care fac un apel recursiv pe fiecare ramură recursivă, există cazuri de „recursie paralelă” în care două sau mai multe apeluri recursive sunt efectuate pe aceeași ramură recursivă. Recursiunea paralelă este tipică atunci când se prelucrează structuri de date complexe, cum ar fi arbori. Cel mai simplu exemplu de funcție paralel-recursivă este calculul seriei Fibonacci, unde pentru a obține valoarea n-lea termen, este necesar să se calculeze (n-1)-th și (n-2)-th .

Implementarea apelurilor de funcții recursive în limbaje utilizate practic și medii de programare, de regulă, se bazează pe mecanismul stivei de apeluri - adresa de retur și variabilele locale ale funcției sunt scrise în stivă , datorită cărora fiecare apel recursiv următor la această funcție folosește propriul set de variabile locale și din acest motiv funcționează corect. Partea inversă a acestui mecanism destul de simplu este că fiecare apel recursiv necesită o anumită cantitate de RAM al computerului , iar dacă recursiunea este prea profundă, stiva de apeluri se poate depăși.

Întrebarea privind dezirabilitatea utilizării funcțiilor recursive în programare este ambiguă: pe de o parte, forma recursivă poate fi structural mai simplă și mai clară, mai ales atunci când algoritmul implementat în sine este în esență recursiv. În plus, unele limbaje declarative sau pur funcționale (cum ar fi Prolog sau Haskell ) pur și simplu nu au mijloace sintactice pentru organizarea buclelor, iar recursiunea în ele este singurul mecanism disponibil pentru organizarea calculelor repetate. Pe de altă parte, se recomandă, în general, să se evite programele recursive care duc (sau în anumite circumstanțe pot duce) la o adâncime prea mare a recursiunii. Astfel, exemplul de calcul recursiv al factorial, care este larg răspândit în literatura educațională, este mai degrabă un exemplu de cum să nu se folosească recursiunea, deoarece duce la o adâncime a recursiunii suficient de mare și are o implementare evidentă sub forma unui ciclu convențional. algoritm.

Există un tip special de recursivitate numită „ recursie coadă ” (structura unui algoritm recursiv este astfel încât apelul recursiv este ultima operație efectuată în funcție, iar rezultatul său este returnat direct ca rezultat al funcției). Interpreții și compilatorii de limbaje funcționale de programare care acceptă optimizarea codului (sursă sau executabil) convertesc automat recursiunea cozii în iterație , ceea ce asigură execuția algoritmilor recursiunii cozii într-o cantitate limitată de memorie. Astfel de calcule recursive, chiar dacă sunt formal infinite (de exemplu, când se folosește recursiunea pentru a organiza munca unui shell care acceptă comenzile utilizatorului), nu duc niciodată la epuizarea memoriei . Cu toate acestea, standardele limbajului de programare nu definesc întotdeauna clar exact ce condiții trebuie să îndeplinească o funcție recursivă pentru ca traducătorul să fie garantat să o transforme într-o iterație. Una dintre rarele excepții este limbajul Scheme ( un dialect al limbii Lisp ), a cărui descriere conține toate informațiile necesare.

Teoretic, orice funcție recursivă poate fi înlocuită cu o buclă și o stivă . Cu toate acestea, o astfel de modificare, de regulă, este lipsită de sens, deoarece duce doar la înlocuirea salvării automate a contextului în stiva de apeluri cu executarea manuală a acelorași operațiuni cu același sau mai mult consum de memorie. O excepție poate fi situația în care algoritmul recursiv trebuie să fie modelat într-un limbaj în care recursiunea este interzisă.

Dovada corectitudinii programelor

Spre deosebire de programele explicit ciclice, nu este nevoie să se introducă artificial un invariant pentru a demonstra corectitudinea celor recursive . Dovada analitică a corectitudinii unei funcții recursive se reduce la metoda inducției matematice, adică la demonstrarea următoarelor afirmații:

Corectitudinea inversării recursive. Se dovedește că rezultatul calculat în orice ramură recursivă a funcției va fi corect, cu condiția ca parametrii funcției să fie setați corect și apelurile recursive corespunzătoare să returneze rezultatul corect.
Corectitudinea tuturor ramurilor terminale. Se dovedește că toate ramurile terminale returnează valori corecte. De regulă, această dovadă este banală, deoarece ramurile terminale de obicei nu conțin niciun calcul.
Accesibilitatea unei ramuri terminale pentru orice set corect de parametri după un număr finit de apeluri recursive. Se dovedește că modificarea parametrilor unui apel de funcție, care se efectuează în timpul unui apel recursiv, după un număr finit de apeluri recursive, va duce la unul dintre seturile de parametri pentru care există o ramură terminală.

Din suma primei și a doua declarații rezultă că, dacă se ajunge la ramura terminală (și asta înseamnă în toate cazurile când calculul funcției se dovedește a fi final), funcția va returna rezultatul corect. A treia propoziție demonstrează că orice calcul va fi finit. Prin urmare, orice apel de funcție cu parametrii corecti va returna rezultatul corect (cu avertismentul „tehnic” evident - dacă adâncimea recursiunii nu este atât de mare încât să provoace un depășire a memoriei).

Date

Definirea datelor recursive apare atunci când o structură de date (înregistrare, obiect) conține un obiect imbricat care este structural similar cu el sau (mai des) o referință la același obiect. Avantajul definirii recursive a unui obiect este că o astfel de definiție finită poate descrie o structură de date potențial infinită. Structuri similare sunt folosite la descrierea listelor și graficelor . Exemplu de descriere a listei ( C ):

struct element_of_list { struct element_of_list * next ; /* indicator la următorul element de același tip */ intdata ; _ /* unele date */ };

Deoarece un număr infinit de obiecte imbricate nu se pot încadra în memoria finită, în realitate astfel de structuri definite recursiv sunt întotdeauna finite. În celulele finale (terminale), se scriu de obicei pointeri goale, care sunt și stegulețe care indică programului care procesează structura că s-a ajuns la capătul acesteia.

Structura de date recursive determină adesea utilizarea recursiunii pentru a procesa aceste date. În ultimii ani, a devenit popular conceptul de așa-numită „ evaluare leneșă ”, conform căruia datele procesate de program sunt calculate doar atunci când este nevoie. Implementarea acestui concept a condus la apariția în unele limbi ( Haskell , Python ) a capacității de a descrie potențial infinit, inclusiv secvențe recursive fără restricții explicite privind generarea de obiecte și de a lucra liber cu ele.

În fizică

Un exemplu clasic de recursivitate infinită sunt două oglinzi plasate una față de cealaltă : ele formează două coridoare de reflexii în oglindă descrescătoare.

Un alt exemplu de recursivitate infinită este efectul de autoexcitare (feedback pozitiv) al circuitelor electronice de amplificare, atunci când semnalul de la ieșire merge la intrare, este amplificat, se întoarce la intrarea circuitului și este amplificat din nou. Amplificatoarele pentru care acest mod de operare este standard se numesc auto- oscilatoare .

În lingvistică

În lingvistică, recursiunea este capacitatea unei limbi de a genera propoziții și construcții imbricate. Propoziția de bază „ pisica a mâncat șoarecele ” poate fi extinsă prin recursivitate ca „ Vanya a ghicit că pisica a mâncat șoarecele” , mai departe ca „ Katya știe că Vanya a ghicit că pisica a mâncat șoarecele”, și așa mai departe. Recursiunea este considerată unul dintre universalele lingvistice , adică este caracteristică oricărei limbi naturale. Cu toate acestea, posibila absență a recursiunii într-una dintre limbile Amazonului - Pirahana , care este remarcată de lingvistul Daniel Everett [1] , a fost recent discutată activ .

În cultură

Majoritatea glumelor despre recursivitate sunt despre recursiunea infinită, în care nu există nicio condiție de ieșire, de exemplu, se știe zicala: „pentru a înțelege recursiunea, trebuie mai întâi să înțelegi recursiunea” .
- O glumă foarte populară despre recursivitate, care amintește de o intrare din dicționar:

recursiunea vezi recursivitate

Tema recursiunii este prezentă în multe povestiri și eseuri ale scriitorului argentinian Jorge Luis Borges .
Mai multe povestiri ale lui Stanislav Lem sunt dedicate incidentelor (posibile) cu recursivitate infinită:
- o poveste din Cyberiad despre o mașină rațională care a fost suficient de inteligentă și de leneșă pentru a construi una similară pentru a rezolva o anumită problemă și a-i încredința soluția (rezultatul a fost o recursivitate nesfârșită, când fiecare mașină nouă a construit una similară și a transferat sarcina acestuia);
- o poveste despre Iyon liniștitul „A paisprezecea călătorie” din „ Jurnalele stelelor lui Iyon liniștitul ”, în care eroul trece succesiv de la un articol despre morminte la un articol despre sepulare, de acolo la un articol despre sepulcarie, în care există este din nou o referire la articolul „sepulks”:

Am găsit următoarele informații succinte:
„SEPULULE sunt un element important al civilizației Ardrite (vezi) de pe planeta Enteropia (vezi). Vezi SEPULCARIA.
Am urmat acest sfat și am citit:
„SEPULCARIA – aparate pentru sepulare (q.v.)”.
Am căutat „Sepulenia”; scria:
„SEPULARE - ocuparea lui Ardrits (vezi) de pe planeta Enteropia (vezi). Vezi SEPULE.

Lem S. „Jurnalele stelare ale lui Iyon cel liniștit. Călătoria paisprezece.

Acronime recursive : GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor), WINE ( Wine Is Not an Emulator ), etc.
Stema Federației Ruse este un obiect grafic definit recursiv: în laba dreaptă a vulturului dublu capete descris pe ea, este prins un sceptru, care este încoronat cu o copie redusă a stemei. Întrucât pe această stemă există și un sceptru în laba dreaptă a vulturului, se obține o recursivitate infinită.

Vezi și

Note

↑ Despre recursiunea în lingvistică, varietățile sale și cele mai caracteristice manifestări în limba rusă sunt descrise în articolul lui E. A. Lodatko „Recursive Linguistic Structures” Copie de arhivă din 4 martie 2009 pe Wayback Machine

Link -uri

Articol în Encyclopedia Foundation // Recurs

fractali
Caracteristici	dimensiune fractală dimensiunea Hausdorff Dimensiunea Lebesgue recursiunea autoasemănarea
Cei mai simpli fractali	Fern Barnsley Setul Cantor curba dragonului curba Koch Sponge Menger covor Sierpinski Triunghiul Sierpinski Curba de umplere a spațiului
atractor ciudat	Multifractal
Sistemul L	Curba de umplere a spațiului
Fractali de bifurcație	Julia a stabilit Fractal Lyapunov Set Mandelbrot bazinele lui Newton
Fractali aleatorii	Mișcarea browniană arbore brunian suprafata fractala Teoria percolarii
oameni	Georg Kantor Felix Hausdorff Gaston Julia Helge von Koch Paul Levy Alexandru Lyapunov Benoit Mandelbrot Lewis Richardson Vaclav Sierpinski
subiecte asemănătoare	Cât de lungă este coasta Marii Britanii? » Paradoxul litoralului