Rekursioon pole keeruline: selle kasuliku programmeerimistehnika üksikasjalik ülevaade

Ma ütlen selle kohe ära. Kas teate sündmusi, mis toimuvad funktsiooni kutsumisel? Ei? Siis alustame sellest.

Funktsioonide kutsumine

Kui kutsume funktsiooni, paigutatakse täitmisekontekst käivitamise virnale. Lammutame selle veel ära.

Esiteks, mis on virn?

Virn on andmestruktuur, mis töötab põhimõttel „Viimane sisse, esimene välja“. Üksus “lükatakse” selle lisamiseks virnale ja üksus “eemaldatakse” virnast selle eemaldamiseks.

Virna kasutamine on meetod teatud toimingute tellimiseks täitmiseks.

Nüüd, mis on hukkamiskontekst? Täitmise kontekst moodustub funktsiooni kutsumisel. See kontekst asetab end täitmise virnale, toimingute järjekorrale. Üksus, mis on selles virnas alati esimene, on globaalne täitmise kontekst. Järgmisena on funktsioonide loodud kontekstid.

Nendel täitmiskontekstidel on omadused, aktiveerimisobjekt ja sidumine „see”. „See” sidumine on viide sellele täitmise kontekstile. Aktiveerimisobjekt sisaldab: edastatud parameetreid, deklareeritud muutujaid ja funktsioonide deklaratsioone.

Nii et iga kord, kui asetame virnale uue konteksti, on meil tavaliselt kõik koodi täitmiseks vajalik.

Miks ma tavaliselt ütlen ?

Rekursiooniga ootame tagasiväärtusi, mis tulevad muudest täitmiskontekstidest. Need muud kontekstid on virnas kõrgemal. Kui virna viimane üksus on täitmise lõpetanud, loob see kontekst tagastusväärtuse. See tagastusväärtus antakse tagasi väärtusena rekursiivsest juhtumist järgmisele üksusele. See hüppekontekst hüpatakse seejärel virnast välja.

Rekursioon

Mis on rekursioon?

Rekursiivne funktsioon on funktsioon, mis kutsub ennast seni, kuni “põhitingimus” on tõene ja täitmine peatub.

Ehkki vale, paigutame jätkamise kontekstid virna kohale. See võib juhtuda seni, kuni meil tekib „virna ülevool”. Virna ületäitumine on siis, kui mälu saab otsa virnas olevate üksuste hoidmiseks.

Üldiselt on rekursiivsel funktsioonil vähemalt kaks osa: põhitingimus ja vähemalt üks rekursiivne juhtum.

Vaatame klassikalist näidet.

Factorial

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

Siin proovime leida 5! (viis faktoori). Faktooriafunktsioon on määratletud kui kõigi positiivsete täisarvude korrutis, mis on selle argumentist väiksem või sellega võrdne.

Esimene tingimus ütleb: "kui edastatud parameeter võrdub 0 või 1, väljume ja tagastame 1".

Järgmisena ütleb rekursiivne juhtum:

"Kui parameeter pole 0 või 1, siis edastame numselle funktsiooni uuesti num-1argumendiks kutsumise tagastatava väärtuse kordade väärtuse ".

Nii et kui helistame factorial(0), tagastab funktsioon 1 ja ei taba kunagi rekursiivset juhtumit.

Sama kehtib ka factorial(1).

Me näeme, mis juhtub, kui sisestame koodi siluri avalduse ja kasutame selleks devtoole, et astuda selle juurde ja vaadata kõnepinu.

  1. Käivitamise virn asetatakse factorial()argumendi möödudes tähega 5. Põhijuht on vale, seega sisestage rekursiivne tingimus.
  2. Käivitamise virn asetab factorial()teise korra num-1argumendina = 4. Põhijuht on vale, sisestage rekursiivne tingimus.
  3. Käivitamise virn asetab factorial()kolmanda korra num-1argumendiks (4–1) = 3. Põhijuht on vale, sisestage rekursiivne tingimus.
  4. Täitmisvirn asetab factorial()neljanda korra num-1argumendiks (3–1) = 2. Põhijuht on vale, sisestage rekursiivne tingimus.
  5. Käivitamise virn asetab factorial()viienda korra num-1argumendiks (2–1) = 1. Nüüd on alusjuht tõene, seega tagastage 1.

Siinkohal oleme vähendanud argumenti iga funktsioonikõne kohta ühe võrra, kuni jõuame 1-naasmise tingimuseni.

6. Siit lõpeb viimane käivitamise kontekst,, num === 1nii et funktsioon tagastab 1.

7. Järgmisena num === 2on tagastusväärtus 2. (1 × 2).

8. Järgmisena num === 3on tagastusväärtus 6, (2 × 3).

Siiani on meil 1 × 2 × 3.

9. Järgmine, num === 4(4 × 6). 24 on järgmise konteksti naaseväärtus.

10. Lõpuks, num === 5(5 × 24) ja meil on lõplik väärtus 120.

Rekursioon on päris korralik, eks?

Me oleksime võinud sama teha ühe või mitme aja jooksul. Kuid rekursiooni kasutamine annab elegantse lahenduse, mis on loetavam.

Seetõttu kasutame rekursiivseid lahendusi.

Mitu korda on väiksemateks osadeks jaotatud probleem tõhusam. Probleemi jagamine väiksemateks osadeks aitab seda vallutada. Seega on rekursioon probleemide lahendamisel jaga ja võida-lähenemine.

  • Alamprobleeme on lihtsam lahendada kui algseid probleeme
  • Algprobleemi lahendamiseks kombineeritakse alamprobleemide lahendusi

"Jaga ja võida" kasutatakse kõige sagedamini selliste andmestruktuuride nagu binaarotsingupuud, graafikud ja hunnikud läbimiseks või otsimiseks. See töötab ka paljude sorteerimisalgoritmide puhul, nagu quicksort ja heapsort.

Vaatame läbi järgmised näited. Kasutage devtoole, et saada kontseptuaalne ülevaade sellest, mis toimub kus ja millal. Ärge unustage kasutada silurilauseid ja astuda läbi igast protsessist.

Fibonacci

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

Rekursiivsed massiivid

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

Stringi tagurdamine

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

Kiire sort

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

Rekursiivsete võtete harjutamine on oluline. Pesastatud andmestruktuuride, nagu puud, graafikud ja hunnikud, korral on rekursioon hindamatu.

Järgmises artiklis käsitlen saba kõne optimeerimise ja memodeerimise tehnikaid, kuna need on seotud rekursiooniga. Täname lugemast!

Edasised ressursid

Vikipeedia

Tarkvaraarendus

Veel üks hea artikkel

MIT avatud kursusevara