„Pentru a înțelege recursivitatea, trebuie mai întâi să înțelegem recursivitatea” – Necunoscut

Dacă sunteți ca mine, atunci probabil că nu ați înțeles recursiunea prima dată când ați citit despre asta.

Pentru mine a fost pentru că

  1. recursivitatea este un concept greu în sine și
  2. unele dintre tutoriale și articole pe care le-am citit nu erau foarte clare.

Din anumite motive, majoritatea articolelor care explicau recursivitatea foloseau exemplul numerelor factoriale și secvența Fibonacci. Asta a însemnat că a trebuit să înțeleg modul în care funcționează numerele Fibonacci, apoi să conectez asta la recursivitate.

Dar luăm o altă cale în acest articol.

Ce este recursivitatea?

În termenii de bază, recursivitatea este atunci când o funcție continuă să se apeleze până când nu mai trebuie.

Ce? Da, funcția continuă să se apeleze singură, dar cu o intrare mai mică de fiecare dată.

Gândiți-vă la recursivitate ca la o cursă de circuit. Este ca și cum ai alerga aceeași pistă iar și iar, dar tururile se micșorează de fiecare dată. În cele din urmă, vei alerga ultima, cea mai mică tură și cursa se va termina.

La fel și cu recursivitatea: funcția continuă să se apeleze cu o intrare mai mică și în cele din urmă se oprește.

Dar funcția nu decide singură când să se oprească. Îi spunem când să se oprească. Oferim funcției o condiție cunoscută sub numele de caz de baza.

Carcasa de bază este condiția care indică funcției când trebuie să se oprească. Este ca și cum ai spune funcției care va fi ultima tură în cursă, astfel încât să nu mai alerge după turul respectiv.

Exemple de recursivitate

Bine asta este recursivitate. Să ne uităm la câteva exemple pentru a înțelege cum funcționează recursivitatea.

Vă amintiți prima dată când ați aflat despre bucle? Primul exemplu pe care l-ați făcut probabil a fost un program de numărătoare inversă. Hai să facem asta.

În primul rând, să înțelegem ce vrem să facă programul nostru. Numărați înapoi de la un număr dat la cel mai mic număr, scăzând 1 de fiecare dată.

Având în vedere numărul 5, ne așteptăm ca rezultatul să fie ceva de genul:

// 5
// 4
// 3
// 2
// 1

Bine, cum putem codifica acest program cu recursivitate?

let countDown = number => {
    //base case
    if (number === 0) {
        return;
    }
    console.log(number);
    return countDown(number - 1);
};
console.log(countDown(5)) // 5, 4, 3, 2, 1

Deci, ce se întâmplă exact aici?

Dacă ați observat, primul lucru pe care l-am făcut a fost să definim cazul de bază. De ce? Pentru că funcția trebuie să știe mai întâi când va înceta să se mai cheme.

Nu ați alerga niciodată într-o cursă fără să știți mai întâi cât este cursa, nu-i așa?

Dacă nu spuneți funcției când să se oprească, atunci se va întâmpla ceva numit stackoverflow. Stiva se va umple cu funcții care sunt apelate, dar nu se întorc sau sunt scoase din stivă.

Bitul recursiv al acestuia se întâmplă de fapt pe linia 7. Acolo îi spunem funcției să se întoarcă în continuare, însă reducând de fiecare dată intrarea cu una.

Deci, efectiv, asta se întâmplă:

// The current input is 5
// Is 5 equal to 0 ?
// No, Ok so lets log 5 to the console.
// Its calls Itself again with number - 1 OR 5 - 1;
// The current input is 4
// Is 4 equal to 0 ?
// No, Ok so lets log 4 to the console
// Repeats until input is 0 so then function stops calling itself. 

Bine, asta avea sens. Să încercăm un alt exemplu.

Știți cum putem spune că un număr este egal folosind operatorul rest (%)? Deci, dacă orice număr% 2 == 0 atunci acel număr este par sau dacă orice număr% 3 == 0 atunci acel număr este impar.

