să revenim la funcții și să le studiem mai în profunzime.

primul nostru subiect va fi recursivitatea.dacă nu sunteți nou în programare, atunci este probabil familiar și puteți sări peste acest capitol.recursivitatea este un model de programare care este util în situațiile în care o sarcină poate fi împărțită în mod natural în mai multe sarcini de același fel, dar mai simplă. Sau când o sarcină poate fi simplificată într-o acțiune ușoară, plus o variantă mai simplă a aceleiași sarcini. Sau, după cum vom vedea în curând, să ne ocupăm de anumite structuri de date.,când o funcție rezolvă o sarcină, în acest proces poate apela multe alte funcții. Un caz parțial al acestui lucru este atunci când o funcție se numește. Asta se numește recursivitate.

Două moduri de gândire

Pentru ceva simplu pentru a începe cu – să se scrie o funcție pow(x, n) care ridică x la o putere naturală de n. Cu alte cuvinte, se multiplică x de la sine n ori.

pow(2, 2) = 4pow(2, 3) = 8pow(2, 4) = 16

există două moduri de a-l implementa.,vă rugăm să rețineți modul în care varianta recursivă este fundamental diferită.

pow(x, n) este numit, executarea se împarte în două ramuri:

 if n==1 = x /pow(x, n) = \ else = x * pow(x, n - 1)

1. Dacă n == 1, atunci totul este banal. Se numește baza recursivității, deoarece produce imediat rezultatul evident: pow(x, 1) este egal cu x.
2. în caz Contrar, putem reprezenta pow(x, n) ca x * pow(x, n - 1)., În matematică, s-ar scrie xn = x * xn-1. Aceasta se numește un pas recursiv: vom transforma sarcina intr-o simplă acțiune (înmulțirea prin x) și un simplu apel de aceeași sarcină (pow cu mici n). Următorii pași simplifica și mai mult și mai departe până când n ajunge 1.

de asemenea, putem spune că pow recursiv se numește până n == 1.,

De exemplu, pentru a calcula pow(2, 4) recursive varianta acești pași:

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

Deci, recursivitate reduce un apel de funcție pentru o mai simplă, și apoi – la mod mult mai simplu, și așa mai departe, până când rezultatul devine evident.,

numărul maxim de apeluri imbricate (inclusiv primul) se numește adâncime de recursivitate. În cazul nostru, va fi exact n.

adâncimea maximă de recursivitate este limitată de motorul JavaScript. Ne putem baza pe faptul că este 10000, unele motoare permit mai mult, dar 100000 este probabil în afara limitei pentru majoritatea acestora. Există Optimizări automate care ajută la atenuarea acestui lucru („coada solicită optimizări”), dar acestea nu sunt încă acceptate peste tot și funcționează doar în cazuri simple.aceasta limitează aplicarea recursivității, dar rămâne foarte largă., Există multe sarcini în care modul recursiv de gândire oferă un cod mai simplu, mai ușor de întreținut.

contextul de execuție și stiva

acum să examinăm cum funcționează apelurile recursive. Pentru asta ne vom uita sub capota funcțiilor.

informațiile despre procesul de execuție a unei funcții de rulare sunt stocate în contextul său de execuție.,contextul de execuție este o structură internă de date care conține detalii despre executarea unei funcții: unde este acum fluxul de control, variabilele curente, valoarea this (nu o folosim aici) și câteva alte detalii interne.un apel de funcție are exact un context de execuție asociat cu acesta.

când o funcție face un apel imbricat, se întâmplă următoarele:

• funcția curentă este întreruptă.
• contextul de execuție asociat cu acesta este amintit într-o structură specială de date numită execution context stack.,
• apelul imbricat se execută.
• după ce se termină, vechiul context de execuție este preluat din stivă, iar funcția exterioară este reluată de unde s-a oprit.

să vedem ce se întâmplă în timpul apelului pow(2, 3).

pow(2, 3)

la începutul apel pow(2, 3) contextul de executie va stoca variabile: x = 2, n = 3, fluxul de execuție este la linie 1 din funcție.,

o putem schița ca:

