Recursivitate

Reflecție infinită ca exemplu de recursivitate : persoana stă cu o oglindă ținută în fața unei oglinzi mai mari de perete. Imaginea oglindă care urmează se conține ca parte.

Deoarece recursivitatea ( latina recurrere 'running back ) este un principiu al procesului infinit pe care el însuși îl conține ca parte sau utilizând un nume autodefinibil. De obicei, procesele recursive pot fi descrise relativ pe scurt sau pot fi declanșate de o instrucțiune relativ scurtă. Procesele parțiale sau obiectele create unul după altul nu sunt independente unul de celălalt în cazul recursivității, dar există o relație specială, recursivă , între fiecare pereche de pași sau pereche de obiecte .

„Termenul [recursivitate] este foarte larg”. În natură este un proces frecvent observabil (de exemplu, în timpul creșterii plantelor ). Este recreat în multe domenii ale culturii , de exemplu în artele plastice , unde fenomenul denumit mise en abyme . Recursivitatea este un termen comun în matematică și informatică .

Recursivitatea este, de asemenea, o strategie de rezolvare a problemelor. Problemele complexe pot fi adesea surprinse foarte elegant cu reguli formulate recursiv. Principiul de bază este apoi de a reduce o sarcină generală la o sarcină mai simplă din aceeași clasă. Asta va include De asemenea, utilizat în așa-numita programare recursivă : Pentru a crea recursivitate, o procedură , funcție sau metodă trebuie să se numească doar pe sine . Acest proces continuă până când intră în vigoare o condiție de avort conținută în program.

În matematică, formularea recursivă este folosită pentru a explica funcțiile (a se vedea definiția recursivă ).

Exemple introductive de recursivitate

Grafică recursivă

Arborele Pitagora „încolțit”

Regulile recursive pot fi, de asemenea, utilizate în crearea graficii, rezultând așa-numitele fractale - structuri plăcute din punct de vedere estetic, cu aspect natural . Un exemplu este arborele Pitagora . Apare conform următoarei reguli (al treilea pas arată recursiunea):

  • Construiți un pătrat pe o linie de bază dată .
  • Desenați un triunghi cu unghiurile și înălțimea date pe partea superioară .
  • Aplicați din nou cei doi pași de mai sus pe cele două laturi libere ale triunghiului nou creat.

Acest algoritm este apoi desfășurat la o adâncime de recursivitate specificată : Dacă este parcurs o singură dată, se creează un triunghi cu un pătrat pe fiecare dintre cele trei laturi. Arată ca ilustrația teoremei pitagoreice - de unde și numele. Cu cât este mai mare adâncimea de recursivitate, cu atât structura seamănă mai mult cu un copac.

Puteți sări peste primii doi pași din descrierea de mai sus și să începeți procesul recursiv cu ilustrația teoremei pitagoreice:

  • Utilizați această ilustrație pentru a crea încă două ilustrații similare , fiecare dintre ele având un pătrat mare care este identic cu unul dintre cele două pătrate mici din ilustrația anterioară.
  • Folosind aceeași procedură, creați încă două ilustrații similare etc. din fiecare dintre ilustrațiile create în primul pas.

Recursivitate în gramatică

Gramatica limbilor naturale este utilizată în lingvistică, altele inter. descrise cu ajutorul așa-numitelor reguli de structurare a frazelor . Majoritatea lingviștilor cred că toate limbile umane au proprietatea de a fi recursive (spre deosebire de sistemele de semnal din regnul animal). Acest lucru apare deoarece în descompunerea unei unități gramaticale care este etichetată cu o categorie, aceeași categorie poate apărea din nou. Un exemplu este fenomenul propozițiilor subordonate , care este descris aici cu următoarea regulă de producție simplificată:

  1. S → NP VP (o propoziție constă dintr-o frază nominală (ca subiect) și o frază verbală )
  2. VP → V NP * (o sintagmă verbală constă dintr-un verb și zero la multe sintagme nominale ca obiecte ale verbului)
  3. VP → VS (o frază verbală constă dintr-un verb și o propoziție subordonată ca obiect al verbului)

Această gramatică vă permite să alegeți dacă să precizați „VP” cu regula 2 sau 3. În cazul în care pașii 1 și apoi 3 sunt numiți, rezultă o recursivitate: simbolul S apare ca produs al regulii 3, care la rândul său reprezintă începutul regulii 1.

Recursivitate în matematică

Recursiunea joacă un rol important în matematică, de exemplu în definirea recursivă a funcțiilor. Calculul secvenței factoriale și a secțiunii Fibonacci sunt prezentate mai jos ca exemple . Cu toate acestea, în matematică, metodele recursive și definițiile recursive nu sunt limitate la funcțiile numerelor naturale.

Facultate

Funcționalitatea factorială a unui număr natural este definită ca produsul numerelor 1 la :

Exemple

Dacă această listă urmează să fie continuată, recursivitatea va rezulta aproape automat. Pentru calculul de 5! nu veți începe de la început, dar vă puteți abate de la rezultatele anterioare, deci

În general, funcția poate fi definită recursiv :

Secvența Fibonacci

Un exemplu clasic de funcție recursivă este secvența Fibonacci , în care fiecare termen suplimentar din secvență este suma celor două precedente:

Spre deosebire de funcția factorială, nu există o reprezentare închisă banală aici. Cea mai simplă descriere este definiția recursivă:

Această definiție recursivă este în cascadă. Folosind această definiție, al treilea număr Fibonacci este calculat după cum urmează:

Calculul pentru se efectuează de mai multe ori aici. Acest lucru indică faptul că există potențial de optimizare.

Tipuri formale de recursivitate

Cea mai comună formă de recursivitate este recursivitatea liniară , în care, în fiecare caz al definiției recursive, poate apărea cel mult un apel recursiv. Calculul se execută apoi de-a lungul unui lanț de apeluri. Cu o astfel de recursivitate, arborele de apel nu conține nicio ramură.

Recursivitatea primitiv este un caz special al recurență liniare, care întotdeauna printr - o iterație poate fi înlocuit (vezi mai jos raportul recursivitatii și # Pentru iterare ). Aici funcțiile sunt definite pe numerele naturale, primul parametru crescând sau scăzând cu unul în fiecare apel recursiv. Fiecare definiție primitiv-recursivă poate fi înlocuită cu o buclă (de exemplu, pentru buclă sau buclă timpurie ) cu ajutorul unei stive .

Terminale sau repetitive recurență ( recursivitatea cozii sau sfârșitul recursie ) descrie cazul special al recursie liniare, în care fiecare apel recursiv este ultima acțiune a apelului recursiv. Recursiunile finale pot fi înlocuite cu bucle while și viceversa. (Spre deosebire de recursivitatea finală este recursivitatea capului ; vezi sub Regres infinit ).

Sub recursivitate imbricată este definit ca o recursivitate, care are loc în apeluri recursive în expresii de parametri apeluri recursive. Această formă de recursivitate este extrem de dificil de înțeles.

Recursivitatea în cascadă descrie cazul în care mai multe apeluri recursive sunt una lângă alta. Apelurile recursive formează apoi un copac. Recursivitatea în cascadă este considerată elegantă, dar fără alte măsuri poate duce la un efort exponențial de calcul. Este adesea folosit ca punct de plecare pentru obținerea unei alte formulări mai eficiente.

Reciprocă Recursivitatea se face referire la definirea mai multor funcții prin utilizarea reciprocă a reciproc. Acesta poate fi urmărit înapoi la recursivitatea obișnuită a unei funcții cu valoare de tuplu.

Recursivitate în programare

Limbajele de programare superioare care funcționează cu funcții permit, de obicei, și recursivitatea. În majoritatea cazurilor, soluțiile pot fi specificate recursiv sau iterativ.

Despre relația dintre recursivitate și iterație

Recursivitatea și iterația sunt în esență abordări la fel de puternice. Aceleași procese sau similare sunt repetate de mai multe ori, diferența constă în algoritmul utilizat .

În cazul unei iterații, comanda, care constă din mai multe părți, este să ruleze prin mai multe bucle ( pentru, în timp ce ...) până când se îndeplinește o condiție de avort. În cazul unei recursiuni, este suficient să adăugați pur și simplu procedurile sau funcțiile cu solicitarea ca acestea să fie utilizate din nou cu un parametru modificat în mod regulat, până la îndeplinirea unei condiții de terminare.

O recursie trece de obicei cu mai puțin cod sursă și este mai clară (pentru utilizatorii experimentați) - nu trebuie definite variabile auxiliare și contoare de bucle. În ceea ce privește procesarea, procesele iterative sunt de obicei mai eficiente și necesită mai puțin spațiu de stocare. Motivul este că apelurile funcționale repetate sunt plasate în stivă cu toate valorile stocate temporar . În special, recursivitatea poate include, de asemenea, o cauză de depășire a tamponului (StackOverflow). Atunci când se programează sisteme în timp real pe microcontrolere , recursivitatea este, prin urmare, adesea evitată.

Unele limbaje de programare (de exemplu în programarea funcțională ) nu permit iterația, deci implementarea recursivă trebuie întotdeauna selectată. Astfel de limbaje folosesc adesea recursiuni primitive pentru optimizare, care sunt implementate intern ca iterații (unii interpreți pentru LISP și Scheme procedează ca mai sus).

Trebuie remarcat faptul că o implementare naivă a unor funcții (de exemplu, numerele Fibonacci ) necesită ca soluțiile parțiale să fie calculate de mai multe ori. În acest exemplu, remediul este oferit de memoizare , care se bazează pe reutilizarea soluțiilor provizorii care au fost deja calculate. Recursivitatea este o parte esențială a unor strategii de proiectare pentru eficiente algoritmi , în special divide-and-cuceri strategia (divide și cucerește) . Alte abordări (de exemplu așa-numiții algoritmi lacomi ) necesită o abordare iterativă. Funcțiile recursive și recursive primitive joacă un rol major în informatica teoretică , în special în teoria complexității și teoria calculabilității (vezi și calculul lambda și funcția Ackermann ).

În compilatorul care este o descendență recursivă (Recursive Descent) o tehnică în care un limbaj analizat recursiv este.

Exemple de programare

Următorul exemplu arată o implementare simplă și populară a funcției factoriale în limbajul de programare Python . Varianta recursivă este contrastată cu o variantă iterativă din motive de claritate. Recursiunea este exprimată prin faptul că funcția se numește singură cu un argument redus cu 1. Ambele implementări execută algoritmul cu complexitate de rulare liniară în funcție de parametrul de intrare. În timp ce complexitatea spațiului rămâne constantă în varianta iterativă, cerința de memorie crește liniar în varianta recursivă, deoarece o nouă zonă de memorie trebuie rezervată pentru variabilele locale și adresa de retur cu fiecare apel de funcție recursivă. În programarea funcțională, gestionarea dinamică a memoriei este implementată folosind o stivă de apeluri .

Programare iterativă Programare recursivă
def factorial(number):
    result = 1
    
    while number > 1:
        result *= number
        number -= 1
    
    return result
def factorial(number):
    if number <= 1:
        return 1
    
    return number * factorial(number - 1)

Următorul exemplu implementează șirul lui Fibonacci în C de programare limba . Varianta recursivă este o recursiune multiplă care duce la runtime exponențială și complexitate spațială. Funcția recursivă apeluri se ramifică către un arbore binar în care rezultatele parțiale identice sunt calculate de mai multe ori. Cel mai adesea numerele Fibonacci sunt calculate în primele două locuri, care definesc condiția de terminare în recursivitate. În varianta iterativă, complexitatea timpului de rulare este liniară, iar complexitatea spațiului este constantă.

Programare iterativă Programare recursivă
int fibonacci(int number) {
    int first = 0, second = 1;

    for (int count = 0; count < number; ++count) {
        int summand = first;
        first = second;
        second += summand;
    }

    return first;
}
int fibonacci(int number) {
    if (number <= 0)
        return 0;

    if (number == 1)
        return 1;

    return fibonacci(number - 1) + fibonacci(number - 2);
}

Rezolvarea recursivelor

Când se rezolvă o recursiune, se caută efortul de execuție pe de o parte și forma explicită a recursiunii pe de altă parte.

Efortul poate fi determinat ca asimptotic legat de Θ sau Ο folosind teorema master sau metoda de substituție . Chiar și ratele inteligente cu inducție ulterioară oferă o modalitate de limitare superioară pentru a determina durata.

Forma explicită (numită și formă închisă) a ecuației recursive poate fi găsită, de exemplu, prin funcția generatoare. O a doua posibilitate este derivarea valorilor funcției succesive ale recurenței prin formarea diferenței.

Moduri diferite de utilizare a recursivității în științe diferite și mai largi

Conceptul de recursivitate este utilizat în moduri diferite în diferite discipline. Se pot distinge cinci tipuri de utilizare: recursiunea „organizațional-sintactică” în psihologia cognitivă, recursiunea „operațional-funcțională” în teoria tehnologiei și recursiunea „emulativă de proces” în evoluția culturală și teoria civilizației.

Psihologie cognitivă

Psihologul cognitiv evolutiv Michael Corballis a elaborat un concept „organizațional-sintactic” al recursiunii în cartea sa The Recursive Mind . Arată că abilitatea umană de a cuibra niveluri de semnificație și acțiune în orice profunzime și de a deschide șiruri sintactice împreună de unități operaționale, deoarece acestea apar practic în comportamentul și cooperarea instrumentului, precede abilitatea limbajului și este o caracteristică generală a cogniției umane și a organizării acțiunii. . Abilitatea umană puternică de a călători în timp mental și teoria minții se bazează pe capacitatea de recursivitate.

Teoria ingineriei

Teoreticianul sistemului W. Brian Arthur a dezvoltat un concept „operațional-funcțional” al recursivității în cartea sa The Nature of Technology . Arthur arată că toate tehnologiile au o cuibărire ierarhică de elemente și niveluri funcționale, elementele inferioare primind funcționalitatea lor operațională prin recursivitate la nivelurile superioare, așa cum este ilustrat în exemplul unei asociații de portavioane: Turbina unui avion de luptă constă din piese sau "executabile", cum ar fi Șuruburi și pale de aer, care sunt încorporate recursiv în funcția generală a turbinei, deoarece, în același timp, turbina este un "executabil" imbricat recursiv al avionului de luptă, avionul de luptă este un "executabil „al asociației purtătorului de aeronave și acesta este un„ executabil ”al unei escadrile.

Cercetarea evoluției culturale și teoria civilizației

Întreaga dezvoltare tehnologică și culturală în evoluția culturală și istoria civilizației are tiparul recursivității „prozessemulativen”, așa cum a demonstrat sociologul Prior Löffler. Recursiunea „emulativă de proces” descrie un mecanism de dezvoltare în care un proces instrumental sau intelectual este abstractizat și reintrodus ca emulație materială sau media. Acest lucru poate fi demonstrat în evoluția tehnologică timpurie, în care etapele de dezvoltare pot fi descrise fiecare ca grade de recursivitate. Conform stării actuale a cunoașterii, rezumat în „modelul extinderii capacităților culturale”, instrumentele simple din piatră („cultura modulară”,> 2,6 Ma ) urmează din punct de vedere al dezvoltării instrumente compozite precum pietre ciocan cu mâner sau sulițe cu vârfuri osoase („ cultură compozită”,> 500 ka ), compuse apoi din module complementare, independente, cum ar fi arc și săgeată sau ac și fir („ cultură complementară ”,> 70 ka ), apoi instrumente ideale, cum ar fi picturile rupestre, instrumente muzicale sau capcane („cultura ideală”,> 40 ka ). Structurile tehnologice ale etapelor de dezvoltare cumulative se bazează pe recursiunea „proces-emulativă” a proceselor etapelor anterioare. De exemplu, aparatul arcului și al săgeții („cultură complementară”) emulează recursiv procesul de aruncare a javelinului („cultură compozită”), iar capcana („cultura ideală”) emulează recursiv prezența unui grup de vânători sau mecanismul capcană emulează mecanismul declanșator al arcului („Cultură complementară”). Ca principiu general, recursivitatea „proces emulativ” parcurge întreaga istorie a tehnologiei: De exemplu, cuptorul cu microunde se bazează pe recursivitatea „proces emulativ”, deoarece emulează procesul de încălzire a alimentelor, de exemplu printr-un cuptor; Recunoașterea digitală a modelelor se bazează pe recursiunea emulativă a procesului de recunoaștere a modelelor umane etc. Sa arătat că principiul de dezvoltare a recursivității „proces emulativ” este, de asemenea, baza dezvoltărilor întregii istorii a civilizației și are loc în plus față de tehnologie în alte domenii, cum ar fi economia, mass-media, politica, dezvoltarea structurilor cognitive, arta și matematica, fiecare etapă de dezvoltare în aceste zone fiind bazată pe emularea recursivă a proceselor etapei anterioare de dezvoltare. În acest fel, fazele de dezvoltare succesive cumulative din istoria civilizației (civilizațiile avansate timpurii , timpurile axiale și moderne ) pot fi explicate ca expresii ale recursiunilor „proces-emulative”.

Vezi si

Link-uri web

Wikționar: recursivitate  - explicații ale semnificațiilor, originilor cuvintelor, sinonime, traduceri
Wikționar: recursiv  - explicații ale semnificațiilor, originii cuvintelor, sinonime, traduceri

literatură

Niklaus Wirth: Algoritmi și structuri de date . Ediția a 5-a. BG Teubner, Stuttgart 2000. (ediția I: 1975). ISBN 978-3-519-22250-7 , doi: 10.1007 / 978-3-322-80154-8 .

Observații

Dovezi individuale

  1. Niklaus Wirth , pagina 149: 3. Recursivitate, 3.1. introducere
  2. Niklaus Wirth : Algorithmen und Datenstruktur , BG Teubner 1983, pagina 150: „Esența recursivității este posibilitatea de a defini un număr infinit de obiecte prin intermediul unei afirmații finite.”
  3. a b Bussmann, Hadumod, ed. (1990): Lexikon der Sprachwissenschaft. Alfred-Kröner-Verlag, Stuttgart, p. 640: Recursivitatea este un termen în lingvistică, „care descrie proprietatea formală a gramaticilor de a genera un număr infinit de propoziții cu un inventar finit de elemente și un set finit de reguli”. (În plus față de exemple din limbaj, natură, artă și poezie, citează matematică și programare, de exemplu în uni-leipzig: Recursivitate în limbaj ).
  4. Douglas R. Hofstadter : Gödel, Escher, Bach , dtv , 2004, pagina 137
  5. Vezi de ex. B. Andrew Carnie: Structură constitutivă. A doua editie. Oxford University Press, 2010. Pe tema recursivității v. A. P. 84ff.
  6. Numai pentru limba Pirahã s- a propus teza că nu ar cunoaște nicio recursivitate în gramatică, deoarece nu există propoziții subordonate. Această analiză este controversată, consultați articolul legat pentru detalii.
  7. Pentru aceste cinci tipuri, vezi Davor Löffler: Realități generative I. Civilizația tehnologică ca o nouă vârstă axială și un nivel de civilizație. O antropologie din secolul XXI . Weilerswist: Velbrück Wissenschaft, 2019, pp. 195–204.
  8. Cf. Davor Löffler: Realități Generative I. Civilizația tehnologică ca o nouă vârstă axială și nivel de civilizație. O antropologie din secolul XXI . Weilerswist: Velbrück Wissenschaft, 2019, p. 197 f.
  9. Michael C. Corballis, Mintea recursivă. Originile limbajului uman, gândului și civilizației . Princeton, NJ / Oxford: Princeton University Press, 2013.
  10. Vezi Michael C. Corballis: The Recursive Mind. Originile limbajului uman, gândului și civilizației . Princeton, NJ / Oxford: Princeton University Press, 2013, pp. 82-165.
  11. Cf. Davor Löffler: Realități Generative I. Civilizația tehnologică ca o nouă vârstă axială și nivel de civilizație. O antropologie din secolul XXI . Weilerswist: Velbrück Wissenschaft, 2019, p. 198 f.
  12. ^ W. Brian Arthur: Natura tehnologiei. Ce este și cum evoluează . Londra: Penguin Books, 2009.
  13. A se vedea W. Brian Arthur: Natura tehnologiei. Ce este și cum evoluează . Londra: Penguin Books, 2009, p. 29
  14. A se vedea W. Brian Arthur: Natura tehnologiei. Ce este și cum evoluează . Londra: Penguin Books, 2009, pp. 39-44
  15. Cf. Davor Löffler: Realități Generative I. Civilizația tehnologică ca o nouă vârstă axială și nivel de civilizație. O antropologie din secolul XXI . Weilerswist: Velbrück Wissenschaft, 2019, pp. 199–204.
  16. Miriam N. Haidle, Michael Bolus, Mark Collard și colab.: Natura culturii: un model de opt grade pentru evoluția și extinderea capacităților culturale la omini și alte animale . În: Jurnalul de științe antropologice , Vol. 93, 2015, pp. 43-70.
  17. Vezi Miriam N. Haidle, Michael Bolus, Mark Collard și colab.: Natura culturii: un model de opt grade pentru evoluția și extinderea capacităților culturale la omini și alte animale . În: Revista de științe antropologice , vol. 93, 2015, p. 56 f.
  18. Vezi Miriam N. Haidle, Michael Bolus, Mark Collard și colab.: Natura culturii: un model de opt grade pentru evoluția și extinderea capacităților culturale la omini și alte animale . În: Journal of Anthropological Sciences , vol. 93, 2015, p. 57 f.
  19. Miriam N. Haidle, Michael Bolus, Mark Collard și colab.: Natura culturii: un model de opt grade pentru evoluția și extinderea capacităților culturale la omini și alte animale . În: Jurnalul de științe antropologice , Vol. 93, 2015, p. 58.
  20. Miriam N. Haidle, Michael Bolus, Mark Collard și colab.: Natura culturii: un model de opt grade pentru evoluția și extinderea capacităților culturale la omini și alte animale . În: Jurnalul de Științe Antropologice , Vol. 93, 2015, pp. 58-60.
  21. Un tabel rezumat poate fi găsit în Davor Löffler: Realități generative I. Civilizația tehnologică ca o nouă vârstă axială și un stadiu al civilizației. O antropologie din secolul XXI . Weilerswist: Velbrück Wissenschaft, 2019, p. 600 f.
  22. Cf. Davor Löffler: Realități Generative I. Civilizația tehnologică ca o nouă vârstă axială și nivel de civilizație. O antropologie din secolul XXI . Weilerswist: Velbrück Wissenschaft, 2019, pp. 621-640.