de Kevin Turney

Recursivitatea nu este grea: un pas cu pas al acestei utile tehnici de programare

Recursivitatea nu este grea un pas cu pas al acestei

Voi spune asta chiar de pe bătaie. Știți evenimentele care se întâmplă la invocarea funcției? Nu? Atunci vom începe.

Invocarea funcției

Când apelăm o funcție, un context de execuție este plasat pe stiva de execuție. Haideți să mai descompunem asta.

În primul rând, ce este un teanc?

O stivă este o structură de date care funcționează pe baza „Last In, First Out”. Un articol este „împins” pe un teanc pentru a-l adăuga, iar un articol este „scos” din teanc pentru al elimina.

Folosirea unui stack este o metodă de ordonare a anumitor operații pentru executare.

Acum, înapoi la ce este un context de execuție? Un context de execuție se formează la invocarea unei funcții. Acest context se plasează pe o stivă de execuție, o ordine de operații. Elementul care este întotdeauna primul în această stivă este contextul global de execuție. Urmează contextele create de orice funcție.

Aceste contexte de execuție au proprietăți, un obiect de activare și o legare „aceasta”. Legarea „aceasta” este o referință la acest context de execuție. Obiectul de activare include: parametri trecuți, variabile declarate și declarații de funcții.

Deci, de fiecare dată când plasăm un nou context pe stivă, avem de obicei tot ce ne trebuie pentru a executa codul.

De ce spun obișnuit?

Cu recursivitate, așteptăm valori returnate provenind din alte contexte de execuție. Aceste alte contexte sunt mai sus în stivă. Când ultimul articol din stivă termină execuția, contextul respectiv generează o valoare returnată. Această valoare de returnare este transmisă ca valoare de returnare de la caz recursiv la următorul articol. Acest context de execuție este apoi eliminat din stivă.

Recursivitate

Deci, ce este recursivitatea?

O funcție recursivă este o funcție care se numește singură până când o „condiție de bază” este adevărată și executarea se oprește.

Deși este fals, vom continua să plasăm contexte de execuție deasupra stivei. Acest lucru se poate întâmpla până când vom avea un „overflow de stivă”. O depășire a stivei este atunci când rămânem fără memorie pentru a păstra elemente în stivă.

1611896826 731 Recursivitatea nu este grea un pas cu pas al acestei

În general, o funcție recursivă are cel puțin două părți: o condiție de bază și cel puțin un caz recursiv.

Să ne uităm la un exemplu clasic.

Factorială

const factorial = function(num) {  debugger;  if (num === 0 || num === 1) {    return 1  } else {    return num * factorial(num - 1)  }}
factorial(5)

Aici încercăm să găsim 5! (cinci factoriale). funcția factorială este definit ca produsul tuturor numerelor întregi pozitive mai mici sau egale cu argumentul său.

Prima condiție prevede: „dacă parametrul trecut este egal cu 0 sau 1, vom ieși și vom returna 1”.

Apoi, cazul recursiv afirmă:

„Dacă parametrul nu este 0 sau 1, atunci vom transmite valoarea lui num ori valoarea returnată a apelării din nou a acestei funcții cu num-1 ca argument al acesteia ”.

Deci, dacă sunăm factorial(0), funcția returnează 1 și nu atinge niciodată cazul recursiv.

Același lucru este valabil și pentru factorial(1).

Putem vedea ce se întâmplă dacă inserăm o instrucțiune de depanare în cod și folosim devtools pentru a păși și a urmări stiva de apeluri.

  1. Stiva de execuție se plasează factorial() cu 5 pe măsură ce argumentul a trecut. Carcasa de bază este falsă, deci introduceți condiția recursivă.
  2. Stiva de execuție se plasează factorial() a doua oară cu num-1 = 4 ca argument. Carcasa de bază este falsă, introduceți condiția recursivă.
  3. Stiva de execuție se plasează factorial() a treia oară cu num-1 (4-1) = 3 ca argument. Carcasa de bază este falsă, introduceți condiția recursivă.
  4. Stiva de execuție se plasează factorial() a patra oară cu num-1(3-1) = 2 ca argument. Carcasa de bază este falsă, introduceți condiția recursivă.
  5. Stiva de execuție se plasează factorial() a cincea oară cu num-1 (2-1) = 1 ca argument. Acum, cazul de bază este adevărat, deci returnează 1.

