Recursiunea este un concept fundamental în informatică și matematică care permite funcțiilor să se numească, permițând rezolvarea unor probleme complexe prin pași iterativi. O reprezentare vizuală folosită în mod obișnuit pentru a înțelege și analiza execuția funcțiilor recursive este un arbore recursiv. În acest articol, vom explora teoria din spatele arborilor recursivi, structura lor și semnificația lor în înțelegerea algoritmilor recursivi.

Ce este un arbore recursiv?

Un arbore recursiv este o reprezentare grafică care ilustrează fluxul de execuție al unei funcții recursive. Oferă o defalcare vizuală a apelurilor recursive, prezentând progresia algoritmului pe măsură ce acesta se ramifică și ajunge în cele din urmă la un caz de bază. Structura arborescentă ajută la analiza complexității timpului și la înțelegerea procesului recursiv implicat.

Structura arborelui

Fiecare nod dintr-un arbore recursiv reprezintă un anumit apel recursiv. Apelul inițial este reprezentat în partea de sus, iar apelurile ulterioare se ramifică sub el. Arborele crește în jos, formând o structură ierarhică. Factorul de ramificare al fiecărui nod depinde de numărul de apeluri recursive efectuate în cadrul funcției. În plus, adâncimea arborelui corespunde numărului de apeluri recursive înainte de a ajunge la cazul de bază.

Caz de baza

Cazul de bază servește ca condiție de terminare pentru o funcție recursivă. Acesta definește punctul în care recursiunea se oprește și funcția începe să returneze valori. Într-un arbore recursiv, nodurile care reprezintă cazul de bază sunt de obicei descrise ca noduri frunză, deoarece nu duc la apeluri recursive ulterioare.

css bold

Apeluri recursive

Nodurile copil dintr-un arbore recursiv reprezintă apelurile recursive efectuate în cadrul funcției. Fiecare nod copil corespunde unui apel recursiv separat, rezultând în crearea de noi subprobleme. Valorile sau parametrii trecuți acestor apeluri recursive pot diferi, ceea ce duce la variații ale caracteristicilor subproblemelor.

Fluxul de execuție:

Parcurgerea unui arbore recursiv oferă perspective asupra fluxului de execuție al unei funcții recursive. Pornind de la apelul inițial la nodul rădăcină, urmărim ramurile pentru a ajunge la apelurile ulterioare până când întâlnim cazul de bază. Pe măsură ce cazurile de bază sunt atinse, apelurile recursive încep să revină, iar nodurile lor respective din arbore sunt marcate cu valorile returnate. Traversarea continuă până când întregul arbore a fost parcurs.

Analiza complexității timpului

Arborii recursivi ajută la analiza complexității în timp a algoritmilor recursivi. Examinând structura arborelui, putem determina numărul de apeluri recursive efectuate și munca depusă la fiecare nivel. Această analiză ajută la înțelegerea eficienței generale a algoritmului și la identificarea oricăror potențiale ineficiențe sau oportunități de optimizare.

Introducere

• Gândiți-vă la un program care determină factorialul unui număr. Această funcție ia un număr N ca intrare și returnează factorialul lui N ca rezultat. Pseudo-codul acestei funcții se va asemăna,

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• Recursiunea este exemplificată de funcția care a fost menționată anterior. Invocăm o funcție pentru a determina factorialul unui număr. Apoi, având în vedere o valoare mai mică a aceluiași număr, această funcție se autoinvocă. Aceasta continuă până când ajungem la cazul de bază, în care nu mai există apeluri de funcție.
• Recursiunea este o tehnică pentru gestionarea problemelor complicate atunci când rezultatul depinde de rezultatele unor cazuri mai mici ale aceleiași probleme.
• Dacă ne gândim la funcții, se spune că o funcție este recursivă dacă continuă să se numească până când ajunge la cazul de bază.
• Orice funcție recursivă are două componente principale: cazul de bază și pasul recursiv. Nu mai mergem la faza recursivă odată ce ajungem la cazul de bază. Pentru a preveni recursiunea fără sfârșit, cazurile de bază trebuie definite corespunzător și sunt cruciale. Definiția recursiunii infinite este o recursivitate care nu ajunge niciodată la cazul de bază. Dacă un program nu ajunge niciodată la cazul de bază, depășirea stivei va continua să aibă loc.

Tipuri de recursivitate

În general, există două forme diferite de recursivitate:

• Recursiune liniară
• Recursiune arborelui
• Recursiune liniară

Recursiune liniară