• Context: { x: 2, n: 3, la linia 1 } pow(2, 3)

atunci funcția începe să se execute., Starea n == 1 este falsy, astfel încât fluxul continuă în cea de-a doua ramură a if:

function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); }}alert( pow(2, 3) );

variabilele sunt aceleași, dar linia se schimbă, deci, contextul este acum:

• Context: { x: 2, nr: 3, la linia 5 } pow(2, 3)

Pentru a calcula x * pow(x, n - 1), avem nevoie pentru a face o subcall de pow cu noi argumente pow(2, 2).,

pow (2, 2)

pentru a face un apel imbricat, JavaScript își amintește contextul de execuție curent din stiva de context de execuție.

aici numim aceeași funcție pow, dar absolut nu contează. Procesul este același pentru toate funcțiile:

1. contextul curent este „amintit” în partea de sus a stivei.
2. noul context este creat pentru subcall.
3. când subcallul este terminat-contextul anterior este scos din stivă, iar execuția acestuia continuă.,

Iată contextul stivă atunci când am intrat în subcall pow(2, 2):

• Context: { x: 2, nr: 2, la linia 1 } pow(2, 2)
• Context: { x: 2, nr: 3, la linia 5 } pow(2, 3)

noul actualul context de executie este pe partea de sus (si bold), iar anterior amintit contextele de mai jos.

când terminăm subcall – este ușor să reluăm contextul anterior, deoarece păstrează atât variabilele, cât și locul exact al codului în care s-a oprit.,

pow(2, 1)

procesul se repetă: un nou subcall se face la linia 5, acum cu argumente x=2, n=1.,

Un nou context de execuție este creat, cel anterior este împins pe partea de sus a stivei:

• Context: { x: 2, n: 1, la linia 1 } pow(2, 1)
• Context: { x: 2, nr: 2, la linia 5 } pow(2, 2)
• Context: { x: 2, n: 3, la linia 5 } pow(2, 3)

sunt 2 vechi contexte acum și 1 execută în prezent pentru pow(2, 1).,

ieșire

în Timpul executării pow(2, 1), spre deosebire de înainte, condiția n == 1 este sinceră, așa că prima ramură a if funcționează:

function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); }}

nu mai Există apeluri imbricate, astfel încât funcția finisaje, revenind 2.

pe măsură ce funcția se termină, contextul său de execuție nu mai este necesar, deci este eliminat din memorie., Cea anterioară este restabilită pe partea de sus a stivei:

• Context: { x: 2, nr: 2, la linia 5 } pow(2, 2)
• Context: { x: 2, nr: 3, la linia 5 } pow(2, 3)

Apoi context anterioară este restabilită:

• Context: { x: 2, nr: 3, la linia 5 } pow(2, 3)

Când se termină, vom avea un rezultat pow(2, 3) = 8.

adâncimea de recursivitate în acest caz a fost: 3.

după cum putem vedea din Ilustrațiile de mai sus, adâncimea de recursivitate este egală cu numărul maxim de context din stivă.

rețineți cerințele de memorie. Contextele iau memorie., În cazul nostru, ridicarea la puterea n de fapt necesită memorie pentru n contexte, pentru toate valorile mai mici de n.

O buclă pe bază de algoritm este mai multă memorie de economisire:

function pow(x, n) { let result = 1; for (let i = 0; i < n; i++) { result *= x; } return result;}

iterativ pow foloseste un singur context în schimbare i și result în acest proces. Cerințele sale de memorie sunt mici, fixe și nu depind de n.,orice recursiune poate fi rescrisă ca o buclă. Varianta de buclă poate fi de obicei mai eficientă.

…dar uneori rescrierea este non-trivială, mai ales atunci când funcția utilizează diferite subcale recursive în funcție de condiții și îmbină rezultatele lor sau când ramificarea este mai complicată. Iar optimizarea poate fi inutilă și total nu merită eforturile.

recursivitatea poate da un cod mai scurt, mai ușor de înțeles și de susținut. Optimizările nu sunt necesare în orice loc, mai ales avem nevoie de un cod bun, de aceea este folosit.,

traversări Recursive

