Cum functioneaza recursivitatea explicat cu diagramele de flux si
Ilustrație (și toate din acest articol) de Adit Bhargava

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

Recursivitatea poate fi greu de înțeles – mai ales pentru noii programatori. În forma sa cea mai simplă, o funcție recursivă este una care se numește singură. Permiteți-mi să încerc să explic cu un exemplu.

Imaginați-vă că mergeți să deschideți ușa dormitorului și este blocată. Fiul tău de trei ani apare din colț și te anunță că a ascuns singura cheie într-o cutie. („La fel ca el”, credeți.) Ați întârziat la serviciu și chiar trebuie să intrați în cameră pentru a vă cămașa.

Deschideți cutia doar pentru a găsi … mai multe cutii. Cutii în interiorul cutiilor. Și nu știi care dintre ele are cheia! Trebuie să obțineți cămașa în curând, așa că trebuie să vă gândiți la un algoritm bun pentru a găsi acea cheie.

Există două abordări principale pentru a crea un algoritm pentru această problemă: iterativă și recursivă. Iată ambele abordări ca diagrame:

1611780246 27 Cum functioneaza recursivitatea explicat cu diagramele de flux si

Care abordare vi se pare mai ușoară?

Prima abordare utilizează o buclă while. În timp ce grămada nu este goală, apucă o cutie și privește-o. Iată câteva pseudocoduri inspirate de JavaScript care arată ce se întâmplă. (Pseudocodul este scris ca un cod, dar menit să semene mai mult cu vorbirea umană.)

function look_for_key(main_box) {
    let pile = main_box.make_a_pile_to_look_through();
    while (pile is not empty) {
        box = pile.grab_a_box();
        for (item in box) {
            if (item.is_a_box()) {
                pile.append(item)
            } else if (item.is_a_key()) {
                console.log("found the key!")
            }
        }
    }}

A doua modalitate folosește recursivitatea. Amintiți-vă, recursivitatea este locul în care o funcție se numește. Iată a doua modalitate în pseudocod.

function look_for_key(box) {
  for (item in box) {
    if (item.is_a_box()) {
      look_for_key(item);
    } else if (item.is_a_key()) {
      console.log("found the key!")
    } 
  }
}

Ambele abordări realizează același lucru. Scopul principal pentru utilizarea abordării recursive este că, odată ce ați înțeles-o, poate fi mai clar de citit. De fapt, nu există niciun beneficiu în ceea ce privește performanța utilizării recursivității. Abordarea iterativă cu bucle poate fi uneori mai rapidă. Dar, în principal, simplitatea recursivității este uneori preferată.

De asemenea, deoarece mulți algoritmi folosesc recursivitatea, este important să înțelegem cum funcționează. Dacă recursivitatea nu vi se pare simplă, nu vă faceți griji: voi trece peste câteva exemple.

Caz de bază și caz recursiv

Ceva pe care trebuie să-l aveți în vedere atunci când scrieți o funcție recursivă este o buclă infinită. Acesta este momentul în care funcția continuă să se cheme singură … și nu încetează să se cheme singură!

De exemplu, poate doriți să scrieți o funcție de numărătoare inversă. Puteți scrie-o recursiv în JavaScript astfel:

// WARNING: This function contains an infinite loop!
function countdown(i) {  console.log(i)  countdown(i - 1)}

countdown(5);    // This is the initial call to the function.
1611780247 566 Cum functioneaza recursivitatea explicat cu diagramele de flux si

Această funcție va continua să numere invers pentru totdeauna. Dacă executați accidental cod cu o buclă infinită, puteți apăsa „Ctrl-C” pentru a vă ucide scriptul. (Sau, dacă uneori folosiți CodePen ca mine, trebuie să adăugați „? Turn_off_js = true” la sfârșitul adresei URL.)

O funcție recursivă trebuie să spună întotdeauna când se oprește repetarea. O funcție recursivă ar trebui să aibă întotdeauna două părți: cazul recursiv și cazul de bază. Cazul recursiv este atunci când funcția se numește singură. Cazul de bază este atunci când funcția încetează să se mai apeleze. Acest lucru previne bucle infinite.

Iată din nou funcția de numărătoare inversă, cu un caz de bază:

function countdown(i) {
    console.log(i)  if (i <= 1) {  // base case
        return;
    } else {     // recursive case
        countdown(i - 1);
    }
}

