Meniul
AcasăBrowsere

Ce înseamnă recursiv? Diferențele dintre recursive în diferite limbaje de programare. Cum se rezolvă problemele recursive

Din latină recursio (întoarcere). ÎN caz general Acesta este numele dat procesului de repetare a elementelor într-un „mod auto-similar”.

Un exemplu izbitor de recursivitate sunt păpușile de cuib. Definiție recursivă: „o matrioșcă este o păpușă detașabilă din lemn, care conține o păpușă de cuib în interior. dimensiune mai mică" Aceasta este recursivitate în rusă. Și dacă nu ar fi limita capacităților maeștrilor, matrioșca ideală ar intra adânc în sine la nivel atomic. Sau chiar mai profund. Lefty pur și simplu nu avea un domeniu de aplicare suficient de puternic. Limita superioară este teoretic și nelimitată, dar baobabii dimensiune potrivită nu crește pe planeta noastră. În general, conform motive tehnice recursiunea trebuie să fie finită.

În programare (ca și în matematică), recursiunea este procesul prin care o funcție se autoapelează (recursie directă) sau apelează funcția B din interiorul funcției A, care la rândul său conține un apel la funcția A (recursie indirectă sau reciprocă). Desigur, apelurile recursive trebuie să aibă o condiție de ieșire satisfăcătoare, în caz contrar programul se va bloca, ca într-o buclă infinită - dar, spre deosebire de o buclă infinită, o recursivitate infinită se va prăbuși pe un depășire a stivei.

Exemplu de recursivitate

Cel mai enervant exemplu de recursivitate în programarea matematică este calculul factorial. Să nu ne schimbăm tradițiile glorioase. Pentru cei care nu au luat-o încă: N! (factorialul N) este produsul tuturor numere naturale de la unu la N (factorialul zero este 1).
Puteți înmulți prost numere de la 1 la N într-o buclă. Sau puteți construi o funcție factorială(n), care va conține o condiție și un apel către sine. Dacă n este egal cu unu, atunci funcția returnează valoarea 1, în caz contrar returnează valoarea lui n înmulțită cu factorial(n-1).
Schițe în PHP

Funcția factorial($n) ( if ($n == 1) ( return 1; ) else ( return intval($n * factorial($n - 1)); ) )

Aplicații practice ale recursiunii

„Ei bine, de ce este nevoie de asta aici?” - ne va întreba un tânăr cititor nerăbdător - „Prostii științifice, oboseală, tot felul de factoriali... Dar practic, de ce să aplici această recursivitate?”
„La ochiul negru al programării web”, vom răspunde fără ezitare. Și vom justifica acest lucru imediat.

De fapt, există mult mai multe utilizări ale recursiunii în programarea web decât pare. Deoarece recursiunea este, probabil, singura modalitate de a traversa orice structură de arbore atunci când nici dimensiunea, nici adâncimea cuibării nu sunt cunoscute dinainte. Apropo, construirea și parcurgerea graficelor nu se poate face fără el. Acesta este un clasic, domnilor - încercați să căutați în alt mod fisierele necesareîntr-un arbore de directoare Unix și vă va deveni imediat clar că fără recursivitate nu există nicăieri.

Încercați să faceți fără ea construind o hartă a site-ului cu o structură ierarhică de secțiuni sub formă de liste imbricate. Ai prefera să te spânzurezi decât să-l construiești dacă nu știi dinainte exact la câte niveluri este limitată adâncimea cuibării. Și chiar dacă știți, dar încercați să faceți fără recursivitate, atunci în loc de o funcție simplă, transparentă și sigură, veți construi un software greoi „raft pe cârje”. Și când termini și îți ștergi fruntea transpirată, adevărul sumbru al vieții va răsări la tine: dacă schimbi adâncimea cuibării, structura ta de răspândire va înceta instantaneu să funcționeze corect. Prin urmare, este puțin probabil să îl puteți folosi în altă parte.

Recursiune în motoarele de căutare

Da exact. Motoare de căutare Nu există nicio scăpare de recursivitate. De când a fost stabilit obiceiul de a măsura autoritatea unui site (document) după numărul de link-uri, motoarele de căutare au căzut într-o capcană recursivă și le-au lăsat să rătăcească în ea pentru totdeauna (acest lucru este sincer dorinte bune autor). Legătura „greutate” a unui site constă în bucăți mici de „greutate” de la toate cele care leagă la acesta. Pentru a calcula această greutate pentru A, care este referită prin B, C și D, trebuie să calculați greutatea lor, care, la rândul său, este transmisă de tot felul de alții, a căror greutate trebuie să fie calculată... și așa mai departe în întreaga Rețea luată în considerare în motorul de căutare. O problemă complet recursivă. Și spui că este o teorie completă. Cea mai reală practică.

PageRank recursiv de la Google

Creatorii Google și-au publicat algoritmul de bază pentru calcularea PageRank cu mult timp în urmă. Și indiferent cum s-a schimbat de atunci, indiferent câte îmbunătățiri i-au fost adăugate, baza rămâne aceeași. Nu există nicio modalitate de a ști cât de mult PageRank transmite pagina B ca link către pagina A până când nu numărăm ce a primit pagina PageRank B de la toate celelalte pagini care au legat la ea, iar asta nu poate fi cunoscut până când numărăm PageRank din acele pagini... vom continua? Probabil că nu mai este necesar. Este din nou Majestatea Sa Recursiune .

Recursiunea este proprietatea unui obiect de a se imita. Un obiect este recursiv dacă părțile sale arată la fel ca întregul obiect. Recursiunea este folosită pe scară largă în matematică și programare:

  • structuri de date:
    • un grafic (în special arbori și liste) poate fi văzut ca o colecție de un singur nod și un subgraf (graf mai mic);
    • șirul este format din primul caracter și un subșir (șir mai mic);
  • modele de design, de ex. Un obiect de decorare poate include și alte obiecte care sunt și decoratoare. McColm Smith a studiat modelele recursive în detaliu, evidențiind un model general de design în cartea sa - Recursion;
  • funcțiile recursive (algoritmii) se numesc.