o altă aplicație excelentă a recursivității este o traversare recursivă.

Imaginați-vă, avem o companie. Structura personalului poate fi prezentată ca un obiect:

cu alte cuvinte, o companie are departamente.

• un departament poate avea o serie de personal. De exemplu, sales departamentul are 2 angajați: John și Alice.

• Sau un departament poate împărți în subdepartamente, ca development are două ramuri: sites și internals. Fiecare dintre ei are propriul personal.,de asemenea, este posibil ca atunci când un Subdepartament crește, acesta se împarte în subsubdepartamente (sau Echipe).

  De exemplu, sites departamentul în viitor, poate fi împărțit în echipe pentru siteA și siteB. Și ei, potențial, se pot împărți și mai mult. Asta nu e pe imagine, doar ceva să aibă în minte.acum, să spunem că vrem o funcție pentru a obține suma tuturor salariilor. Cum putem face asta?o abordare iterativă nu este ușoară, deoarece structura nu este simplă., Prima idee ar fi sa faci un for bucla peste company cu imbricate subloop peste 1 nivel de departamente. Dar avem nevoie de mai multe imbricate subloops pentru a itera peste personalului în al 2-lea nivel de departamente, cum ar fi sites… Și apoi un alt subloop în interiorul celor pentru nivelul 3 departamente care ar putea apărea în viitor? Dacă punem 3-4 subloops imbricate în cod pentru a traversa un singur obiect, devine destul de urât.

  Să încercăm recursivitate.,după cum putem vedea, atunci când funcția noastră devine un departament pentru a însuma, există două cazuri posibile:

  1. fie este un departament „simplu”, cu o serie de oameni – atunci putem însuma salariile într-o buclă simplă.
  2. Sau e un obiect cu N subdepartamente – atunci putem face N apeluri recursive pentru a obține suma pentru fiecare dintre subdeps și de a combina rezultatele.

  primul caz este baza recursivității, cazul trivial, când obținem o matrice.

  al doilea caz când obținem un obiect este pasul recursiv., O sarcină complexă este împărțită în subtascuri pentru departamente mai mici. La rândul lor, se pot împărți din nou, dar mai devreme sau mai târziu, împărțirea se va termina la (1).

  algoritmul este probabil chiar mai ușor de citit din Cod:

  codul este scurt și ușor de înțeles (sperăm?). Aceasta este puterea recursivității. De asemenea, funcționează pentru orice nivel de cuibărit Subdepartament.,

  Aici e diagrama de apeluri:

  

  Rețineți că codul utilizează caracteristici inteligente care ne-am acoperit înainte:

  • Metoda arr.reduce explicate în capitolul Serie de metode pentru a obține suma de matrice.
  • Bucla for(val of Object.values(obj)) pentru a itera peste obiect valori: Object.values returnează o matrice de ei.,

  structuri Recursive

  o structură de date recursivă (definită recursiv) este o structură care se reproduce în părți.

  tocmai am văzut-o în exemplul unei structuri a companiei de mai sus.

  un departament al companiei este:

  • fie o serie de oameni.
  • sau un obiect cu departamente.pentru dezvoltatorii web există exemple mult mai bine cunoscute: documente HTML și XML.

    în documentul HTML, o etichetă HTML poate conține o listă de:

    • piese de Text.
    • HTML-comentarii.,
    • alte HTML-tag-uri (care la rândul lor pot conține piese de text/comentarii sau alte tag-uri etc).

    aceasta este din nou o definiție recursivă.

    pentru o mai bună înțelegere, vom acoperi o structură recursivă numită „listă legată” care ar putea fi o alternativă mai bună pentru matrice în unele cazuri.

    listă legată

    Imaginați-vă, dorim să stocăm o listă ordonată de obiecte.

    alegerea naturală ar fi o matrice:

    let arr = ;

    …Dar e o problemă cu matrice., Operațiile” ștergere element „și” inserare element ” sunt costisitoare. De exemplu, arr.unshift(obj) operațiunea trebuie să se renumerotează toate elementele pentru a face loc pentru un nou obj, și dacă o matrice este mare, este nevoie de timp. La fel cu arr.shift().singurele modificări structurale care nu necesită Renumerotare în masă sunt cele care funcționează cu sfârșitul matricei: arr.push/pop. Deci, o matrice poate fi destul de lent pentru cozi mari, atunci când trebuie să lucrăm cu începutul.,în mod alternativ, dacă într-adevăr avem nevoie de inserare/ștergere rapidă, putem alege o altă structură de date numită listă legată.

    elementul listă legată este definit recursiv ca un obiect cu:

    • value.
    • next proprietate referire la următoarea listă de legat element sau null dacă ăsta e sfârșitul.,

    For instance:

    let list = { value: 1, next: { value: 2, next: { value: 3, next: { value: 4, next: null } } }};

    Graphical representation of the list:

    

    An alternative code for creation:

    let list = { value: 1 };list.next = { value: 2 };list.next.next = { value: 3 };list.next.next.next = { value: 4 };list.next.next.next.next = null;

    Here we can even more clearly see that there are multiple objects, each one has the value and next pointing to the neighbour., Variabila list este primul obiect din lanț, astfel încât urmând next indicii din acesta putem ajunge la orice element.

    lista poate fi ușor împărțită în mai multe părți și mai târziu s-au alăturat spate:

    let secondList = list.next.next;list.next.next = null;

    

    Să se alăture:

    list.next.next = secondList;

    Și cu siguranță putem introduce sau a elimina elemente din orice loc.,head of the list:

    

    To remove a value from the middle, change next of the previous one:

    list.next = list.next.next;

    

    We made list.next jump over 1 to value 2., Valoarea 1 este acum exclusă din lanț. Dacă nu este stocat în altă parte, acesta va fi eliminat automat din memorie.spre deosebire de matrice, nu există Renumerotare în masă, putem rearanja cu ușurință elementele.desigur, listele nu sunt întotdeauna mai bune decât matricele. În caz contrar, toată lumea ar folosi doar liste.principalul dezavantaj este că nu putem accesa cu ușurință un element după numărul său. Într-o matrice care este ușor: arr este o referință directă., Dar în listă trebuie să înceapă de la primul articol și du-te next N ori pentru a obține cel mai Inalt element.

    …dar nu avem întotdeauna nevoie de astfel de operațiuni. De exemplu, atunci când avem nevoie de o coadă sau chiar un deque – structura ordonată care trebuie să permită adăugarea/eliminarea foarte rapidă a elementelor din ambele capete, dar accesul la mijlocul acesteia nu este necesar.

    Liste pot fi îmbunătățite:

    • putem adăuga proprietate prev în plus față de next de referință elementul anterior, să se mute înapoi cu ușurință.,
    • putem adăuga, de asemenea, o variabilă numită tail referindu-se la ultimul element al listei (și actualizați-l la adăugarea / eliminarea elementelor de la sfârșit).
    • … structura datelor poate varia în funcție de nevoile noastre.

    rezumat

    Termeni:

    • recursivitatea este un termen de programare care înseamnă apelarea unei funcții de la sine. Funcțiile Recursive pot fi utilizate pentru a rezolva sarcini în moduri elegante.

      când o funcție se apelează, aceasta se numește un pas de recursivitate., Baza recursivității este argumentele funcției care fac sarcina atât de simplă încât funcția nu efectuează apeluri suplimentare.

    • o structură de date definită recursiv este o structură de date care poate fi definită folosind ea însăși.

      de exemplu, lista legată poate fi definită ca o structură de date constând dintr-un obiect care face referire la o listă (sau nul).

      list = { value, next -> list }

      Copaci, ca elemente HTML copac sau departamentul copac de la acest capitol sunt, de asemenea, în mod natural recursivă: ei de ramură și fiecare ramură poate avea și alte ramuri.,

      funcțiile Recursive pot fi folosite pentru a le parcurge așa cum am văzut în exemplul sumSalary.orice funcție recursivă poate fi rescrisă într-una iterativă. Și asta este uneori necesar pentru a optimiza lucrurile. Dar pentru multe sarcini, o soluție recursivă este suficient de rapidă și mai ușor de scris și de susținut.