Ei bine, se pare că există o altă metodă.

Dacă scădem în mod continuu două dintr-un număr până când cel mai mic număr este fie 0, fie 1 putem spune dacă numărul este par sau impar.

Să încercăm asta cu recursivitate. Deci, având în vedere numărul 6, programul nostru ar trebui să revină ‘Chiar’ deoarece 6-2-2-2 = 0. Având în vedere 7, programul nostru ar trebui să revină ‘ciudat’ deoarece 7-2-2-2 = 1.

Să o vedem în cod.

let oddOrEven = (number) => {
    if (number === 0) {
        return 'Even';
    } else if (number === 1) {
        return 'Odd';
    } else {
        return oddOrEven(number - 2);
    }
};
console.log(oddOrEven(20)) // Even
console.log(oddOrEven(75)) // Odd
console.log(oddOrEven(98)) // Even
console.log(oddOrEven(113)) // Odd

Din nou, primul pas a fost să spui funcției când să încetezi să o mai numești. Apoi i-am spus ce să facă atunci când se numește singur.

Recursiunea este practic împărțiți și cuceriți. Continuăm să împărțim problema, făcând-o mai mică de fiecare dată.

Recursivitate vs Bucle

Când vine vorba de viteză, o buclă rulează mult mai repede decât o funcție recursivă. De asemenea, este mai ușor să scrieți o buclă decât o funcție recursivă. Și când vine vorba de lizibilitate, este mai ușor să știți ce se întâmplă cu o buclă decât o funcție recursivă.

Dar funcțiile recursive sunt foarte elegante.

Deci, care este cea mai bună alegere? Eficiență sau viteză?

Iată un citat din cartea JavaScript elocventă.

Îngrijorarea cu privire la eficiență poate fi o distragere a atenției. Este încă un alt factor care
complică proiectarea programului și atunci când faci ceva care este deja
dificil, acel lucru în plus de care să-ți faci griji poate fi paralizant.
Prin urmare, începeți întotdeauna prin a scrie ceva corect și ușor de înțeles.
Dacă vă faceți griji că este prea lent – ceea ce de obicei nu mai este
majoritatea codului pur și simplu nu este executat suficient de des pentru a lua o cantitate semnificativă
de timp – puteți măsura ulterior și îmbunătăți dacă este necesar.

În acest moment s-ar putea să vă întrebați de ce în lume ați alege vreodată să scrieți o funcție recursivă pe o buclă. Adică buclele sunt mult mai ușoare nu?

Ei bine, este adevărat – dar există unele probleme care sunt mai ușor de rezolvat cu recursivitate. Dacă doriți să explorați o astfel de problemă, atunci luați în considerare citirea capitolul 3 de JavaScript elocvent.

Acum, că ați descoperit o nouă super putere, hai să o folosim.

Efectuați următoarele exerciții folosind recursivitatea. Dacă simți că poți prelua mai mult, atunci poți rezolva faimoasele probleme factoriale și ale secvenței Fibonacci.

Exerciții

Dacă doriți să vă provocați în continuare, luați în considerare rezolvarea acestor probleme recursive.

  1. Scrieți un program care inversează un șir folosind recursivitate. Dat fiind șirul „Routech”, programul dvs. ar trebui să returneze „pmaCedoCeerf”.
  2. Scrieți un program care returnează de câte ori apare un caracter în șir. Programul dvs. ar trebui să primească un șir și caracterul. Apoi ar trebui să returneze de câte ori apare caracterul în șir.
    Având în vedere șirul „JavaScript” și un caracter „a”, programul dvs. ar trebui să returneze 2.

    Aluzie: Încercați să vă dați seama când doriți ca funcția să nu se mai apeleze și cum să reveniți la o versiune mai mică a problemei de fiecare dată când funcția se apelează.

Asta este tot pentru acest articol. Sper că v-a ajutat să înțelegeți în continuare recursivitatea.

Dacă ți-a plăcut acest articol, te poți conecta cu mine pe Stare de nervozitate.