• Se spune că o funcție care se numește o singură dată de fiecare dată când se execută este recursivă liniar. O ilustrare frumoasă a recursiunii liniare este funcția factorială. Numele „recursiune liniară” se referă la faptul că o funcție recursivă liniar necesită o perioadă liniară de timp pentru a fi executată.
• Aruncă o privire la pseudo-codul de mai jos:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Dacă ne uităm la funcția doSomething(n), aceasta acceptă un parametru numit n și face câteva calcule înainte de a apela din nou aceeași procedură, dar cu valori mai mici.
• Când metoda doSomething() este apelată cu valoarea argumentului n, să presupunem că T(n) reprezintă timpul total necesar pentru a finaliza calculul. Pentru aceasta, putem formula și o relație de recurență, T(n) = T(n-1) + K. K servește aici ca constantă. Constanta K este inclusă deoarece este nevoie de timp pentru ca funcția să aloce sau să dezaoce memorie unei variabile sau să efectueze o operație matematică. Folosim K pentru a defini timpul, deoarece este atât de mic și nesemnificativ.
• Complexitatea de timp a acestui program recursiv poate fi calculată simplu, deoarece, în cel mai rău scenariu, metoda doSomething() se numește de n ori. Din punct de vedere formal, complexitatea temporală a funcției este O(N).

Recursiune arborelui

• Când efectuați un apel recursiv în cazul dumneavoastră recursiv de mai multe ori, acesta este denumit recursivitate arborescentă. O ilustrare eficientă a recursiunii arborelui este secvența Fibonacci. Funcțiile recursive arborescente operează în timp exponențial; nu sunt liniare în complexitatea lor temporală.
• Aruncă o privire la pseudo-codul de mai jos,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• Singura diferență dintre acest cod și cel anterior este că acesta efectuează încă un apel către aceeași funcție cu o valoare mai mică de n.
• Să punem T(n) = T(n-1) + T(n-2) + k ca relație de recurență pentru această funcție. K servește încă o dată ca constantă.
• Când se efectuează mai multe apeluri la aceeași funcție cu valori mai mici, acest tip de recursivitate este cunoscut sub numele de recursivitate arborescentă. Aspectul intrigant este acum: cât de consumatoare este această funcție?
• Luați o ghicire bazată pe arborele recursiv de mai jos pentru aceeași funcție.
  
• S-ar putea să vi se pară că este dificil să estimați complexitatea timpului uitându-vă direct la o funcție recursivă, în special atunci când este o recursivitate arborescentă. Metoda arborelui recursiv este una dintre mai multe tehnici de calculare a complexității temporale a unor astfel de funcții. Să-l examinăm mai detaliat.

Ce este metoda arborelui recursiv?

• Relațiile de recurență precum T(N) = T(N/2) + N sau cele două pe care le-am acoperit mai devreme în secțiunea tipuri de recursivitate sunt rezolvate folosind abordarea arborelui recursiv. Aceste relații de recurență folosesc adesea o strategie de împărțire și cucerire pentru a aborda problemele.
• Este nevoie de timp pentru a integra răspunsurile la subproblemele mai mici care sunt create atunci când o problemă mai mare este împărțită în subprobleme mai mici.
• Relația de recurență, de exemplu, este T(N) = 2 * T(N/2) + O(N) pentru sortarea Merge. Timpul necesar pentru a combina răspunsurile la două subprobleme cu o dimensiune combinată de T(N/2) este O(N), ceea ce este adevărat și la nivelul implementării.
• De exemplu, deoarece relația de recurență pentru căutarea binară este T(N) = T(N/2) + 1, știm că fiecare iterație a căutării binare are ca rezultat un spațiu de căutare care este tăiat la jumătate. Odată ce rezultatul este determinat, ieșim din funcție. Relația de recurență are +1 adăugat deoarece aceasta este o operație în timp constant.
• Relația de recurență T(n) = 2T(n/2) + Kn este una de luat în considerare. Kn indică timpul necesar pentru a combina răspunsurile la subprobleme n/2-dimensionale.
• Să descriem arborele recursiv pentru relația de recurență menționată mai sus.

Putem trage câteva concluzii din studierea arborelui recursiv de mai sus, inclusiv

1. Amploarea problemei la fiecare nivel este tot ceea ce contează pentru a determina valoarea unui nod. Mărimea problemei este n la nivelul 0, n/2 la nivelul 1, n/2 la nivelul 2 și așa mai departe.

2. În general, definim înălțimea arborelui ca fiind egală cu log (n), unde n este dimensiunea problemei, iar înălțimea acestui arbore recursiv este egală cu numărul de niveluri din arbore. Acest lucru este adevărat deoarece, așa cum tocmai am stabilit, strategia de împărțire și cucerire este utilizată de relațiile de recurență pentru a rezolva probleme, iar trecerea de la dimensiunea problemei n la dimensiunea problemei 1 necesită pur și simplu luarea de pași log (n).

