Rekursija nėra sunki: šios naudingos programavimo technikos žingsnis po žingsnio

Aš tai pasakysiu iškart. Ar žinote įvykius, įvykstančius iškviečiant funkciją? Ne? Tada nuo to ir pradėsime.

Funkcijos iškvietimas

Kai iškviečiame funkciją, vykdymo kontekstas patenka į vykdymo kaminą. Dar suskaidykime tai.

Pirma, kas yra kaminas?

Šūsnis yra duomenų struktūra, veikianti „Paskutinis įėjimas, pirmas išėjimas“ principu. Elementas „stumiamas“ ant kamino, kad jį būtų galima pridėti, o daiktas yra „iššokęs“ nuo kamino, kad jį pašalintų.

Šūsnio naudojimas yra tam tikrų operacijų užsakymo vykdymo būdas.

Dabar grįžkime prie įvykdymo konteksto? Vykdymo kontekstas susidaro iškvietus funkciją. Šis kontekstas patenka į vykdymo kaminą, operacijų tvarką. Elementas, kuris visada yra pirmas šioje rietuvėje, yra visuotinis vykdymo kontekstas. Toliau yra bet kurios funkcijos sukurti kontekstai.

Šie vykdymo kontekstai turi savybių, aktyvinimo objektą ir „šį“ susiejimą. „Šis“ įrišimas yra nuoroda į šį vykdymo kontekstą. Aktyvinimo objektą sudaro: perduoti parametrai, deklaruoti kintamieji ir funkcijų deklaracijos.

Taigi kiekvieną kartą, kai ant kamino dedame naują kontekstą, paprastai turime viską, ko reikia kodui vykdyti.

Kodėl sakau paprastai ?

Su rekursija laukiame grąžinimo verčių, gaunamų iš kitų vykdymo kontekstų. Šie kiti kontekstai yra aukščiau. Kai paskutinis kamino elementas baigs vykdyti, tas kontekstas sukuria grąžinimo vertę. Ši grąžinimo vertė perduodama kaip grįžtamoji vertė iš rekursinio atvejo į kitą elementą. Tada tas vykdymo kontekstas iššoka iš rietuvės.

Rekursija

Taigi, kas yra rekursija?

Rekursinė funkcija yra funkcija, kuri save vadina tol, kol įvyksta „pagrindinė sąlyga“, ir vykdymas sustoja.

Nors klaidinga, vykdymo kontekstus mes laikysime ant kamino viršaus. Tai gali atsitikti tol, kol mes neturime „kamino perpildymo“. Kamino perpildymas yra tada, kai pritrūksta atminties laikyti daiktus rietuvėje.

Paprastai rekursinė funkcija turi bent dvi dalis: pagrindinę sąlygą ir bent vieną rekursišką atvejį.

Pažvelkime į klasikinį pavyzdį.

Faktoralis

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

Čia mes bandome rasti 5! (penki faktoriai). Faktorinė funkcija apibrėžiama kaip visų teigiamų sveikųjų skaičių, mažesnių arba lygių jos argumentui, sandauga.

Pirmoji sąlyga teigia: „jei perduotas parametras lygus 0 arba 1, išeisime ir grįšime 1“.

Toliau rekursinis atvejis nurodo:

"Jei parametras nėra 0 arba 1, tada mes perduosime vertės, numpakartotinės vertės, pakartotinai iškviečiant šią funkciją num-1, argumentą".

Taigi, jei mes paskambinsime factorial(0), funkcija grąžins 1 ir niekada nepasieks rekursinio atvejo.

Tas pats galioja ir factorial(1).

Mes galime pamatyti, kas vyksta, jei į kodą įterpiame derintuvo pareiškimą ir naudodamiesi devtools žengsime jį ir stebėsime skambučių kaminą.

  1. Vykdymo kamino vieta factorial()yra 5, kai argumentas praėjo. Pagrindinis atvejis yra klaidingas, todėl įveskite rekursinę sąlygą.
  2. Vykdymo kaminas factorial()antrą kartą pateikiamas kaip num-1= 4 kaip argumentas. Pagrindinė byla yra klaidinga, įveskite rekursinę sąlygą.
  3. Vykdymo kaminas factorial()trečią kartą pateikia num-1argumentą (4–1) = 3. Pagrindinė byla yra klaidinga, įveskite rekursinę sąlygą.
  4. Vykdymo kaminas pateikia factorial()ketvirtą kartą num-1argumentu (3–1) = 2. Bazė yra neteisinga, įveskite rekursinę sąlygą.
  5. Vykdymo kaminas pateikia factorial()penktą kartą num-1argumentu (2–1) = 1. Dabar pagrindinė byla yra teisinga, todėl grąžinkite 1.

Šiuo metu mes sumažinome argumentą po vieną kiekviename funkcijos iškvietime, kol pasieksime sąlygą grąžinti 1.

6. Iš čia paskutinis vykdymo kontekstas baigiamas num === 1, taigi funkcija grąžina 1.

7. Toliau num === 2, todėl grąžinimo vertė yra 2. (1 × 2).

8. Toliau num === 3grąžinimo vertė yra 6, (2 × 3).

Kol kas turime 1 × 2 × 3.

9. Kitas, num === 4(4 × 6). 24 yra grąžinimo vertė į kitą kontekstą.

10. Galiausiai, num === 5(5 × 24), o galutinė vertė yra 120.

Rekursija yra gana tvarkinga, tiesa?

Mes galėjome tą patį padaryti „a“ arba „while“ kilpa. Tačiau naudojant rekursiją gaunamas elegantiškas sprendimas, kuris yra labiau įskaitomas.

Štai kodėl mes naudojame rekursinius sprendimus.

Daug kartų problema, suskaidyta į mažesnes dalis, yra efektyvesnė. Problemos padalijimas į mažesnes dalis padeda ją užkariauti. Taigi rekursija yra „skaldyk ir užvaldyk“ metodas sprendžiant problemas.

  • Papildomas problemas lengviau išspręsti nei pradinę problemą
  • Pirminės problemos sprendimui derinami subproblemų sprendimai

„Skaldyti ir užkariauti“ dažniausiai naudojamas norint pereiti arba ieškoti duomenų struktūrų, pvz., Dvejetainių paieškos medžių, grafikų ir kaupų. Tai taip pat tinka daugeliui rūšiavimo algoritmų, tokių kaip „quicksort“ ir „heapsort“.

Panagrinėkime šiuos pavyzdžius. Naudokite devtools, kad suprastumėte, kas vyksta kur ir kada. Nepamirškite naudoti derintuvo pareiškimų ir atlikite veiksmus kiekviename procese.

Fibonači

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

Rekurziniai masyvai

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

Stygos pakeitimas

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

Rekurzinių metodų praktika yra svarbi. Įterptoms duomenų struktūroms, tokioms kaip medžiai, grafikai ir krūvos, rekursija yra neįkainojama.

Būsimame straipsnyje aptarsiu uodegos skambučio optimizavimo ir atminties perdavimo būdus, susijusius su rekursija. Ačiū, kad skaitėte!

Kiti ištekliai

Vikipedija

Programinės įrangos inžinerija

Dar vienas geras straipsnis

MIT atvira programinė įranga