Articolul este dedicat analizei complexității algoritmilor recursivi, sunt date informațiile matematice necesare și sunt luate în considerare exemple. În plus, este descrisă posibilitatea înlocuirii recursiunii cu o buclă, recursiunea coadă.

Exemple de algoritmi recursivi

Un algoritm recursiv împarte întotdeauna o problemă în părți care au aceeași structură cu problema originală, dar mai simple. Pentru a rezolva subprobleme, o funcție este numită recursiv, iar rezultatele lor sunt combinate într-un fel. Împărțirea unei sarcini are loc numai atunci când nu poate fi rezolvată imediat (este prea complexă).

De exemplu, sarcina de a procesa o matrice poate fi adesea redusă la procesarea părților sale. Împărțirea în părți se realizează până când acestea devin elementare, adică. suficient de simplu pentru a obține rezultatul fără o simplificare suplimentară.

Găsirea unui element de matrice

Start; căutare(matrice, început, sfârșit, element); caută un element cu element de valoare în matriceîntre indecși începe și sfârșit dacă începe > rezultat final:= fals; elementul nu a fost găsit altfel if array = element result:= true; element găsit altfel rezultat:= search(array, begin+1, end, element) end; returnează rezultatul

Algoritmul împarte matricea originală în două părți - primul element și o matrice de elemente rămase. Există două cazuri simple când separarea nu este necesară - toate elementele au fost prelucrate sau primul element este cel căutat.

În algoritmul de căutare, matricea ar putea fi împărțită diferit (de exemplu, la jumătate), dar acest lucru nu ar afecta eficiența. Dacă matricea este sortată, atunci împărțirea în jumătate este recomandabilă, deoarece La fiecare pas, cantitatea de date prelucrate poate fi redusă la jumătate.

Căutare binară într-o matrice

Căutarea binară se efectuează pe o matrice sortată. La fiecare pas, elementul căutat este comparat cu valoarea situată în mijlocul matricei. În funcție de rezultatele comparației, fie partea stângă, fie partea dreaptă pot fi „aruncate”.

Start; binary_search(array, begin, end, element) ; caută un element cu elementul valoare ; într-o matrice ordonată în ordine crescătoare matrice; între indici start și end dacă begin > end end; return false - element negăsit mid:= (end + begin) div 2; calcularea indicelui elementului din mijlocul părții considerate a matricei dacă matrice = sfârșitul elementului; returnează adevărat (element găsit) dacă matrice< element результат:= binary_search(array, mid+1, end, element) иначе результат:= binary_search(array, begin, mid, element) конец; вернуть результат

Calcularea numerelor Fibonacci

Numerele Fibonacci sunt determinate de o expresie recurentă, adică astfel încât calculul elementului al cărui element este exprimat din elementele anterioare: \(F_0 = 0, F_1 ​​​​= 1, F_n = F_(n-1) + F_(n-2), n > 2\).

Start; Fibonacci(numar) daca numarul = 0 sfarsitul; returnează 0 dacă numărul = 1 capăt; returnează 1 fib_1:= fibonacci(număr-1) fib_2:= fibonacci(număr-2) rezultat:= fib_1 + fib_2 final; returnează rezultatul

Sortare rapida

Algoritm sortare rapida la fiecare pas, selectează unul dintre elemente (referință) și în raport cu acesta împarte matricea în două părți, care sunt procesate recursiv. Elementele mai mici decât cel de susținere sunt așezate într-o parte, iar restul sunt așezate în cealaltă.

Organigrama algoritmului de sortare rapidă

Sortare îmbinare

Algoritmul de sortare de îmbinare se bazează pe capacitatea asociere rapidă tablouri ordonate (sau liste) astfel încât rezultatul să fie ordonat. Algoritmul împarte matricea originală în două părți la întâmplare(de obicei în jumătate), le sortează recursiv și concatenează rezultatul. Diviziunea are loc atâta timp cât dimensiunea matricei este mai mare decât unu, deoarece o matrice goală și o matrice dintr-un element sunt întotdeauna sortate.

Diagrama bloc a sortării îmbinării

La fiecare pas de îmbinare, primul element brut din ambele liste este selectat. Elementele sunt comparate și cel mai mic este adăugat la rezultat și marcat ca procesat. Fuziunea are loc până când una dintre liste este goală.

Start; merge(Matrice1, Dimensiune1, Matrice2, Dimensiune2) ; matricele originale sunt ordonate; rezultatul este o matrice ordonată de lungime Size1+Size2 i:= 0, j:= 0 eternal_loop if i >= Size1 adăugați elemente de la j la Size2 din tabloul Array2 la sfârșitul rezultatului ieșiți din buclă dacă j >= Size2 adăugați elemente de la i la Size1 ale tabloului Array1 la sfârșitul rezultatului ieșiți din buclă dacă Array1[i]< Array2[j] результат := Array1[i] i:= i + 1 иначе (если Array1[i] >= Matrice2[j]) rezultat := Matrice2[j] j:= j + 1 capăt; returnează rezultatul

Analiza algoritmilor recursivi

Când se calculează complexitatea iterațiilor și numărul acestora în cele mai rele, cele mai bune și medii cazuri. Cu toate acestea, nu va fi posibilă aplicarea acestei abordări la o funcție recursivă, deoarece rezultatul va fi o relație de recurență. De exemplu, pentru ca funcția să caute un element dintr-o matrice:

\(
\begin(ecuație*)
T^(căutare)_n = \begin(cases)
\mathcal(O)(1) \quad &\text($n = 0$) \\
\mathcal(O)(1) + \mathcal(O)(T^(căutare)_(n-1)) \quad &\text($n > 0$)
\end(cazuri)
\end(ecuație*)
\)

Relațiile recurente nu ne permit să evaluăm complexitatea - nu le putem compara pur și simplu și, prin urmare, comparăm eficiența algoritmilor corespunzători. Este necesar să se obțină o formulă care să descrie relația de recurență - într-un mod universal pentru a face acest lucru este să selectați o formulă folosind metoda substituției și apoi să demonstrați corespondența formulei cu relația folosind metoda inducției matematice.

Metoda de substituție (iterație).

Constă în înlocuirea secvenţială a părţii recurente într-o expresie pentru a obţine noi expresii. Înlocuirea se efectuează până când este posibil să se prindă principiu generalși exprimați-l ca o formulă nerecurentă. De exemplu, pentru a căuta un element într-o matrice:

\(
T^(căutare)_n = \mathcal(O)(1) + \mathcal(O)(T^(căutare)_(n-1)) =
2\ori\mathcal(O)(1) + \mathcal(O)(T^(căutare)_(n-2)) =
3\ori\mathcal(O)(1) + \mathcal(O)(T^(căutare)_(n-3))
\)

Putem presupune că \(T^(căutare)_n = T^(căutare)_(n-k) + k\times\mathcal(O)(1)\), dar apoi \(T^(căutare)_n = T^ (căutare)_(0) + n\times\mathcal(O)(1) = \mathcal(O)(n)\).

Am derivat formula, dar primul pas conține o presupunere, adică. nu există nicio dovadă a corespondenței formulei cu expresia recurentă – metoda inducției matematice ne permite să obținem demonstrația.

Metoda inducției matematice

Vă permite să demonstrați adevărul unei anumite afirmații (\(P_n\)), constă din doi pași:

  1. dovada afirmației pentru unul sau mai multe cazuri speciale \(P_0, P_1, …\);
  2. din adevărul \(P_n\) (ipoteza inductivă) și cazuri speciale se deduce dovada lui \(P_(n+1)\).

Să demonstrăm corectitudinea ipotezei făcute la estimarea complexității funcției de căutare (\(T^(search)_n = (n+1)\times\mathcal(O)(1)\)):

  1. \(T^(căutare)_(1) = 2\times\mathcal(O)(1)\) este adevărată din condiție (poate fi înlocuită în formula recurentă inițială);
  2. să presupunem adevărul \(T^(căutare)_n = (n+1)\times\mathcal(O)(1)\);
  3. trebuie să demonstrăm că \(T^(căutare)_(n+1) = ((n+1)+1)\times\mathcal(O)(1) = (n+2)\times\mathcal(O ) (1)\);
    1. să substituim \(n+1\) în relația de recurență: \(T^(căutare)_(n+1) = \mathcal(O)(1) + T^(căutare)_n\);
    2. în partea dreaptă a expresiei se poate face o înlocuire pe baza ipotezei inductive: \(T^(căutare)_(n+1) = \mathcal(O)(1) + (n+1)\times \mathcal(O)(1) = (n+2)\times\mathcal(O)(1)\);
    3. afirmația a fost dovedită.

Adesea, o astfel de dovadă este un proces destul de intensiv în muncă, dar este și mai dificil să identifici un model folosind metoda substituției. În acest sens, așa-numitul metoda generala.

Metodă generală (de bază) de rezolvare a relațiilor de recurență

Metoda generală nu este universală; de exemplu, nu poate fi utilizată pentru a estima complexitatea algoritmului de mai sus pentru calcularea numerelor Fibonacci. Cu toate acestea, se aplică tuturor cazurilor de utilizare a abordării împărțiți și cuceriți:

\(T_n = a\cdot T(\frac(n)(b))+f_n; a, b = const, a \geq 1, b > 1, f_n > 0, \forall n\).

Ecuațiile de acest tip se obțin dacă problema inițială este împărțită într-o subsarcini, fiecare procesând elemente \(\frac(n)(b)\). \(f_n\) este complexitatea operațiilor de împărțire a problemei în părți și combinarea soluțiilor. Pe lângă tipul de relație, metoda generală impune restricții asupra funcției \(f_n\), distingând trei cazuri:

  1. \(\există \varepsilon > 0: f_n = \mathcal(O)(n^(\log_b a - \varepsilon)) \Rightarrow T_n = \Theta(n^(\log_b a))\);
  2. \(f_n = \Theta(n^(\log_b a)) \Rightarrow T_n = \Theta(n^(\log_b a) \cdot \log n)\);
  3. \(\există \varepsilon > 0, c< 1: f_n = \Omega(n^{\log_b a + \varepsilon}), f_{\frac{n}{b}} \leq c \cdot f_n \Rightarrow T_n = \Theta(f_n)\).

Corectitudinea afirmațiilor pentru fiecare caz este dovedită formal. Sarcina de a analiza un algoritm recursiv se rezumă acum la determinarea cazului teoremei principale căreia îi corespunde relația de recurență.

Analiza algoritmului de căutare binar

Algoritmul împarte datele sursă în 2 părți (b = 2), dar procesează doar una dintre ele (a = 1), \(f_n = 1\). \(n^(\log_b a) = n^(\log_2 1) = n^0 = 1\). Funcția de împărțire a sarcinii și aranjare a rezultatului crește în aceeași rată cu \(n^(\log_b a)\), ceea ce înseamnă că este necesar să folosiți al doilea caz al teoremei:

\(T^(binarySearch)_n = \Theta(n^(\log_b a) \cdot \log n) = \Theta(1 \cdot \log n) = \Theta(\log n)\).