• Luați în considerare valoarea lui N = 16, de exemplu. Dacă ni se permite să împărțim N la 2 la fiecare pas, câți pași sunt necesari pentru a obține N = 1? Având în vedere că împărțim la doi la fiecare pas, răspunsul corect este 4, care este valoarea log(16) baza 2.

log(16) baza 2

log(2^4) baza 2

șirul java este gol

4 * log(2) baza 2, deoarece log(a) baza a = 1

deci, 4 * log(2) baza 2 = 4

3. La fiecare nivel, al doilea termen din recurență este privit ca rădăcină.

Deși cuvântul „copac” apare în numele acestei strategii, nu trebuie să fii un expert în copaci pentru a-l înțelege.

Cum să utilizați un arbore recursiv pentru a rezolva relațiile de recurență?

Costul problemei secundare în tehnica arborelui recursiv este timpul necesar pentru rezolvarea problemei secundare. Prin urmare, dacă observați expresia „cost” legată de arborele recursiv, se referă pur și simplu la timpul necesar pentru a rezolva o anumită problemă secundară.

Să înțelegem toți acești pași cu câteva exemple.

Exemplu

Luați în considerare relația de recurență,

T(n) = 2T(n/2) + K

Soluţie

Relația de recurență dată arată următoarele proprietăți,

O problemă cu dimensiunea n este împărțită în două sub-probleme fiecare cu dimensiunea n/2. Costul combinării soluțiilor la aceste subprobleme este K.

Fiecare dimensiune de problemă a lui n/2 este împărțită în două sub-probleme fiecare de dimensiunea n/4 și așa mai departe.

La ultimul nivel, dimensiunea sub-problemei va fi redusă la 1. Cu alte cuvinte, am lovit în sfârșit cazul de bază.

Să urmăm pașii pentru a rezolva această relație de recurență,

Pasul 1: Desenați arborele recursiv

testarea software-ului și tipurile

Pasul 2: Calculați înălțimea copacului

Deoarece știm că atunci când împărțim continuu un număr la 2, vine un moment în care acest număr se reduce la 1. La fel ca și cu dimensiunea problemei N, să presupunem că după K împărțiri cu 2, N devine egal cu 1, ceea ce implică, ( n / 2^k) = 1

Aici n / 2^k este dimensiunea problemei la ultimul nivel și este întotdeauna egală cu 1.

Acum putem calcula cu ușurință valoarea lui k din expresia de mai sus, luând log() de ambele părți. Mai jos este o derivație mai clară,

dependență parțială

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) baza 2

Deci, înălțimea copacului este log (n) baza 2.

Pasul 3: Calculați costul la fiecare nivel

• Cost la Nivel-0 = K, două subprobleme sunt îmbinate.
• Cost la Nivel-1 = K + K = 2*K, două sub-probleme sunt îmbinate de două ori.
• Cost la Nivel-2 = K + K + K + K = 4*K, două subprobleme sunt îmbinate de patru ori. și așa mai departe....

Pasul 4: Calculați numărul de noduri la fiecare nivel

Să determinăm mai întâi numărul de noduri din ultimul nivel. Din arborele recursiv putem deduce acest lucru

• Nivelul-0 are 1 (2^0) nod
• Nivelul-1 are 2 (2^1) noduri
• Nivelul-2 are 4 (2^2) noduri
• Nivelul-3 are 8 (2^3) noduri

Deci nivelul log(n) ar trebui să aibă 2^(log(n)) noduri, adică n noduri.

Pasul 5: Însumați costul tuturor nivelurilor

• Costul total poate fi scris ca:
• Cost total = Costul tuturor nivelurilor, cu excepția ultimului nivel + Costul ultimului nivel
• Cost total = Cost pentru nivelul-0 + Cost pentru nivelul-1 + Cost pentru nivelul-2 +.... + Cost pentru nivel-log(n) + Cost pentru ultimul nivel

Costul ultimului nivel este calculat separat, deoarece este cazul de bază și nu se face o fuziune la ultimul nivel, astfel încât costul rezolvării unei singure probleme la acest nivel este o valoare constantă. Să o luăm ca O (1).

Să punem valorile în formule,

• T(n) = K + 2*K + 4*K + .... + log(n)` ori + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) ori)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) ori + O(n)

Dacă vă uitați îndeaproape la expresia de mai sus, aceasta formează o progresie geometrică (a, ar, ar^2, ar^3 ...... timp infinit). Suma lui GP este dată de S(N) = a / (r - 1). Aici este primul termen și r este raportul comun.