Recursie în logică. Coada recursiunii și buclă

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 pe sine.

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 aceasta 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 elementul valoare în matricea dintre indicii de început și de final dacă begin > end result:= false; 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

La fiecare pas, algoritmul de sortare rapidă 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

Baza algoritmului de sortare de îmbinare este capacitatea de a combina rapid matrice ordonate (sau liste), astfel încât rezultatul să fie ordonat. Algoritmul împarte matricea originală în două părți aleatoriu (de obicei în jumătate), le sortează recursiv și combină 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 recurentă - o modalitate universală de a face acest lucru este de a selecta formula folosind metoda substituției și apoi de a demonstra 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 face până când este posibil să se înțeleagă principiul general și să-l exprime sub forma unei formule nerecurente. 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^(search)_(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, se folosește așa-numita metodă generală.

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

Metoda generală nu este universală, de exemplu, nu poate fi folosită 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ția recursivă împarte problema inițială într-o singură 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 caz, 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, elementul minim sau maxim al matricei va fi selectat în mod constant ca referință. 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ă modificați valoarea registrului contorului programului, în care procesorul stochează numărul instrucțiunii care se execută în prezent - în același mod, controlul este transferat ramurilor algoritmului, de exemplu, atunci când se utilizează un operator condiționat. 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ă, așa că algoritmii recursivi pot duce la depășirea stivei și, în orice caz, lucrul cu acesta poate dura o perioadă semnificativă de timp.

Î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 necesară o abordare mai creativă, dar cel mai adesea o astfel de înlocuire este posibilă. În plus, există un tip special de recursivitate în care apelul recursiv este ultima operație efectuată de funcție. Evident, în acest caz, funcția de apelare nu va schimba în niciun fel rezultatul, 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 a cozii 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 bun exemplu de utilizare a acestei tehnici este funcția 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) = factCoada(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 valoarea inițială a iteratorului și doi acumulatori (cele două numere Fibonacci anterioare) ca argumente.

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 relevantă în special î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[Resursă electronică] - 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 [Resurse electronice] - 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. Algoritmi secvențiali și paraleli: O 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 superiori manual stabilimente / G.M. Sergievski, N.G. Volcenkov. - M.: Centrul de editură „Academia”, 2010.- 320 p.

Din latină recursio (întoarcere). În general, acesta este numele dat procesului de repetare a elementelor într-o manieră „auto-similară”.

Un exemplu izbitor de recursivitate sunt păpușile de cuib. Definiție recursiva: „o păpușă de cuib este o păpușă detașabilă din lemn, care conține o păpușă mai mică în interior.” 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, de asemenea, teoretic nelimitată, dar baobabii de o dimensiune adecvată nu cresc pe planeta noastră. În general, din 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 ei 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 numerelor 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 fișierele necesare într-un arbore de directoare Unix într-un alt mod și vă va deveni imediat clar că fără recursire nu veți ajunge 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. De asemenea, motoarele de căutare nu au de unde să scape 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 (aceasta este dorința sinceră a autorului). 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 și asta nu poate fi știut 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 .

YouTube enciclopedic

• 1 / 5

  În matematică, recursiunea are de-a face cu metoda de definire a funcțiilor și a seriilor de numere: definite recursiv o funcție își determină valoarea apelându-se cu alte argumente. În acest caz, sunt posibile două opțiuni:

  e = 2 + 2 2 + 3 3 + 4 4 + … = 2 + f (2) (\displaystyle e=2+(\cfrac (2)(2+(\cfrac (3)(3+(\cfrac () 4)(4+\ldots ))))))\;=2+f(2)), Unde f (n) = n n + f (n + 1) (\displaystyle f(n)=(\cfrac (n)(n+f(n+1)))) Un calcul direct folosind formula de mai sus va provoca o recursivitate 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 a calcula aproximativ valoarea lui e, este suficient să limitați artificial adâncimea recursiunii la un număr prestabilit și, la atingerea acestuia, să o utilizați în schimb f (n) (\displaystyle f(n)) unitate.

  Un alt exemplu de recursivitate în matematică este o serie de numere dată printr-o formulă recurentă, când fiecare termen următor al seriei este calculat ca rezultat al unei funcții a n termeni anteriori. Astfel, folosind o expresie finită (care este o combinație între o formulă recurentă și un set de valori pentru primii n termeni ai unei serii), poate fi dată definiția unei serii infinite.

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

  Deoarece un număr infinit de obiecte imbricate nu pot fi adăpostite într-o memorie 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 sfârșitul acesteia.

  Recursiunea este un fenomen destul de comun care apare nu numai în domeniile științei, ci și în viața de zi cu zi. De exemplu, efectul Droste, triunghiul Sierpinski etc. Cel mai simplu mod de a vedea recursiunea este să îndreptați camera Web spre ecranul monitorului computerului, desigur, după ce ați pornit-o mai întâi. Astfel, camera va înregistra imaginea ecranului computerului și o va afișa pe acest ecran, va fi ceva ca o buclă închisă. Ca urmare, vom observa ceva asemănător cu un tunel.

  În programare, recursiunea este strâns legată de funcții, mai precis, datorită funcțiilor din programare există un asemenea lucru precum recursiunea sau o funcție recursivă. În cuvinte simple, recursiunea este definirea unei părți a unei funcții (metode) prin ea însăși, adică este o funcție care se autoinvocă, direct (în corpul său) sau indirect (prin altă funcție). Problemele recursive tipice sunt: ​​găsirea n!, numerele Fibonacci. Am rezolvat deja astfel de probleme, dar folosind bucle, adică iterativ. În general, tot ceea ce este rezolvat iterativ poate fi rezolvat recursiv, adică folosind o funcție recursivă. Întreaga soluție se rezumă la rezolvarea cazului principal sau, așa cum se mai numește, cazul de bază. Există un pas de recursivitate sau un apel recursiv. În cazul în care o funcție recursivă este apelată pentru a rezolva o problemă complexă (nu cazul de bază), se efectuează un număr de apeluri sau pași recursivi pentru a reduce problema la una mai simplă. Și așa mai departe până obținem o soluție de bază. Să dezvoltăm un program care declară o funcție recursivă care calculează n!

  „stdafx.h” #include << "Enter n!: "; cin >>n; cout<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

  // cod Cod::Blocuri

  // Cod Dev-C++

  // factorial.cpp: Definește punctul de intrare pentru aplicația consolă. #include folosind namespace std; unsigned long int factorial(unsigned long int // prototip al unei funcții recursive int i = 1); // inițializarea unei variabile globale pentru a număra numărul de apeluri recursive unsigned long int rezultat; // variabilă globală pentru stocarea rezultatului returnat al funcției recursive int main(int argc, char* argv) ( int n; // variabilă locală pentru trecerea numărului introdus de la tastatură cout<< "Enter n!: "; cin >>n; cout<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

  ÎN rândurile 7, 9, 21 Tipul de date este declarat unsigned long int , deoarece valoarea factorialului crește foarte repede, de exemplu, deja 10! = 3.628.800 Dacă dimensiunea tipului de date nu este suficientă, atunci rezultatul va fi o valoare complet incorectă. Codul declară mai mulți operatori decât sunt necesari pentru a găsi n!. Acest lucru se face astfel încât, după rulare, programul să arate ce se întâmplă la fiecare pas al apelurilor recursive. Vă rugăm să rețineți liniile de cod evidențiate, rândurile 23, 24, 28 este o soluție recursivă pentru n!. Rândurile 23, 24 sunt soluția de bază a unei funcții recursive, adică de îndată ce valoarea din variabilă f va fi egal cu 1 sau 0 (din moment ce știm că 1! = 1 și 0! = 1), apelurile recursive se vor opri, iar valorile vor începe să fie returnate pentru fiecare apel recursiv. Când se întoarce valoarea pentru primul apel recursiv, programul va returna valoarea factorialului calculat. ÎN linia 28 funcția factorial() se autoapelează, dar argumentul său este cu unul mai puțin. Argumentul se reduce de fiecare dată pentru a ajunge la o anumită soluție. Rezultatul programului (vezi Figura 1).

  Introdu n!: 5 Rezultatul pasului 1= 0 Rezultatul pasului 2= 0 Rezultatul pasului 3= 0 Rezultatul pasului 4= 0 5!=120

  Figura 1 - Recursiune în C++

  Pe baza rezultatului programului, fiecare pas este clar vizibil și rezultatul la fiecare pas este zero, cu excepția ultimului apel recursiv. A fost necesar să se calculeze cinci factoriali. Programul a făcut patru apeluri recursive, iar la al cincilea apel a fost găsit cazul de bază. Și odată ce programul a avut o soluție pentru cazul de bază, a rezolvat pașii anteriori și a scos rezultatul general. În figura 1, sunt vizibili doar patru pași, deoarece în pasul al cincilea a fost găsită o soluție parțială, care în cele din urmă a returnat soluția finală, adică 120. Figura 2 prezintă schema de calcul recursiv 5!. Diagrama arată clar că primul rezultat este returnat atunci când se ajunge la o anumită soluție, dar nu imediat, după fiecare apel recursiv.

  Figura 2 - Recursiune în C++

  Deci să găsesc 5! trebuie sa stii 4! și înmulțiți-l cu 5; 4! = 4*3! și așa mai departe. Conform schemei prezentate în Figura 2, calculul se va reduce la găsirea unui caz special, adică 1!, după care valorile vor fi returnate la fiecare apel recursiv pe rând. Ultimul apel recursiv va returna valoarea 5!.

  Să reluăm programul pentru găsirea factorialului astfel încât să obținem un tabel de factoriali. Pentru a face acest lucru, vom declara o buclă for în care vom apela funcția recursivă.

  folosind namespace std; unsigned long int factorial(unsigned long int // prototip al unei funcții recursive int i = 1); // inițializarea unei variabile globale pentru a număra numărul de apeluri recursive unsigned long int rezultat; // variabilă globală pentru stocarea rezultatului returnat al funcției recursive int main(int argc, char* argv) ( int n; // variabilă locală pentru trecerea numărului introdus de la tastatură cout<< "Enter n!: "; cin >>n; pentru (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i <>n; pentru (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i <> <= entered_number; counter++) cout << setw(2) <

  // cod Cod::Blocuri

  // Cod Dev-C++

  // fibonacci.cpp: definește punctul de intrare pentru aplicația de consolă. #include // bibliotecă pentru formatarea informațiilor afișate pe ecran #include folosind namespace std; unsigned long fibonacci(unsigned long // prototip al unei funcții recursive pentru căutarea numerelor din seria Fibonacci int main(int argc, char* argv) ( unsigned long entered_number; cout);<< "Enter number from the Fibonacci series: "; cin >> număr_introdus; for (int counter = 1; counter<= entered_number; counter++) cout << setw(2) <#include folosind namespace std; void tower(int, int, int, int); // declararea unui prototip al unei funcții recursive int count = 1; // variabilă globală pentru numărarea numărului de pași int _tmain(int argc, _TCHAR* argv) ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>număr; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> tijă_de bază; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> final_rod; int help_rod; // bloc pentru determinarea numărului tijei auxiliare, analizând numerele tijei inițiale și finale if (basic_rod != 2 && final_rod != 2) help_rod = 2; else if (basic_rod != 1 && final_rod != 1) help_rod = 1; else if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(// lansează o funcție recursivă pentru rezolvarea numărului problemei Towers of Hanoi, // o variabilă care stochează numărul de discuri care trebuie mutate basic_rod, // o variabilă care stochează numărul tijei pe care vor fi inițial discurile localizat help_rod , // o variabilă care stochează numărul tijei, care este folosită ca auxiliar final_rod); // variabila care stocheaza numarul tijei la care trebuie mutate discurile system("pause"); întoarce 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // condiție pentru terminarea apelurilor recursive ( cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

  // cod Cod::Blocuri

  // Cod Dev-C++

  // hanoi_tower.cpp: Definește punctul de intrare pentru aplicația de consolă. // Un program care rezolvă recursiv problema Turnului din Hanoi #include #include folosind namespace std; void tower(int, int, int, int); // declararea unui prototip al unei funcții recursive int count = 1; // variabilă globală pentru numărarea numărului de pași int main() ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>număr; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> tijă_de bază; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> final_rod; int help_rod; // bloc pentru determinarea numărului tijei auxiliare, analizând numerele tijei inițiale și finale if (basic_rod != 2 && final_rod != 2) help_rod = 2; else if (basic_rod != 1 && final_rod != 1) help_rod = 1; else if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(// lansează o funcție recursivă pentru rezolvarea numărului problemei Towers of Hanoi, // o variabilă care stochează numărul de discuri care trebuie mutate basic_rod, // o variabilă care stochează numărul tijei pe care vor fi inițial discurile localizat help_rod , // o variabilă care stochează numărul tijei, care este folosită ca auxiliar final_rod); // variabila care memoreaza numarul tijei la care trebuie mutate discurile returneaza 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // condiție pentru terminarea apelurilor recursive ( cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

  Figura 5 prezintă un exemplu de program recursiv Turnul din Hanoi. Mai întâi, am introdus numărul de discuri egal cu trei, apoi am intrat în tija de bază (întâi) și am desemnat tija finală (a treia). În mod automat, a doua tijă a devenit auxiliară. Programul a produs un rezultat care coincide complet cu soluția animată a acestei probleme.

  Introduceți numărul de discuri: 3 Introduceți numărul tijei de bază: 1 Introduceți numărul tijei finale: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3

  Figura 5 - Recursiune în C++

  Din figură se poate observa că mai întâi discul se mișcă de la tija unu la tija trei, apoi de la tija unu la tija doi, de la tija trei la tijadoi, etc. Adică, programul afișează doar secvența mișcărilor discului și numărul minim de pași în care vor fi mutate toate discurile.

  Toate aceste probleme ar putea fi rezolvate iterativ. Apare întrebarea: „Ce este mai bine de rezolvat, iterativ sau recursiv?” Răspund: „Dezavantajul recursiunii este că consumă mult mai multe resurse computerizate decât iterația. Acest lucru are ca rezultat o sarcină mare atât pe RAM, cât și pe procesor. Dacă este evident că o anumită problemă poate fi rezolvată într-un mod iterativ, atunci ar trebui folosită diferit, folosind recursiunea!” În funcție de problema rezolvată, complexitatea scrierii programelor se modifică atunci când se folosește una sau alta metodă de rezolvare. Dar, mai des, o problemă rezolvată folosind o metodă recursivă din punct de vedere al lizibilității codului este mult mai clară și mai scurtă.

  Recursiunile sunt evenimente interesante în sine, dar în programare sunt deosebit de importante în cazuri specifice. Când le întâlnesc pentru prima dată, un număr destul de semnificativ de oameni au probleme în a le înțelege. Acest lucru se datorează câmpului uriaș de potențiale aplicații ale termenului în sine, în funcție de contextul în care este folosită „recursiune”. Dar putem spera că acest articol va ajuta la evitarea oricărei posibile neînțelegeri sau neînțelegeri.

  Oricum, ce este „recursiune”?

  Cuvântul „recursiune” are o întreagă gamă de sensuri, care depind de domeniul în care este aplicat. Denumirea universală este următoarea: recursiunile sunt definiții, imagini, descrieri ale obiectelor sau proceselor din obiectele în sine. Sunt posibile numai în cazurile în care obiectul face parte din el însuși. Matematica, fizica, programarea și o serie de alte discipline științifice definesc recursiunea în felul lor. A găsit aplicație practică în operarea sistemelor informaționale și experimente fizice.

  Ce se înțelege prin recursivitate în programare?

  

  Situațiile recursive, sau recursiunea în programare, sunt momente în care o procedură de program sau o funcție se autoapelează. Oricât de ciudat ar suna pentru cei care au început să învețe programarea, nu este nimic ciudat aici. Trebuie amintit că recursiunile nu sunt dificile și, în unele cazuri, înlocuiesc buclele. Dacă computerul este instruit corect să apeleze o procedură sau o funcție, va începe pur și simplu să o execute.

  Recursiunea poate fi finită sau infinită. Pentru ca primul să înceteze să se autoprovoce, trebuie să conțină și condiții de reziliere. Aceasta poate fi scăderea valorii unei variabile și, atunci când se atinge o anumită valoare, oprirea apelului și terminarea programului / trecerea la codul ulterior, în funcție de nevoile pentru atingerea anumitor obiective. Prin recursivitate infinită înțelegem că va fi apelat atâta timp cât computerul sau programul în care rulează rulează.

  De asemenea, este posibilă organizarea recursiunii complexe folosind două funcții. Să presupunem că există A și B. Funcția A are un apel la B în codul său, iar B, la rândul său, indică computerului necesitatea de a executa A. Recursiunile complexe sunt o cale de ieșire dintr-o serie de situații logice complexe pentru computer logică.

  Dacă cititorul acestor rânduri a studiat buclele de program, atunci probabil că a observat deja asemănările dintre ele și recursiunea. În general, ei pot îndeplini într-adevăr sarcini similare sau identice. Folosind recursiunea, este convenabil să simulați funcționarea unei bucle. Acest lucru este util mai ales acolo unde ciclurile în sine nu sunt foarte convenabile de utilizat. Schema de implementare a software-ului nu diferă mult între diferitele limbaje de programare de nivel înalt. Dar, totuși, recursiunea în Pascal și recursiunea în C sau în alt limbaj au propriile lor caracteristici. Poate fi implementat cu succes în limbaje de nivel scăzut, cum ar fi Assembly, dar acest lucru este mai problematic și necesită mult timp.

  Arbori recursivi

  

  Ce este „arborele” în programare? Aceasta este o mulțime finită constând din cel puțin un nod care:

  1. Are un nod special inițial, care se numește rădăcina întregului arbore.
  2. Nodurile rămase sunt într-un număr diferit de zero de subseturi disjunse în perechi și sunt, de asemenea, un arbore. Toate aceste forme de organizare sunt numite subarbori ai arborelui principal.

  Cu alte cuvinte: copacii conțin subarbori, care conțin mai mulți copaci, dar în număr mai mic decât arborele anterior. Aceasta continuă până când unul dintre noduri nu se mai poate mișca înainte, iar aceasta va marca sfârșitul recursiunii. Mai există o nuanță despre reprezentarea schematică: copacii obișnuiți cresc de jos în sus, dar în programare sunt desenați invers. Nodurile care nu au continuare sunt numite noduri frunză. Pentru ușurința desemnării și comoditate, se folosește terminologia genealogică (strămoși, copii).

  De ce este folosit în programare?

  

  Recursiunea în programare și-a găsit aplicația în rezolvarea unui număr de probleme complexe. Dacă este necesar să se efectueze un singur apel, atunci este mai ușor să folosești o buclă de integrare, dar cu două sau mai multe repetări, pentru a evita construirea unui lanț și a face execuția lor sub formă de arbore, se folosesc situații recursive. Pentru o clasă largă de sarcini, organizarea procesului de calcul în acest mod este cea mai optimă din punct de vedere al consumului de resurse. Astfel, recursiunea în Pascal sau în orice alt limbaj de programare de nivel înalt este un apel către o funcție sau procedură până când sunt îndeplinite condițiile, indiferent de numărul de apeluri externe. Cu alte cuvinte, un program poate avea un singur apel la o subrutină, dar va avea loc până la un moment prestabilit. În unele moduri, acesta este un analog al unui ciclu cu propriile sale specificități de utilizare.

  Diferențele dintre recursive în diferite limbaje de programare

  În ciuda schemei generale de implementare și a aplicării specifice în fiecare caz individual, recursiunea în programare are propriile sale caracteristici. Acest lucru poate duce la dificultăți la căutarea materialului necesar. Dar trebuie să vă amintiți întotdeauna: dacă un limbaj de programare apelează funcții sau proceduri, atunci apelarea recursiunii este fezabilă. Dar cele mai semnificative diferențe apar atunci când se utilizează limbaje de programare scăzute și înalte. Acest lucru este valabil mai ales pentru capabilitățile de implementare a software-ului. Execuția depinde în cele din urmă de ce sarcină este pusă, iar recursiunea este scrisă în conformitate cu aceasta. Funcțiile și procedurile utilizate sunt diferite, dar scopul lor este întotdeauna același - să-i forțeze să se numească.

  Recursiunea este ușoară. Cât de ușor este să-ți amintești conținutul unui articol?

  

  Pentru începători, poate fi dificil de înțeles la început, așa că aveți nevoie de exemple de recursivitate, sau cel puțin unul. Prin urmare, ar trebui să dăm un mic exemplu din viața de zi cu zi care ne va ajuta să înțelegem însăși esența acestui mecanism pentru atingerea obiectivelor în programare. Luați două sau mai multe oglinzi, plasați-le astfel încât toate celelalte să fie afișate într-una singură. Puteți vedea că oglinzile se reflectă de mai multe ori, creând un efect infinit. Recursiunile sunt, la figurat vorbind, reflecții (vor fi multe). După cum puteți vedea, nu este greu de înțeles, doar dacă aveți dorința. Și studiind materialele de programare, puteți înțelege mai departe că recursiunea este, de asemenea, o sarcină foarte ușor de finalizat.