Bazele recursivității

În practică, limbile de programare nu sunt pur procedurale, funcționale sau logice, ci conțin caracteristici ale limbilor de diferite tipuri. În limbajul procedural, puteți scrie adesea un program sau o parte din acesta și viceversa. Poate ar fi mai exactă în loc de tipul de limbă care să vorbească despre stilul sau metoda de programare. Bineînțeles, diferite limbi suportă diferite stiluri în grade diferite.

Procesarea și programarea funcțională

Programul procedural constă în operatorii și propunerile care guvernează punerea lor în aplicare. Operatorii tipici sunt operatori de transfer și de transfer, operatori de I / O și oferte speciale pentru organizarea de bucle. Dintre acestea, puteți face fragmente de programe și subrutine. Această programare se bazează pe luarea unei valori a unei anumite variabile, executarea unei acțiuni asupra acesteia și salvarea unei noi valori cu operatorul de atribuire și așa mai departe, până când valoarea finală dorită este primită (și eventual imprimată).
Un program funcțional constă dintr-un set de definiții ale funcțiilor. Funcțiile, la rândul lor, reprezintă apeluri către alte funcții și propoziții care controlează apelurile. Calculele încep cu apelul unei funcții, care la rândul său numește funcții care fac parte din definiția sa etc. în conformitate cu ierarhia definițiilor și structura propozițiilor condiționate. Funcțiile de multe ori se cauzează direct sau indirect.
Fiecare apel returnează o valoare funcției de apelare, care este apoi evaluată; Acest proces se repetă până când funcția calculată returnează rezultatul final utilizatorului.
Programarea funcțională "Pure" nu recunoaște transferurile și transferurile de control. Ramificarea calculelor se bazează pe mecanismul de procesare a argumentelor condiționate. Calculele repetate se efectuează prin recursiune, care reprezintă principalul mijloc de programare funcțională.

Recursiv înseamnă a te folosi

Multe situații practice implică un comportament recurent sau auto-repetitiv care se întoarce la sine. Să presupunem că, de exemplu, încercăm să citim textul într-o altă limbă, folosind dicționarul explicativ al acestei limbi. Atunci când în text apare un cuvânt nefamiliar, explicația lui este căutată în dicționar. În explicația unui cuvânt, la rândul lui, pot fi găsite cuvinte necunoscute, care trebuie găsite în dicționar etc. Puteți stabili această procedură utilizând următoarele reguli:

Recursia conține o ramură terminală

În descrierea recursivă a acțiunilor, este logic să se acorde atenție următoarelor circumstanțe. În primul rând, procedura conține, de regulă, ramificații terminale și condiția de terminare. În al doilea rând, atunci când procedura ajunge la o ramură recursivă, procesul de funcționare este suspendat și un nou proces este lansat de la început, dar la un nou nivel. Procesul întrerupt este amintit într-un fel. El va aștepta și va fi executat numai după finalizarea noului proces. La rândul său, noul proces poate întrerupe, aștepta, etc.
Astfel, se formează un arbore al proceselor întrerupte, din care se execută doar în prezent, doar ultimele procese (pliante); după terminarea muncii lor, procesul care precede acestea continuă să fie realizat. Întregul proces este finalizat când arborele este din nou gol, sau, cu alte cuvinte, toate procesele întrerupte sunt executate.

Recurgerea se poate manifesta în multe forme

În lumea reală, recursiunea se manifestă sub forma unor forme și legături diferite. Poate fi atât în structură cât și în acțiuni.
Toată lumea știe o imagine repetată în două oglinzi, montate unul lângă altul, o imagine care ilustrează imaginea, un televizor în care este vizibil televizorul etc. În matematică, recursiunea are loc în legătură cu multe aspecte diferite, cum ar fi serii, linii repetitive, algoritmi, proceduri pentru determinarea și demonstrarea, într-un cuvânt, în structuri foarte diferite.

Recursiunea se găsește de obicei în natură: copacii au o structură recursivă (ramurile sunt formate din alte ramuri), râurile sunt formate din râurile care curg în ele. Celulele se împart recursiv. În plante, acest lucru este adesea văzut deja la nivel macro. De exemplu, conuri de semințe de conuri și semințe de unele flori (de exemplu, floarea-soarelui) sunt adesea localizate intersectează fanii spirala, determinată de raportul dintre numerele Fibonacci.
Continuarea vieții este asociată cu un proces recursiv. Moleculele ADN și virușii se înmulțesc, se copiază singuri, lucrurile vii au descendenți, care, la rândul lor, au și puși, etc.
Recurgerea este comună atât în limbaj, cât și în comportament, precum și în moduri de gândire și de cunoaștere. Recursia într-o limbă, de exemplu, poate fi în structură sau în conținut:
"Petya a spus că Vasya a spus că ..."
"Știu că știu, dar nu-mi amintesc"
"Pentru a face, pentru a forța să facă, pentru a forța să facă pentru a face, ..."
"Înlocuiți x cu această teză"
"Amintiți-vă și treceți acest mesaj"
...

