Rekurzija nije teška: korak po korak kroz ovu korisnu tehniku ​​programiranja

Reći ću ovo odmah. Znate li događaje koji se događaju nakon pozivanja funkcije? Ne? Tada ćemo tu početi.

Pozivanje funkcije

Kad pozovemo funkciju, kontekst izvršenja stavlja se na stek izvršenja. Razmotrimo ovo još malo.

Prvo, što je stog?

Stog je struktura podataka koja djeluje na osnovi "Posljednji ulaz, prvi izlaz". Stavka se "gurne" na stog da bi se dodala, a stavka se "iskoči" iz hrpe da bi se uklonila.

Korištenje stoga metoda je naređivanja određenih operacija za izvršenje.

Sad, vratimo se što je kontekst izvršenja? Kontekst izvršenja formira se nakon pozivanja funkcije. Ovaj se kontekst postavlja na stek izvršenja, redoslijed operacija. Stavka koja je uvijek prva u ovom stogu je globalni kontekst izvršenja. Slijede svi konteksti stvoreni funkcijom.

Ovi konteksti izvršenja imaju svojstva, objekt za aktivaciju i "ovo" vezanje. Obveznik "this" referenca je na ovaj kontekst izvršenja. Objekt aktivacije uključuje: proslijeđene parametre, deklarirane varijable i deklaracije funkcija.

Dakle, svaki put kad na stog postavimo novi kontekst, obično imamo sve što nam treba za izvršavanje koda.

Zašto kažem obično ?

S rekurzijom čekamo povratne vrijednosti koje dolaze iz drugih konteksta izvršavanja. Ovi su drugi konteksti viši na vrhu. Kada zadnja stavka u stogu završi izvršenje, taj kontekst generira povratnu vrijednost. Ova se povratna vrijednost prenosi kao povratna vrijednost iz rekurzivnog slučaja u sljedeću stavku. Taj se kontekst izvršavanja tada iskače iz stoga.

Rekurzija

Pa, što je rekurzija?

Rekurzivna funkcija je funkcija koja se sama poziva sve dok "osnovni uvjet" nije istinit i izvršenje se zaustavi.

Iako je false, nastavit ćemo postavljati kontekste izvršavanja na vrh stoga. To se može dogoditi dok ne imamo "preljev stoga". Prekomjerni stek je kada nam ponestane memorije za držanje predmeta u stogu.

Općenito, rekurzivna funkcija ima najmanje dva dijela: osnovni uvjet i barem jedan rekurzivni slučaj.

Pogledajmo klasični primjer.

Faktorijel

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

Ovdje pokušavamo pronaći 5! (pet faktora). Faktorska funkcija definira se kao umnožak svih pozitivnih cijelih brojeva manjih ili jednakih njegovom argumentu.

Prvi uvjet glasi: "ako je preneseni parametar jednak 0 ili 1, izaći ćemo i vratiti 1".

Dalje, rekurzivni slučaj navodi:

"Ako parametar nije 0 ili 1, tada ćemo proslijediti vrijednost numputa vraćenu vrijednost ponovnog poziva ove funkcije s num-1argumentom".

Dakle, ako pozovemo factorial(0), funkcija vraća 1 i nikada ne pogađa rekurzivni slučaj.

Isto vrijedi i za factorial(1).

Možemo vidjeti što se događa ako u kod umetnemo iskaz za otklanjanje pogrešaka i pomoću njega razvijemo korake i promatramo hrpu poziva.

  1. Izvršni stog stavlja factorial()peticu dok je argument prolazio. Osnovni slučaj je netočan, zato unesite rekurzivno stanje.
  2. Izvršni stog factorial()drugi put postavlja num-1argument = 4. Osnovni slučaj je netočan, unesite rekurzivno stanje.
  3. Izvršni stog postavlja factorial()treći put s num-1argumentom (4–1) = 3. Osnovni slučaj je netočan, unesite rekurzivno stanje.
  4. Izvršni stog postavlja factorial()četvrti put s num-1(3–1) = 2 kao argument. Osnovni slučaj je netočan, unesite rekurzivno stanje.
  5. Izvršni stog postavlja factorial()peti put s num-1argumentom (2–1) = 1. Sada je osnovni slučaj istinit, pa vratite 1.

U ovom trenutku smanjili smo argument za jedan na svakom pozivu funkcije dok ne postignemo uvjet za vraćanje 1.

6. Odavde se dovršava zadnji kontekst izvršenja num === 1, tako da funkcija vraća 1.

7. Dalje num === 2, pa je povratna vrijednost 2. (1 × 2).

8. Dalje num === 3, povratna vrijednost je 6, (2 × 3).

Zasad imamo 1 × 2 × 3.

9. Dalje,, num === 4(4 × 6). 24 je povratna vrijednost u sljedeći kontekst.

10. Napokon, num === 5(5 × 24) i imamo 120 kao konačnu vrijednost.

Rekurzija je prilično uredna, zar ne?

Mogli smo učiniti istu stvar s for ili time loop. Ali upotreba rekurzije daje elegantno rješenje koje je čitljivije.

Zbog toga koristimo rekurzivna rješenja.

Mnogo je puta problem raščlanjen na manje dijelove učinkovitiji. Podjela problema na manje dijelove pomaže u njegovom osvajanju. Stoga je rekurzija pristup dijeljenja i osvajanja u rješavanju problema.

  • Podprobleme je lakše riješiti od izvornih problema
  • Rješenja za potprobleme kombiniraju se za rješavanje izvornog problema

"Podijeli i osvoji" najčešće se koristi za prelazak ili pretraživanje podataka, poput binarnih stabala pretraživanja, grafikona i gomila. Također radi za mnoge algoritme za sortiranje, poput brzog sortiranja i sortiranja.

Poradimo na sljedećim primjerima. Upotrijebite devtools da biste konceptualno shvatili što se događa gdje i kada. Ne zaboravite koristiti izrade programa za otklanjanje pogrešaka i korake kroz svaki postupak.

Fibonacci

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

Rekurzivni nizovi

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]]]]);

Obrtanje niza

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

Quicksort

function quickSort(arr, lo, hi) { if (lo === undefined) lo = 0 if (hi === undefined) hi = arr.length - 1
 if (lo  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])

Vježbanje rekurzivnih tehnika je važno. Za ugniježđene podatkovne strukture poput stabala, grafova i gomila, rekurzija je neprocjenjiva.

U budućem članku raspravljat ću o tehnikama optimizacije i memoriranja povratnih poziva koje se odnose na rekurziju. Hvala na čitanju!

Daljnji resursi

Wikipedija

Software Engineering

Another good article

M.I.T. open courseware