countdown(5);    // This is the initial call to the function.
1611780247 901 Cum functioneaza recursivitatea explicat cu diagramele de flux si

Este posibil să nu fie evident exact ce se întâmplă în această funcție. Voi parcurge ceea ce se întâmplă când apelați funcția de numărătoare inversă trecând în „5”.

Începem prin a tipări numărul 5 folosind console.log. Din moment ce cinci sunt nu mai mic sau egal cu zero, mergem la declarația else. Acolo apelăm din nou funcția de numărătoare inversă cu numărul patru (5-1 = 4?).

Înregistram numărul 4. Din nou, i este nu mai mică sau egală cu zero, așa că mergem la instrucțiunea else și apelăm numărătoarea inversă cu 3. Aceasta continuă până când i este egal cu zero. Când se întâmplă acest lucru, înregistrăm numărul zero și apoi i este mai mic sau egal cu zero. În cele din urmă ajungem la declarația return și ieșim din funcție.

Pila de apeluri

Funcțiile recursive folosesc ceva numit „stiva de apeluri”. Când un program apelează o funcție, acea funcție merge în partea de sus a stivei de apeluri. Acest lucru este similar cu un teanc de cărți. Adăugați lucruri pe rând. Apoi, când sunteți gata să scoateți ceva, scoateți întotdeauna elementul de sus.

Vă voi arăta stiva de apeluri în acțiune cu factorial funcţie. factorial(5) este scris ca 5! și se definește astfel: 5! = 5 * 4 * 3 * 2 * 1. Iată o funcție recursivă pentru a calcula factorialul unui număr:

function fact(x) {
    if (x == 1) {
        return 1;
    } else {
        return x * fact(x-1);
    }
}

Acum să vedem ce se întâmplă dacă suni fact(3) Ilustrația de mai jos arată cum se schimbă stiva, linie cu linie. Căsuța de sus din stivă vă spune la ce apel fact ești în prezent.

1611780247 501 Cum functioneaza recursivitatea explicat cu diagramele de flux si
1611780247 618 Cum functioneaza recursivitatea explicat cu diagramele de flux si
Credit de imagine: Adit Bhargava

Observați modul în care fiecare apel fact are propria copie a x. Acest lucru este foarte important pentru ca recursivitatea să funcționeze. Nu puteți accesa o copie a unei alte funcții x.

Ai găsit încă cheia?

Să ne întoarcem pe scurt la exemplul original despre căutarea unei chei în căsuțe imbricate. Amintiți-vă, prima metodă a fost iterativă folosind bucle. Cu această metodă, creați o grămadă de cutii pe care să le căutați, astfel încât să știți întotdeauna ce cutii mai trebuie să căutați.

1611780248 311 Cum functioneaza recursivitatea explicat cu diagramele de flux si

Dar nu există o grămadă în abordarea recursivă. De unde știe algoritmul tău în ce casete mai trebuie să te uiți? „Mormanul de cutii” este salvat pe teanc. Acesta este un teanc de apeluri de funcții pe jumătate finalizate, fiecare cu propria listă de cutii pe jumătate completă pentru a căuta. Stiva ține evidența teancului de cutii pentru dvs.!

Și datorită recursivității, puteți găsi în cele din urmă cheia și puteți obține cămașa!

1611780248 261 Cum functioneaza recursivitatea explicat cu diagramele de flux si

Puteți viziona și acest videoclip de 5 minute pe care l-am făcut despre recursivitate. Ar trebui să consolideze aceste concepte de recursivitate.

Concluzie

Sper că acest articol vă va aduce mai multă claritate despre recursivitatea în programare. Acest articol se bazează pe o lecție din noul meu curs video de la Manning Publications Algoritmi în mișcare. Cursul (și, de asemenea, acest articol) se bazează pe uimitor carte Algoritmi Grokking de Adit Bhargava. El este cel care a desenat toate ilustrațiile distractive din acest articol.

Dacă înveți cel mai bine prin cărți, ia cartea! Dacă înveți cel mai bine prin videoclipuri, ia în considerare cumpărându-mi cursul.

Obțineți o reducere de 39% a cursului meu folosind codul ‘39carnes‘!

1611780248 741 Cum functioneaza recursivitatea explicat cu diagramele de flux si

Și, în cele din urmă, pentru a înțelege cu adevărat recursivitatea, trebuie să citiți din nou acest articol. ?