În acest moment, am redus argumentul cu unul pe fiecare apel de funcție până când ajungem la o condiție pentru a returna 1.

6. De aici se finalizează ultimul context de execuție, num === 1, astfel încât funcția returnează 1.

7. În continuare num === 2, deci valoarea returnată este 2. (1 × 2).

8. În continuare num === 3, astfel încât valoarea de returnare este 6, (2 × 3).

Până acum avem 1 × 2 × 3.

9. Apoi, num === 4, (4 × 6). 24 este valoarea returnată la contextul următor.

10. În cele din urmă, num === 5, (5 × 24) și avem 120 ca valoare finală.

1611896826 898 Recursivitatea nu este grea un pas cu pas al acestei

Recursivitatea este destul de îngrijită, nu?

Am fi putut face același lucru cu o buclă de timp sau de timp. Dar utilizarea recursivității dă o soluție elegantă, care este mai ușor de citit.

Acesta este motivul pentru care folosim soluții recursive.

De multe ori, o problemă împărțită în părți mai mici este mai eficientă. Împărțirea unei probleme în părți mai mici ajută la cucerirea ei. Prin urmare, recursivitatea este o abordare divizată și cucerită pentru rezolvarea problemelor.

  • Subproblemele sunt mai ușor de rezolvat decât problema inițială
  • Soluțiile la subprobleme sunt combinate pentru a rezolva problema inițială

„Împărțiți și cuceriți” este cel mai adesea folosit pentru a traversa sau căuta structuri de date, cum ar fi arborii binari de căutare, grafice și grămezi. De asemenea, funcționează pentru mulți algoritmi de sortare, cum ar fi sortare rapida și grămadă.

Să analizăm următoarele exemple. Folosiți devtools pentru a înțelege conceptual ce se întâmplă unde și când. Nu uitați să utilizați instrucțiunile de depanare și să faceți pas în fiecare proces.

Fibonacci

const fibonacci = function(num) {  if (num <= 1) {    return num  } else {    return fibonacci(num - 1) + fibonacci(num - 2)  }}fibonacci(5);

Matrice recursive

function flatten(arr) {  var result = []  arr.forEach(function(element) {    if (!Array.isArray(element)) {      result.push(element)    } else {      result = result.concat(flatten(element))    }  })  return result}
flatten([1, [2], [3, [[4]]]]);

Inversarea unui șir

function reverse(str) {  if (str.length === 0) return ''  return str[str.length - 1] + reverse(str.substr(0, str.length - 1))}
reverse('abcdefg');

Sortare rapida

function quickSort(arr, lo, hi) {  if (lo === undefined) lo = 0  if (hi === undefined) hi = arr.length - 1
  if (lo < hi) {    // partition the array    var p = partition(arr, lo, hi)    console.log('partition from, ' + lo + ' to ' + hi + '=> partition: ' + p)    // sort subarrays    quickSort(arr, lo, p - 1)    quickSort(arr, p + 1, hi)  }  // for initial call, return a sorted array  if (hi - lo === arr.length - 1) return arr}
function partition(arr, lo, hi) {  // choose last element as pivot  var pivot = arr[hi]  // keep track of index to put pivot at  var pivotLocation = lo  // loop through subarray and if element <= pivot, place element before pivot  for (var i = lo; i < hi; i++) {    if (arr[i] <= pivot) {      swap(arr, pivotLocation, i)      pivotLocation++    }  }  swap(arr, pivotLocation, hi)  return pivotLocation}
function swap(arr, index1, index2) {  if (index1 === index2) return  var temp = arr[index1]  arr[index1] = arr[index2]  arr[index2] = temp  console.log('swapped' + arr[index1], arr[index2], +' in ', arr)  return arr}
quickSort([1, 4, 3, 56, 9, 8, 7, 5])

Practicarea tehnicilor recursive este importantă. Pentru structuri de date imbricate, cum ar fi copaci, grafice și grămezi, recursivitatea este neprețuită.

Într-un articol viitor, voi discuta despre tehnicile de optimizare și memoizare ale apelurilor secundare, în legătură cu recursivitatea. Mulțumesc pentru lectură!

Resurse suplimentare

Wikipedia

Inginerie software

Un alt articol bun

MIT deschis cursuri