Definiții de bază
Recurgerea este definirea unui obiect prin același obiect.
În acest exemplu, partea recursivă a definiției este "<Список> „“ <Число> “.
OBSERVAȚIE 1. O definiție recursivă, fiind finită, definește un set infinit de obiecte.
De asemenea, menționăm acest lucru <Список> poate fi definit și într-un alt mod:
Definiția (1) este numită stânga recursivă. și (2) are dreptate recursivă.
REMARK 2. O parte nerecursivă trebuie să fie prezentă în definiția recursivă.
O definiție recursivă poate fi indirectă.
una dintre ramurile unei definiții recursive se referă la un obiect a cărui definiție, la rândul său, determină obiectul sursă de către una dintre ramuri.
În acest exemplu, există o definiție recursivă atât directă, cât și indirectă.
În programare, sub recursiune se înțelege:
- apel de la o subrutină în sine (recursiune directă)
- apelează din subprogram o altă subrutină care cheamă originalul (recursiune indirectă)
Exemple simple de utilizare a recursivității
Când apelați această procedură, va apărea o buclă recursivă. deoarece apelul recursiv se face necondiționat.
Concluzie. Pentru bucla recursive nu a avut loc, apelul recursiv trebuie să aibă loc nu este absolut, dar în unele condiții care se schimbă de fiecare dată, iar unele apel recursiv devine fals (așa-numita stare continuarea recursivitatii).
Să corectăm procedura noastră conform concluziilor făcute:
Când se apela p (0), vor fi afișate următoarele:
Din punct de vedere grafic, apelurile recursive pot fi reprezentate după cum urmează:
Procesul de apeluri succesive recursive ale unui subprogram din el însuși se numește descendență recursivă.
Procesul de revenire de la apelurile recursive se numește returnare recursivă.
În acest exemplu, numerele sunt generate pe o coborâre recursivă (adică, în ordinea directă).
Cu toate acestea, pentru a efectua acțiunile în ordine inversă, acestea trebuie să fie chemate într-o întoarcere recursivă.
Exemplul 2. retrage
Adâncimea maximă a apelurilor recursive se numește profunzimea recursivității.
Adâncimea curentă este denumită nivelul actual de recursiune.
Notă. Cu cât este mai mare adâncimea recurenței, cu atât este mai mare memoria deasupra capului.
Reprezentări grafice ale apelurilor recursive
Aveam deja o imagine grafică. Să ne amintim:
Luați în considerare în detaliu apelul la procedura p (0)
- O stivă de software este o zonă continuă de memorie alocată unui program, în special pentru a plasa subrutinele numite în el.
- De fiecare dată când subrutina este apelată pe stivă, este introdusă înregistrarea de activare (FOR) și, când este returnată, este scoasă din teanc.
astfel Pe stiva, sunt practic stocate toate valorile variabilei i.
Notă 1. Deoarece pentru fiecare apel recursiv ST este așezat pe teanc, atunci dacă adâncimea de recursiune este mare, stiva programului poate depăși. iar programul se va termina cu o eroare.
Acest lucru se va întâmpla cu cât mai repede, cu atât volumul total al parametrilor formali și al variabilelor locale este mai mare.
Prin urmare, următorul cod este foarte rău.
Nota 2. Overhead pentru plasarea pe un teanc de cheltuieli pentru împușcat peste stiva, precum și valorile atribuindu parametrii formali pe stivă sunt suficient de mari.
Prin urmare, dacă există o soluție simplă non-recursivă (iterativă), atunci ar trebui utilizată.
Observația 3. Orice recursiune poate fi înlocuită cu o iterație.
Exemple de utilizare a recurenței
Exemplul 1. Găsiți n! = n (n-1) (n-2). 2 * 1
Evident, definiți n! poate fi după cum urmează:
Apoi soluția are forma:
Totuși, rețineți că valoarea returnată nu este definită pentru n <0.
Cel puțin, putem înlocui condiția n = 0 cu n <= 0. но, в таком случае, мы получим неверный результат, т.к. факториал вообще не определен для отрицательных чисел.
Evident, este necesar să se verifice corectitudinea parametrului de intrare (Assert (n> = 0)) cu ajutorul instrucțiunii). Dar utilizarea lui pentru fiecare apel recursiv este costisitoare. Prin urmare, puteți "înfășura" o subrutină recursivă, de exemplu, astfel:
Adâncimea de recursiune a acestui algoritm este n.
Exemplul 2. Găsiți. Să dăm o definiție recursivă:
Adâncimea recursivității este:
- - în cel mai bun caz
- - în cel mai rău caz
Exemplul 3. Găsirea elementului minim într-o matrice. Putem defini acest element ca un minim (un element, minimul unui matrice fără acest element). și anume definiția recursivă este după cum urmează:
În concordanță cu aceasta avem o soluție:
Adâncimea recursiei este n - 1.
În mod clar, acest lucru nu este un rezultat foarte bun.
Puteți reduce în mod semnificativ adâncimea dacă căutați minimul între părțile aproximativ egale ale matricei. Ie Trebuie să împărțiți matricea la jumătate, să găsiți elementele minime în fiecare jumătate și să le comparați. O căutare în jumătate este efectuată în același mod, iar împărțirea este efectuată până când un element rămâne în subarray.
Încă puteți optimiza acest algoritm - dacă există două elemente în subarray, este suficient să returnați minimul.
Acum, cunoașterea numărului de elemente nu este suficientă: trebuie să știți, printre care elemente ale matricei de căutare. Prin urmare, vom trece limitele stânga (l) și dreapta (r) ale subarrays ca parametri.
Să dăm o nouă definiție recursivă:
Adâncimea recursului unui astfel de algoritm este aproximativ egală (prin numărul de diviziuni).
Exemplul 4. Ieșirea unei liste liniare pur și simplu conectate la ecran.
Să ne amintim cum arată lista:
soluţie:
Adâncimea recursivă este egală cu lungimea listei - 1
O recursiune se numește recursiune terminală. Dacă apelul recursiv este ultima în subrutină.
End recursion este cel mai ușor convertit într-un algoritm iterativ:
Dovada de completare a recursivității
Adăugăm întregul parametru n la procedura recursivă.
Dacă, pentru fiecare apel recursiv, parametrul n scade, primim apeluri
Și dacă recursiunea este terminată când n <= 0. то это служит доказательством завершимости рекурсии.
Într-adevăr, la fiecare nivel de recursiune următor, n devine mai mic.
Deoarece pentru n <= 0 рекурсивных вызовов нет, то число рекурсивных вызовов конечно.
Nu este întotdeauna posibil să spunem că recursiunea este completă.
Un exemplu.
Forme de subrutine recursive
1. Acțiunea se desfășoară pe o coborâre recursivă
2. Acțiunea se efectuează printr-o întoarcere recursivă
3. Acțiunea se desfășoară atât pe o coborâre recursivă cât și pe o întoarcere recursivă
4. Recurgerea în cascadă
Această recursiune se numește cascadă. deoarece fiecare apel de subrutină poate genera mai multe apeluri recursive (cascadă).
5. Recurgerea la distanță.
Un exemplu de recursiune la distanță este funcția Ackerman.
Exemple de utilizare proastă și bună a recurenței
Un exemplu de utilizare slabă a recursivității este numerele Fibonacci
Numerele Fibonacci sunt date de următoarea relație de recurență:
Le-am calculat deja cu cicluri. Poate că o soluție recursivă (rău!):
Asta se întâmplă când sunați Fib (7).
arbore recursiv de apeluri
După cum puteți vedea, aceleași numere sunt calculate de mai multe ori:
Algoritmul poate fi îmbunătățit utilizând o matrice încărcată inițial cu zerouri.
Primul calcul al fib (n) va umple elementul corespunzător, iar pentru toate cele ulterioare, pur și simplu se va referi la valoarea sa. Această tehnică se numește memoizare. și anume memorarea rezultatelor intermediare pentru a exclude recalcularea lor.
Evident, această metodă este extrem de ineficientă în comparație cu algoritmul iterativ atât din memorie, cât și din momentul operării. În special, adâncimea de recursiune la calcularea numărului n-al lui Fibonacci este n-1.
Metoda recursivă de calcul a numerelor Fibonacci, construită de algoritmul iterativ
Ne amintim un algoritm iterativ pentru găsirea numărului n-al lui Fibonacci:
Noi construim de la un algoritm recursiv, transmiterea de fiecare subprogram recursiv variabilele a, b, c, schimbarea la fiecare iterație buclă. De fapt, cu fiecare apel recursiv, vom face o înlocuire:
Algoritmul recursiv implementat prin această substituție va avea forma:
Recurgerea în acest exemplu este sfârșitul. Așa cum am menționat deja, este ușor de înlocuit cu iterație, în timp ce soluția iterativă anterioară este obținută. Compilatorii optimizați optim fac acest lucru automat.
Un exemplu de utilizare bună a recursivității este turnurile din Hanoi
Sarcina este următoarea:
Sunt date trei bare. Pe primele discuri de nișă de diferite raze, cu condiția ca nici un disc cu o rază mai mare să nu se găsească pe un disc cu o rază mai mică.
Este necesar să transferați discurile de la prima tija la cea de-a treia, folosind al doilea, cu condiția ca:
- O mișcare poate transfera un singur disc
- Discul mai mic ar trebui să fie mai mare
Ideea algoritmului este următoarea:
astfel avem o soluție simplă recursivă:
Sortare rapidă
Algoritmul de sortare rapidă (un fel de algoritm "divide și conquer") constă din două etape:
1. Selectarea unui element al matricei x și împărțirea matricei în două părți astfel încât în primul să existe toate elementele <= x, а в о второй —>= x
2. Aplicarea recursivă a algoritmului nostru la piesele obținute
Evident, algoritmul va funcționa mai repede, decât pe părți mai egale vom împărți matricea (ideal - de fiecare dată în jumătate).
Prin urmare, ar trebui să ne străduim să selectăm elementul x astfel încât să fie aproximativ jumătate din elementele matricei <= его, и, соответственно, вторая половина —>=. Pe de altă parte, alegerea lui x nu trebuie să ia mult timp și, cel puțin, să nu depindă de n-dimensiunea matricei).
Vom folosi cea mai simplă cale de a alege x - ca primul element care trebuie luat.
Următoarea animație prezintă un exemplu de aplicare a algoritmului de sortare rapidă pe o matrice
Luați în considerare etapa 1 în detaliu:
- Pentru a separa matricea în aceste părți, introducem 2 indici i și j.
- La început voi îndrepta spre primul element și mă mut în dreapta, iar j - la ultimul și mișcarea spre stânga.
Pasul 1.
Vom avansa înainte până când A [i] va deveni> = x.
Apoi, vom avansa j înapoi până când A [j] devine <= x .
Am ajuns la elementele A [i] și A [j]. care „nu sunt în locurile lor“ (amintiți-vă că vrem să împrăștie tot mai mică sau egală cu x la elementele din stânga, și mai mare sau egală - la dreapta)
Pasul 2.
Schimbați-le în funcție de locații și deplasați-i înainte un element, iar j - înapoi, de asemenea, un element.
Vom repeta acțiunile indicate până când devin> = j.
Ca rezultat, obținem matricea A. împărțită în două părți:
Codul programului
Estimarea asimptotică a complexității
Vom porni de la faptul că matricea este împărțită în 2 părți identice de fiecare dată. Aceasta este cea mai bună opțiune.
Adâncimea de recursiune în acest caz este log2 n.
astfel sub rezerva împărțirii în aproximativ jumătate. complexitatea asimptotică a întregului algoritm = Θ (n log n).
Teoretic, se demonstrează că, în medie, dacă nu împărțim exact jumătate, complexitatea asimptotică păstrează formula Θ (n log n).
Î: Care este cel mai grav scenariu? Cel mai rău este atunci când selectăm elementul minim (sau maxim) pentru x. Acest lucru se întâmplă (în situația noastră, pentru că am selectat primul element), dacă matricea este deja sortată.
În acest caz, ca rezultat al divizării în părți, cea mai mare parte va scădea cu 1, iar adâncimea de recursiune în procedura de sortare va fi egală cu.
Prin urmare, în cel mai rău caz, complexitatea asimptotică =.
Aprobarea. Pentru datele arbitrare nu există un algoritm cu complexitate asimptotică mai bun decât Θ (n log n) în medie.
Generarea tuturor permutărilor
Ideea de bază a algoritmului de generare a tuturor permutărilor este după cum urmează. Într-o serie de lungime n, care conține o permutare, vom schimba ultimul element din fiecare, iar apoi vom recursiv va face același lucru pentru lungimea de matrice n-1, și apoi să se întoarcă elementul rearanjat la locul vechi. Dacă lungimea șirului este atins n = 1, atunci swap-ul nu are nevoie de nimic, și ar trebui să dea afară întregul conținut al matrice-permutări pe ecran. O astfel de algoritm permite de a genera toate permutările, care rezultă din definiția recursiv verbală: ultima vizită fiecare element de conținut în această matrice, după care partea rămasă din matrice același algoritm este aplicat recursiv.
Este ușor de observat că adâncimea de recursiune este n-1, iar numărul apelurilor la procedura Perm este n.
Generarea tuturor subseturilor
Generarea tuturor subseturilor este un algoritm de enumerare. În algoritmii de căutare, toate opțiunile sunt sortate și se efectuează o anumită acțiune pentru variantele potrivite. În acest caz, toate subseturile sunt afișate pur și simplu.
Backtracking (backtracking)
Schema generală de căutare cu întoarcere
Trimiteți-le prietenilor: