Înțelegerea recursului cu JavaScript

Introducere

Unele probleme sunt rezolvate mai natural folosind recursion. De exemplu, o secvență cum ar fi Fibonacci are o definiție recursivă. Fiecare număr din acesta este suma celor două numere anterioare ale secvenței. Problemele care vă cer să construiți sau să tăiați o structură de date asemănătoare copacului pot fi, de asemenea, rezolvate cu recursion. Trenul pentru a gândi recursiv vă va oferi o capacitate puternică de a aborda aceste probleme.

În acest tutorial voi face o revizuire pas cu pas a mai multor funcții recursive pentru a vedea cum funcționează și vă arată tehnici pe care le puteți utiliza pentru a defini sistematic funcțiile recursive.

Conținut:

• Care este recursiunea?
• Recursiune cu numere
• Recursiune cu liste
• Liste de clădiri

Ce este recursiunea?

O funcție definită recursiv este o funcție care este definită în termeni de o versiune mai simplă a lui. Acesta este un exemplu simplificat:

function doA(n) { ... doA(n-1);}

Pentru a înțelege modul în care recurgerea funcționează conceptual, vom vedea un exemplu care nu are nimic de-a face cu codul. Imaginați-vă că sunteți responsabil pentru a răspunde la apelurile telefonice în munca dvs. Deoarece aceasta este o companie aglomerată, telefonul dvs. are mai multe linii, astfel încât să puteți participa la mai multe apeluri în același timp. Fiecare linie telefonică este un buton pe receptor și când există un apel primit, butonul va clipi. Astăzi, când ajungeți la locul de muncă și porniți telefonul, există patru linii care clipeau în același timp. Prin urmare, începeți să lucrați la răspunsuri la toate apelurile.

Răspundeți la linia unu și spuneți „Vă rugăm să așteptați”. Apoi răspundeți la linia a două și puneți-o în așteptare. Mai jos răspundeți la cele trei linii și puneți-l în așteptare. În cele din urmă, răspundeți la a patra linie și discutați cu persoana pe care o apelați. Când ați terminat cu cea de-a patra persoană, atârnă și răspundeți la al treilea apel. Când ați terminat cu al treilea apel, închideți și răspundeți la al doilea. Când ați terminat cu al doilea apel, închideți și răspundeți la prima. Când ajungeți la acel apel, puteți să închideți telefonul.

Fiecare dintre apelurile telefonice ale acestui exemplu este ca un apel recursiv într-o funcție. Când primiți un apel, acesta este plasat pe stiva de apel (în termeni de cod). Dacă nu puteți termina imediat un apel, atunci stați în așteptare. Dacă aveți un apel către o funcție care nu poate fi evaluată imediat, acesta rămâne în stiva de apeluri. Când puteți răspunde la un apel, acesta este servit. Când codul dvs. este capabil să evalueze apelul la o funcție, acesta este scos din stivă. Aveți în vedere această analogie în timp ce verificați următoarele exemple de cod.

Recursiune cu numere

Toate funcțiile recursive au nevoie de un caz de bază pentru a putea termina. Cu toate acestea, simplul fapt de adăugare a unui caz de bază la funcția noastră nu va împiedica să funcționeze infinit. Funcția trebuie să facă un pas pentru a se apropia de cazul de bază. În cele din urmă, există pasul recursiv. În etapa recursivă, problema este redusă la o versiune mai mică a problemei.

Să presupunem că aveți o funcție care va adăuga numerele de la 1 la n. De exemplu, dacă n = 4, funcția va adăuga 1 + 2 + 3 + 4.

Mai întâi determinăm cazul de bază. Găsirea cazului de bază este ca găsirea cazului în care problema poate fi rezolvată fără recursură. În acest exemplu, atunci când n este egal cu zero. Zero nu are părți, astfel încât recursiunea noastră se poate opri când sosesc la 0.

în fiecare pas veți scădea valoarea unu la numărul curent. Care este cazul recursiv? Cazul recursiv este funcția Suma a fost invocată cu numărul redus.

function sum(num){ if (num === 0) { return 0; } else { return num + sum(--num) }}sum(4); //10

Acesta este ceea ce se întâmplă în fiecare pas:

• Du-te la suma (4).
• 4 este egal cu 0? Numărul de sumă (4) în așteptare și treceți la suma (3).
• 3 este egal cu 0? Numărul de sumă (3) în așteptare și treceți la suma (2).
• 2 este egal cu 0? Numărul de sumă (2) în așteptare și treceți la suma (1).
• 1 este egal cu 0? Nr. Așezați suma (1) în așteptare și mergeți la suma (0).
• 0 este egal cu 0? Da. Evaluați suma (0).
• reta suma (1).
• reta suma (2).
• reta suma (3).
• RETA SUS (4).

Acesta este un alt mod de a vedea cum funcția procesează fiecare apel:

sum(4)4 + sum(3)4 + ( 3 + sum(2) )4 + ( 3 + ( 2 + sum(1) ))4 + ( 3 + ( 2 + ( 1 + sum(0) )))4 + ( 3 + ( 2 + ( 1 + 0 ) ))4 + ( 3 + ( 2 + 1 ) )4 + ( 3 + 3 ) 4 + 6 10

Argumentul trebuie să se schimbe în cazul recursiv și să abordeze cazul de bază. Acest argument trebuie verificat în cazul de bază. În exemplul anterior, deoarece restabilim valoarea 1 în cazul recursiv trebuie să verificăm dacă argumentul este egal cu zero în cazul nostru de bază.

sarcină

1. implementare funcția SME folosind un ciclu în loc de recursură.
2. creează o funcție care multiplică două numere recursiv. De exemplu, multiply(2,4) va avea ca rezultat ce se întâmplă în fiecare pas pentru multiply(2,4).

Recursiunea cu liste

Recursiunea pe o listă este similară cu recursiunea într-un număr, dar în loc să reducă numărul la fiecare pas, vom reduce lista la fiecare pas până când avem o listă goală.

Luați în considerare funcția de sumă care primește o listă ca intrare și returnează suma tuturor elementelor acestei liste. Aceasta este o implementare pentru funcția sumară:

function sum(l){ if (empty(l)) { return 0; } else { return car(l) + sum(cdr(l)); }}

Funcția empty Returnează valoarea TRUE (TRUE) dacă Lista nu are elemente. Funcția car Returnează primul element din listă. De exemplu, car() Returnează valoarea 1. Funcția cdr Returnează lista fără primul element. De exemplu, cdr() returnări. Ce se întâmplă atunci când executăm sum()

sum()1 + sum()1 + ( 2 + sum() )1 + ( 2 + ( 3 + sum() ))1 + ( 2 + ( 3 + ( 4 + sum() )))1 + ( 2 + ( 3 + ( 4 + 0 ) ))1 + ( 2 + ( 3 + 4 ) )1 + ( 2 + 7 ) 1 + 910

atunci când rulați recursiunea pe o listă este revizuită dacă este goală. În caz contrar, etapa recursivă este efectuată într-o versiune redusă a listei.

sarcină

1. replică această sumă funcție, astfel încât să utilizați un ciclu pentru a adăuga fiecare element de la Lista în loc să utilizeze recursiunea.
2. definește o funcție numită Lungime (lungime) care primește o listă ca intrare și returnează numărul de elemente din lista respectivă. Nu trebuie să utilizați funcția de lungime integrată în JavaScript. De exemplu, length() trebuie să returneze valoarea 4. Scrieți ce se întâmplă la fiecare pas.

Liste de clădiri

în Ultimul exemplu pe care ne-am întors un număr. Dar să presupunem că vrem să reamintim o listă. Aceasta înseamnă că, în loc să adăugați un număr la pasul nostru recursiv, trebuie să adăugăm o listă. Luați în considerare funcția remove (Ștergere), care primește un element și o listă ca intrare și returnează lista fără elementul pe care vrem să îl eliminăm. Numai primul element pe care îl găsim va fi eliminat.

function remove(item, l){ if (empty(l)) { return ; } else if (eq(car(l), item)) { return cdr(l); } else { return cons(car(l), remove(item, cdr(l))); }}remove('c', ) //

aici, funcția eq Returnează o valoare reală (adevărat) dacă ambele intrări sunt egale. cons primește un element și o listă ca intrări și returnează o nouă listă cu elementul adăugat la începutul acestuia.

Verifică dacă primul element din listă este egal cu elementul pe care dorim să îl ștergeți. Dacă da, ștergeți primul element din listă și returnează noua listă. Dacă primul element nu este egal cu elementul pe care dorim să-l ștergeți, luăm primul element din listă și adăugăm la pasul recursiv. Etapa recursivă va conține lista cu primul element eliminat.

Vom continua să eliminăm elementele până când ajungem la cazul nostru, care este o listă goală. O listă goală înseamnă că am călătorit toate elementele sale. Ce face funcția remove('c', )?

remove('c', )cons( ‘a’, remove(‘c’, ) )cons( ‘a’ , cons( ‘b’, remove(‘c’, ) ))cons( ‘a’, cons( ‘b’, )cons( ‘a’, )

Într-o situație în care trebuie să construim o listă, luăm Primul element și îl adăugăm la partea recursivă a listei noastre.

sarcină

1. strângeți funcția de eliminare, astfel încât să utilizați cicluri în loc de recurs pentru a șterge un element de la ștergere O listă.
2. Modificați funcția Eliminare pentru a elimina toate aparițiile dintr-un element dintr-o listă. De exemplu, remove(‘c’, returnări. Scrieți ce se întâmplă pas cu pas.

Review

O funcție recursivă are trei părți. Primul este cazul de bază, care este starea terminalului. Al doilea este pasul care vine la cazul nostru de bază. Al treilea este pasul recursiv, în care funcția este invocată pentru o intrare redusă.

Recursiunea este ca o iterație. Orice funcție pe care o puteți defini recursiv poate fi de asemenea definită utilizând cicluri. Alte aspecte care trebuie luate în considerare la utilizarea acestei tehnici sunt recursiunea în listele imbricate și optimizarea apelurilor dvs. recursive.

O resursă excelentă pentru a continua învățarea despre recursiune este cartea micul schemer. Acest lucru vă învață să vă gândiți la recursiv folosind un format de întrebări și răspunsuri.