Formele și acțiunile muzicale pot fi, de asemenea, recursive în mai multe moduri (de exemplu, un canon în care o melodie este însoțită de aceeași melodie întârziată și altele).
Comportamentul orientat și rezolvarea problemelor sunt procese recursive. În mod similar, cercetarea în domeniul inteligenței artificiale este recursivă în încercarea de a investiga procesele care au loc în creier, prin care are loc cercetarea și rezolvarea problemelor, inclusiv cercetarea în domeniul inteligenței artificiale.

Listele sunt construite recursiv

Recursiunea în Lisp se bazează pe teoria matematică a funcțiilor recursive. Recurgerea este potrivită pentru lucrul cu liste, deoarece listele în sine pot consta în subliste, adică au o structură recursivă. Este perfect natural să se recurgă la proceduri recursive pentru a trata structurile recursive.
Listele pot fi definite utilizând următoarele reguli Backus-Naur:

Lisp se bazează pe o abordare recursivă

În programarea Lisp, recursiunea este utilizată pentru a organiza calcule repetitive. Se bazează, de asemenea, pe împărțirea problemei și pe împărțirea acesteia în subtascuri, a cărei soluționare, pe cât posibil, este încercată să reducă la problema deja rezolvată sau în conformitate cu ideea de bază a recursului la rezolvarea problemei în momentul de față.
Pe recursie pe bază și adesea folosite în rezolvarea problemelor și în mecanismul de căutare de întoarcere, prin care se poate întoarce din ramura mort-end de la locul de ramificare se fac calcule de anulare. Recurgerea la Lisp nu este doar o organizație a calculelor - este o metodă de gândire și o metodologie pentru rezolvarea problemelor.

Teoria funcțiilor recursive

Teoria funcțiilor recursive, împreună cu algebra listelor și a calculului lambda, este un alt suport pe care Lisp este în repaus. În acest domeniu al matematicii, sunt studiate aspectele teoretice legate de calcul. Prin calcul sunt înțelese astfel de probleme, care în principiu pot fi programate și rezolvate cu ajutorul unui computer. Teoria funcțiilor recursive oferă, împreună cu mașina Turing, lambda-calcul și alte formalisme teoretice, formalismul echivalent al calculării algoritmice.
Teoria funcțiilor recursive în sine funcții (algoritmi) și proprietățile acestora sunt analizate și clasificate în funcție de care sunt disponibile caracteristici și se calculează, folosind diverse forme de recursivitate. Ideea principală a definiției recursive este că funcția poate fi redusă la unele valori inițiale, la funcțiile definite anterior sau la funcția însăși, cu ajutorul formulelor de recurență, dar cu argumente mai simple "simple". Calculul unei astfel de funcții se termină în momentul în care se reduce la valorile inițiale cunoscute. De exemplu, numerele Fibonacci

0, 1, 1, 2, 3, 5, ...

utilizând notația Lisp infix, poate fi determinată folosind următoarele formule de recurență:

(0 fib) = 0
(1 fib) = 1
(n fib) = ((n - 1) fib) + ((n - 2) fib))

Clasa funcțiilor obținute în acest fel se numește clasa funcțiilor primitive recursive.
Există, de asemenea, funcții care nu sunt primitive recursive. Un exemplu este funcția Akkerman, care poate fi specificată prin următoarele formule de recurență:

(0 Ack x y) = (y + x)
(1 Ack x y) = (y * x)
(2 Ack x y) = (y ^ x)
... ((z + 1) Ack x y) = Pentru valorile y x-1 ori operația (lambda (u v) (z Ack u v)

Funcția Ack dată de circuitul de mai sus nu este recursivă primitivă, deși este calculată, adică se poate determina și pe baza acestei definiții, se calculează valoarea sa într-un timp finit.
Se poate arăta că există funcții ale căror valori pot fi calculate folosind un algoritm, dar care nu pot fi descrise algoritmic. Calculul unei astfel de funcții poate fi infinit. De exemplu, dăm funcția (n f m). rezultatul căruia este 1 dacă în notația zecimală a numărului π există un fragment de cifre repetate m de lungime n.
Se poate arăta că algoritmul pentru calculul acestei funcții există, dar nu știm ce este. Putem doar încerca să calculam semnele lui π în speranța că se va găsi fragmentul dorit, dar nu putem determina dacă calculul se va termina vreodată. Astfel de funcții sunt numite recursive generale.
Clasa funcțiilor primitive recursive este destul de interesantă din punctul de vedere al multor probleme practice. Folosirea funcțiilor recursive în Lisp nu se limitează la argumentele numerice, ele sunt folosite (și chiar în primul rând) pentru structurile simbolice, ceea ce deschide noi oportunități mari în comparație cu calculele numerice.

Articole similare

Pagina anterioară

Pagina următoare