Analiza algoritmului de căutare

Funcțiile recursive se împart problema initiala per subsarcină (a = 1), datele sunt împărțite într-o singură parte (b = 1). Nu putem folosi teorema principală pentru a analiza acest algoritm, deoarece condiția \(b > 1\) nu este îndeplinită.

Pentru efectuarea analizei se poate folosi metoda substituției sau următorul raționament: fiecare apel recursiv reduce dimensiunea datelor de intrare cu una, ceea ce înseamnă că vor fi n piese în total, fiecare având complexitate \(\mathcal( O)(1)\). Atunci \(T^(căutare)_n = n \cdot \mathcal(O)(1) = \mathcal(O)(n)\).

Analiza algoritmului Merge Sort

Datele sursă sunt împărțite în două părți, ambele fiind procesate: \(a = 2, b = 2, n^(\log_b a) = n\).

La procesarea unei liste, diviziunea poate necesita operațiuni \(\Theta(n)\), în timp ce pentru o matrice este nevoie de timp constant (\(\Theta(1)\)). Cu toate acestea, în orice caz, \(\Theta(n)\) va fi cheltuit pentru conectarea rezultatelor, deci \(f_n = n\).

Se utilizează al doilea caz al teoremei: \(T^(mergeSort)_n = \Theta(n^(\log_b a) \cdot \log n) = \Theta(n \cdot \log n)\).

Analiza intensității muncii de sortare rapidă

ÎN cel mai bun scenariu matricea originală este împărțită în două părți, fiecare conținând jumătate din datele originale. Împărțirea va necesita n operațiuni. Complexitatea compunerii rezultatului depinde de structurile de date utilizate - pentru o matrice \(\mathcal(O)(n)\), pentru o listă legată \(\mathcal(O)(1)\). \(a = 2, b = 2, f_n = b\), ceea ce înseamnă că complexitatea algoritmului va fi aceeași cu cea a sortării de îmbinare: \(T^(quickSort)_n = \mathcal(O)(n \ cdot \log n)\ ).

Cu toate acestea, în cel mai rău caz, minimul sau element maxim matrice. Apoi \(b = 1\), ceea ce înseamnă că nu putem folosi din nou teorema principală. Cu toate acestea, știm că în acest caz vor fi făcute n apeluri recursive, fiecare dintre ele împarte matricea în părți (\(\mathcal(O)(n)\)) - ceea ce înseamnă complexitatea algoritmului \(T^( quickSort)_n = \mathcal(O)(n^2)\).

Când se analizează sortarea rapidă prin înlocuire, ar trebui să se ia în considerare, de asemenea, cele mai bune și cele mai rele cazuri separat.

Coada recursiunii și buclă

Analiza complexității funcțiilor recursive este mult mai complexă decât evaluarea buclelor, dar principalul motiv pentru care buclele sunt de preferat este costul ridicat al apelării unei funcții.

După apel controlul este transferat altă funcție. Pentru a transfera controlul, este suficient să schimbați valoarea registrului contorului programului, în care procesorul stochează numărul instrucțiunii executate curent - în același mod, controlul este transferat ramurilor algoritmului, de exemplu, atunci când se utilizează operator condițional. Cu toate acestea, un apel nu este doar un transfer de control, deoarece după ce funcția apelată își finalizează calculele, trebuie controlul de întoarcere până la punctul în care a fost efectuat apelul și, de asemenea, restabiliți valorile variabilelor locale care existau acolo înainte de apel.

Pentru a implementa acest comportament, se folosește o stivă (stivă de apeluri) - numărul comenzii de returnat și informații despre variabilele locale sunt plasate în ea. Stiva nu este infinită, deci algoritmi recursivi poate duce la depășirea acestuia, în orice caz, lucrul cu acesta poate dura o parte semnificativă a timpului.

În unele cazuri, este destul de ușor să înlocuiți o funcție recursivă cu o buclă, de exemplu, cele discutate mai sus. În unele cazuri este nevoie de mai mult creativitate, dar cel mai adesea o astfel de înlocuire este posibilă. În plus, există un tip special de recursivitate unde este apelul recursiv ultima operatie realizat de funcţia. Evident, în acest caz funcția de apelare nu va schimba rezultatul în niciun fel, ceea ce înseamnă că nu are rost să returnăm controlul. Astfel de recursiunea se numește recursiune de coadă— compilatorii îl înlocuiesc automat cu o buclă.

Adesea ajută să faci o recursivitate de coadă metoda parametrilor acumulativi, care constă în adăugarea funcției unui argument acumulator suplimentar în care se acumulează rezultatul. Funcția efectuează calcule pe acumulator înainte de apelul recursiv. Un exemplu bun Folosind această tehnică este funcția de a calcula factorial:
\(fact_n = n \cdot fact(n-1) \\
fact_3 = 3 \cdot fact_2 = 3 \cdot (2 \cdot fact_1) = 3\cdot (2 \cdot (1 \cdot fact_0)) = 6 \\
fact_n = factCoada_(n, 1) \\
\\
factCoada_(n, acumulator) = factTail(n-1, acumulator \cdot n)\\
factTail_(3, 1) = factTail_(2, 3) = factTail_(1, 6) = factTail_(0, 6) = 6
\)

Ca exemplu mai complex, luați în considerare funcția pentru calcularea numerelor Fibonacci. Funcția principală apelează o funcție auxiliară care utilizează metoda parametrilor de acumulare, trecând ca argumente valoarea initiala un iterator și doi acumulatori (cele două numere Fibonacci anterioare).

Start; Fibonacci(număr) returnare fibonacci(număr, 1, 1, 0) sfârşit început; Fibonacci(număr, iterator, fib1, fib2) if iterator == număr return fib1 return fibonacci(număr, iterator + 1, fib1 + fib2, fib1) final

O funcție cu un parametru de acumulare returnează rezultatul acumulat dacă se calculează numărul specificat de numere, în caz contrar, crește contorul, calculează un nou număr Fibonacci și efectuează un apel recursiv. Optimizarea compilatoarelor poate detecta că rezultatul unui apel de funcție este transmis neschimbat la ieșirea funcției și îl poate înlocui cu o buclă. Această tehnică este deosebit de relevantă în limbajele de programare funcționale și logice, deoarece în ele programatorul nu poate folosi în mod explicit constructe ciclice.

Literatură

  1. Server Qt cu mai multe fire. Bazin de fire. Model de decorator[ Resursa electronica] - modul de acces: https://site/archives/1390. Data accesului: 21.02.2015.
  2. Jason McColm Smith: Trad. din engleza - M.: SRL „I.D. Williams”, 2013. - 304 p.
  3. Skiena S. Algoritmi. Ghid de dezvoltare.-ed. a II-a: trad. din engleză-SPb.: BHV-Petersburg, 2011.-720 p.: ill.
  4. Vasiliev V. S. Analiza complexității algoritmilor. Exemple [Resursă electronică] - mod de acces: https://site/archives/1660. Data accesului: 21.02.2015.
  5. A. Aho, J. Hopcroft, J. Ullman, Structuri de date și algoritmi, M., Williams, 2007.
  6. Miller, R. secvenţial şi algoritmi paraleli: Abordare generală/ R. Miller, L. Boxer; BANDĂ din engleza - M.: BINOM. Laboratorul de cunoștințe, 2006. - 406 p.
  7. Sergievski G.M. Programare funcțională și logică: manual. manual pentru elevii superioare manual stabilimente / G.M. Sergievski, N.G. Volcenkov. - M.: Centrul de editură „Academia”, 2010.- 320 p.

Subrutinele din Pascal se pot referi la ele însele. Acest tip de tratament se numește recursiunea .

Pentru ca un astfel de acces să nu fie infinit, textul subrutinei trebuie să conțină o condiție la atingerea căreia să nu aibă loc accesul suplimentar la subrutină.

Exemplu .

Să ne uităm la un puzzle matematic din cartea lui J. Arsac „Jocuri de programare și puzzle-uri”.

Să construim o succesiune de numere după cum urmează: luăm un întreg i>1. Următorul termen din șir este egal cu i/2 dacă i este par și 3 i+1 dacă i este impar. Dacă i=1, atunci secvența se oprește.

Matematic, caracterul finit al secvenței, indiferent de i-ul inițial, nu a fost dovedit, dar în practică șirul se oprește întotdeauna.

Utilizarea recursiunii a făcut posibilă rezolvarea problemei fără a utiliza bucle, atât în ​​programul principal, cât și în procedură.

Exemplu de program folosind recursiunea

Programul Arsac;
Var mai întâi: cuvânt;
Procedura posledov (i: cuvânt);
ÎNCEPE
Writeln(i);
Daca i=1 atunci iesire;
Dacă impar(i) atunci posledov(3*i+1) else posledov(i div 2);
Sfârşit;
ÎNCEPE
Scrie ("introduceți prima valoare"); readln(primul);
Posledov (primul);
Readln;
Sfârşit.

Programatorul dezvoltă un program, reducând problema inițială la altele mai simple. Printre aceste sarcini poate fi și cea originală, dar într-o formă simplificată. De exemplu, pentru a calcula F(N), ar putea fi necesar să calculați F(N-1). Cu alte cuvinte, o parte a algoritmului pentru calcularea unei funcții va fi calculul aceleiași funcții.

Se numește un algoritm care este propria sa parte recursiv. Adesea, baza unui astfel de algoritm este o definiție recursivă.

N! = (N-1)!* N, dacă N=0, atunci N!= 1

Orice definiție recursivă constă din două părți. O parte definește un concept prin ea, cealaltă parte prin alte concepte.

Exemplu de algoritm recursiv

2n= 2 n-1*2, dacă n=0, atunci 2 n= 1

Procedura este recursiv, dacă se referă la sine în mod direct sau indirect (prin alte proceduri).

Rețineți că, cu acces indirect, toate procedurile din lanț sunt recursive.

Tot ce se spune despre proceduri se aplică în întregime funcțiilor.

Exemplu de funcție factorială recursivă

Funcție factorială (N: întreg) : longint;
ÎNCEPE
Dacă N= 0 atunci
Factorial:= 1
Else Factorial:= factorial(N-1) * N
Sfârşit;

Recursie din interior

Acest lucru poate părea surprinzător, dar apelarea unei proceduri în sine nu este diferită de apelarea unei alte proceduri. Ce se întâmplă dacă o procedură cheamă alta? ÎN schiță generală ca urmare a:

  • parametrii trecuți procedurii sunt localizați în memorie (dar nu parametri variabili!);
  • valorile variabilelor interne ale procedurii de apelare sunt stocate în altă parte în memorie;
  • se reține adresa de retur la procedura de apelare;
  • controlul este transferat la procedura apelată.

Dacă o procedură este apelată din nou dintr-o altă procedură sau de la ea însăși, același cod va fi executat, dar va funcționa cu valori diferite ale parametrilor și variabilelor interne. Acesta este ceea ce face posibilă recursiunea.

Fie procedura recursivă Power(X, N, Y) ridică numărul X la puterea N și returnează rezultatul Y .

Un exemplu de procedură recursivă care ridică un număr la o putere

Puterea de procedură (X: real; N: întreg; var Y: real);
ÎNCEPE
Dacă N=0 atunci
Y:= 1
Else Begin Power(X, N-1,Y);
Y:= Y*X;
Sfârşit ;
Sfârşit ;

Să monitorizăm starea memoriei în timpul executării apelului la această procedură Power(5,3, Y). Săgeata „->” înseamnă intrarea în procedură, săgeata „

Se numește numărul de copii ale variabilelor care sunt simultan în memorie adâncimea recursiunii . După cum se vede din exemplu, mai întâi crește și apoi se contractă.

Rezuma.

  • O procedură sau o funcție care se autoinvocă se numește recursivă;
  • Pentru a finaliza procesul recursiv, algoritmul unei funcții recursive (procedură) trebuie să aibă o condiție care să asigure finalizarea imediată a funcției (procedurii).

Să scriem un program pentru a calcula o funcție definită după cum urmează:

F(1)=1; F(2n)=F(n); F(2n+1)=F(n)+F(n+1)

Soluţie: Din definiție este clar că calcularea unei funcții dintr-un argument se reduce la calcularea aceleiași funcții dintr-un argument mai mic, iar procesul de reducere a argumentului continuă până când argumentul este unul. Se determină valoarea funcției din unitate.

Astfel, munca algoritmului va consta dintr-un anumit număr de pași, la fiecare dintre care se vor efectua două acțiuni:

  • Determinarea dacă un argument este par sau impar. Alegerea formulei de calcul depinde de aceasta;
  • Efectuați calcule. De fapt, acest lucru se va reduce la definirea unui nou argument al funcției.
Exemplu de program recursiv de evaluare a funcțiilor

Primer program;
Useescrt;
Var
N, a: întreg;
Funcția f(n:întreg):întreg;
ÎNCEPE
Dacă n =1 atunci
f:=1 (condiția de terminare a recursiunii)
Altfel
ÎNCEPE
Dacă impar (n)
apoi începe
n:= n div 2;
f:=f(n)+f(n+1)
Sfârşit
altfel începe
n:= n div 2;
f:=f(n)
Sfârşit;
Sfârşit ;
Sfârşit ;
clrscr;
scrie ("Introduceți un număr - ");
readln(n);
a:=f(n);
scrie(" rezultat – ", a);
Sfârşit.

Program recursiv de construcție a fulgilor de zăpadă

Scrieți un program pentru a crea o imagine pe ecran:

Imaginea este construită după următoarea regulă: se construiește un cerc cu o rază dată r. Apoi, în puncte diametral opuse ale cercului (x- r și x+ r), se construiește din nou un cerc de rază mai mică (r = 3 r/5). Pentru fiecare cerc mai mic, un cerc de rază mai mică este din nou construit în puncte diametral opuse și așa mai departe, până când raza scade la 10.

programul se repetă;
folosește graficul;
var x,y,r,d,m:intger;
var i:intger;
ÎNCEPE
dacă r cerc(x,y,r);
pentru i:=1 până la 1000 do; (doar o buclă de întârziere)
ris(x+r,y,r*3 div 5);
ris(x-r,y,r*3 div 5);
Sfârşit ;
începe (începutul programului principal)
d:=detecta;
x:=320;
y:=240;
r:=120;
ris(x,y,r);
readln;
Sfârşit.

După cum se poate observa din figură, aceleași fragmente se repetă din nou aici. Construcția se realizează astfel: pe un cerc de rază dată r se iau 6 puncte egal distanțate (începând dintr-un unghi de 0 0, cu pas de ?/3), se trasează raze din fiecare punct spre centru. a cercului. Apoi fiecare dintre aceste puncte acționează ca centrul unui nou cerc mai mic, cu raza r=2 r/5. Pe fiecare cerc mai mic, sunt luate din nou 6 puncte egal distanțate, din care sunt construite raze spre centru și așa mai departe, până când raza devine mai mică sau egală cu 1.

program zăpadă;
folosește graph, crt;
var
x,y,r,d,m:întreg;
procedura ris(x,y,r:intger);
var
x1,y1,t:întreg;
ÎNCEPE
dacă r pentru t:=0 până la 6 face
ÎNCEPE
x1:=x+trunc(r*cos(t*pi/3));
y1:=y+trunc(r*sin(t*pi/3));
line(x,y,x1,y1);
ris(x1,y1,r*2 div 5);
întârziere (500);
Sfârşit;
Sfârşit;
ÎNCEPE
d:=detecta;
initgraph(d,m,"e:\bp\bgi");
x:=320;
y:=240;
r:=80;
ris(x,y,r);
readln;
Sfârşit.

Un exemplu de „Curba Dragonului”.

Să ne uităm la un exemplu de rezolvare a unei alte probleme clasice: „Curba Dragonului”.

Imaginea curbei Dragon arată astfel:

Foarte frumos, nu-i așa? Să ne dăm seama cum se obține această curbă.

Să luăm o fâșie lungă de hârtie și să o împăturim în jumătate, apoi să o întoarcem cu 90 de grade. Dacă te uiți la bandă din lateral, vei obține o linie întreruptă de două secțiuni perpendiculare: vezi. orez. A. Acum pliați banda în jumătate de două ori și, de asemenea, întoarceți-o la 90 de grade de două ori, așa cum se arată în orez. b. Obținem o linie întreruptă formată din patru segmente, iar unghiul dintre segmentele adiacente este de 90. În cele din urmă, dacă plierea și desfacerea benzii se efectuează de trei ori, rezultatul va fi figura prezentată în orez. V. Continuând acest proces, puteți obține o curbă similară cu cea afișată în orez. 1. Această curbă bizară se numește curba dragonului. Metoda de construcție sugerează că nu are auto-intersecții.

Curba dragonului a fost descrisă pentru prima dată în literatura populară în Scientific American în 1967. O notă despre aceasta a apărut în coloana „Jocuri matematice”, scrisă de Martin Gardner. Inițial, a fost folosit numele complet al curbei - „dragon Harter-Hateway”, care i-a fost dat de fondator. fractal computerizat geometrie Benoit Mandelbrot, după care poartă numele celebrului set. Mai târziu au început să vorbească pur și simplu despre curba dragonului. Mai sus am descris unul dintre algoritmii pentru construirea unei curbe. În opinia noastră, este oarecum confuz (deși destul de simplu de implementat). Iată o descriere a algoritmului de construcție a curbei, care este aproape de cel folosit de Martin Gardner.

Considerați segmentul orizontal ca o curbă dragon de ordinul zero. Împărțiți segmentul în jumătate și construiți un unghi drept pe el, așa cum se arată în orez. A).

Obținem o curbă dragon de ordinul întâi. Pe laturile unghiului drept construim din nou unghiuri drepte ( orez. b).

În acest caz, vârful primului unghi este întotdeauna la dreapta, când este privit din punctul A (începutul curbei) de-a lungul primului segment al curbei, iar direcțiile în care sunt construite vârfurile unghiurilor rămase alternează . Pe orez. c) și d) arată curbele dragonului de ordinul trei și, respectiv, al patrulea.

program dragon;
folosește graficul;
var k,d,m:intger;
procedura ris(x1,y1,x2,y2,k:intger);
var xn,yn:intger;
ÎNCEPE
dacă k>0 atunci
ÎNCEPE
xn:=(x1+x2) div 2 +(y2-y1) div 2;
yn:=(y1+y2) div 2 -(x2-x1) div 2;
ris(x1,y1,xn,yn,k-1);
ris(x2,y2,xn,yn,k-1);
Sfârşit
else start line(x1,y1,x2,y2); Sfârşit;
Sfârşit;
ÎNCEPE
readln (k); (setează ordinea curbei)
d:=detecta;
initgraph(d,m,"e:\bp\bgi");
ris(200.300.500.300,k);
readln;
Sfârşit.

La Universitatea Națională din Ucraina de Est, numită după Vladimir Dahl

Recursiune

Informatica si tehnologia calculatoarelor

© Veligura A.V., Departamentul de Cibernetică Economică, 2004

recursivitate - metoda puternica programare, care vă permite să împărțiți o problemă în părți din ce în ce mai mici până când acestea devin atât de mici încât soluția acestor subprobleme se reduce la un set de operații simple.

Odată ce câștigi experiență cu recursiunea, o vei vedea peste tot. Mulți programatori care au stăpânit recent recursiunea se lasă duși de cap și încep să o folosească în situații în care este inutilă și uneori dăunătoare.

Ce este recursiunea?

Recursiunea apare atunci când o funcție sau o subrutină se autoapelează. Drept recursiunea(recursie directă) arată cam așa:

Funcție Factorial (num As Long) As Long

Factorial = num * Factorial(num - 1)

Când recursiunea indirectă(recursiune indirectă) o procedură recursivă apelează o altă procedură, care la rândul său o apelează pe prima:

Ping sub privat (număr ca întreg)

Private Sub Pong (număr ca întreg)

Recursiunea este utilă atunci când se rezolvă probleme care se descompun în mod natural în mai multe subprobleme, fiecare dintre ele fiind mai mult caz simplu sarcina originală. Vă puteți gândi la un copac ca la un „trunchi” cu doi copaci mai mici pe el. Atunci poți scrie procedura recursivă pentru desenarea copacilor:

Sub DrawTree privat()

Desenați „trunchiul”

Desenați un copac mai mic rotit -45 de grade

Desenați un copac mai mic rotit la 45 de grade

Deși recursiunea poate face unele probleme mai ușor de înțeles, oamenii, în general, nu gândesc recursiv. De obicei, se străduiesc să despartă sarcinile complexe în sarcini mai mici care pot fi finalizate una după alta până la finalizare. De exemplu, pentru a picta un gard viu, puteți începe de la marginea din stânga și puteți continua spre dreapta până când ați terminat. Probabil că nu vă gândiți la posibilitatea de a colora recursiv jumătatea stângă a gardului mai întâi și apoi de a colora recursiv jumătatea dreaptă atunci când efectuați o sarcină ca aceasta.

Pentru a gândi recursiv, trebuie să împărțiți o problemă în subprobleme, care pot fi apoi împărțite în subprobleme mai mici. La un moment dat, sarcinile secundare devin atât de simple încât pot fi efectuate direct. Când subsarcinile sunt finalizate, subsarcinile mai mari care sunt compuse din ele vor fi, de asemenea, finalizate. Sarcina inițială va fi finalizată când toate sarcinile sale secundare sunt finalizate.

    1. Pericolele recursiunii

      1. Recursie infinită

Cel mai evident pericol al recursiunii este recursiunea infinită. Dacă algoritmul este construit incorect, funcția poate pierde condiția de oprire a recursiunii și poate fi executată la nesfârșit. Cel mai simplu mod de a face această greșeală este să uitați pur și simplu să verificați condiția de oprire, așa cum se face în următoarea versiune eronată a funcției factoriale. Deoarece funcția nu verifică dacă a fost atinsă condiția de oprire a recursiunii, se va apela la nesfârșit.

Funcție privată BadFactorial(num As Integer) As Integer

BadFactorial = num * BadFactorial (num - 1)

O funcție se poate autodenomina și pe termen nelimitat dacă condiția de oprire nu termină totul moduri posibile recursiunea. În următoarea versiune buggy a funcției factoriale, funcția se va apela la nesfârșit dacă valoarea de intrare nu este un număr întreg sau dacă este mai mică de 0. Aceste valori nu sunt valori de intrare valide pentru funcția factorială, deci o verificare poate fi necesară într-un program care utilizează valorile de intrare ale acestei funcții. Cu toate acestea, va fi mai bine dacă funcția efectuează această verificare singură.

Funcție privată BadFactorial2(num As Double) As Double

BadFactorial2 = 1

BadFactorial2 = num * BadFactorial2(num-1)

Următoarea versiune a funcției Fibonacci este mai mult exemplu complex. Condiția sa de oprire a recursiunii oprește doar câteva căi recursive și are aceleași probleme ca BadFactorial2 dacă valorile de intrare sunt negative sau neîntregi.

Funcție privată BadFib(num As Double) As Double

BadFib = BadPib (număr - 1) + BadFib (număr - 2)

Ultima problemă cu recursiunea infinită este că „infinit” înseamnă de fapt „până când spațiul stivei este epuizat”. Chiar și procedurile recursive bine scrise vor duce uneori la o depășire a stivei și la blocarea. Următoarea funcție, care calculează suma lui N + (N - 1) + ... + 2 +1, face ca spațiul de stivă să fie epuizat pentru valori mari ale lui N. Cea mai mare valoare posibilă a lui N la care programul va funcționa în continuare depinde de configurația computerului dvs.

Funcție privată BigAdd(N As Double) As Double

Daca N<= 1 Then

BigAdd=N + BigAdd(N - 1)

Programul BigAdd de pe discul exemplu demonstrează acest algoritm. Testați cât de mare o valoare de intrare puteți introduce în acest program înainte de a provoca o depășire a stivei pe computer.

Functii: dat recursiv o funcție în definiția sa se conține; în special, o funcție definită printr-o formulă recurentă este recursivă. Astfel, într-o expresie puteți da un set infinit de moduri de a calcula o funcție, defini multe obiecte prin tine folosind definiții private specificate anterior.

Date

Struct element_of_list ( element_of_list * next; /* referință la următorul element de același tip */ int date; /* unele date */ ) ;

Structura recursivă a datelor dictează adesea utilizarea recursiunii pentru a procesa datele.

În fizică

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

Un alt exemplu de recursivitate infinită este efectul de autoexcitare (feedback pozitiv) în circuitele 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ă

Capacitatea unei limbi de a genera propoziții și construcții imbricate. Oferta de baza" pisica a mâncat șoarecele» poate fi extins prin recursivitate ca Vanya a ghicit că pisica a mâncat șoarecele, apoi 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, recent s-a discutat activ despre posibila lipsă de recursivitate într-una dintre limbile Amazonului - Pirahã, care este remarcată de lingvistul Daniel Everett ( Engleză) .

În cultură

Cele mai multe glume despre recursivitate se referă la recursiunea infinită, în care nu există nicio condiție de ieșire, de exemplu, celebra zicală: „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:

Mai multe povestiri ale lui Stanislaw Lem sunt dedicate incidentelor (posibile) cu recursivitate infinită:

  • povestea despre Ion liniștitul „A paisprezecea călătorie” din „Jurnalele stelelor lui Iyon liniștitul”, în care eroul trece secvenţial de la un articol despre sepulki la un articol despre sepulcare, de acolo la un articol despre sepulcarie, care din nou conține o referire la articolul „sepulki”:

Am gasit urmatoarele informatii scurte:
„SEPULKI sunt un element important al civilizației Ardrite (q.v.) de pe planeta Enteropia (q.v.). Vezi SEPULCARIA."
Am urmat acest sfat si am citit:
„SEPULCARIA - dispozitive pentru sepulție (vezi).”
Am căutat „Sepulenia”; se citi:
„SEPULAREA este ocupația Ardriților (q.v.) de pe planeta Enteropia (q.v.). Vezi SEPULS.”

Lem S. „Jurnalele stelelor lui Iyon the Quiet. Călătoria paisprezece.”

  • O poveste din „Cyberiad” despre o mașină inteligentă care avea suficientă inteligență și lene pentru a construi una similară pentru a rezolva o anumită problemă și a-i încredința soluția (rezultatul a fost o recursivitate fără sfârșit, când fiecare mașină nouă a construit una similară și i-a delegat sarcina).
  • Acronime recursive: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor), etc.

Vezi si

  • Secvența de întoarcere

Note


Fundația Wikimedia. 2010.

  • Memorie video
  • Radiatie electromagnetica

Vedeți ce este „Recursiune” în alte dicționare:

    recursiunea- return, repetition Dicționar de sinonime rusești. substantiv recursiv, număr de sinonime: 1 ... Dicţionar de sinonime

    recursiunea- - [] recursivitate În sens general, calculul unei funcții folosind un algoritm specific. Exemple de astfel de algoritmi sunt formule recurente care derivă calculul unui termen dat... ... Ghidul tehnic al traducătorului

    Recursiune- în sens general, calculul unei funcții folosind un algoritm specific. Exemple de astfel de algoritmi sunt formulele recurente, care derivă calculul unui termen dat dintr-o secvență (cel mai adesea numeric) din calculul mai multor ... Dicționar economic și matematic

    Recursiune- Un model terapeutic în care o condiție sau un criteriu formulat în enunțul original este luat și aplicat enunțului în sine. De exemplu: nu am timp. Cât timp ai avut de petrecut pentru a te asigura că... ... Mare enciclopedie psihologică

    RECURSIE- o metodă de determinare a funcțiilor, care face obiectul de studiu în teoria algoritmilor și a altor ramuri ale matematicii. logică. Această metodă a fost folosită mult timp în aritmetică pentru a determina secvențe numerice (progresie, numere Fibonacci etc.).... ... Enciclopedie matematică

    recursiunea- (fond) (lat. recursio return). Una dintre cele trei faze ale articulației sunetului, indentarea. Transferarea organelor vorbirii într-o stare calmă sau începerea articulării sunetului următor. În cuvântul odihnă, recursiunea (indentarea) atunci când se articulează [t] se poate suprapune ... ... Dicţionar de termeni lingvistici T.V. Mânz