A rekurzió nem nehéz: ennek a hasznos programozási technikának a részletes bemutatása

Ezt rögtön le fogom mondani. Ismeri azokat az eseményeket, amelyek a függvényhíváskor történnek? Nem? Akkor ott kezdjük.

Funkcióhívás

Ha meghívunk egy függvényt, egy végrehajtási kontextus kerül a végrehajtási verembe. Bontsuk ezt még le.

Először is, mi a verem?

A verem egy olyan adatszerkezet, amely „Last In, First Out” alapon működik. Egy elemet „tolnak” egy veremre, hogy hozzá lehessen tenni, és egy elemet „kipattan” a veremből, hogy eltávolítsa azt.

A verem használata bizonyos műveletek végrehajtásra rendelésének módja.

Most visszatérünk arra, hogy mi a végrehajtási kontextus? A végrehajtási kontextus egy függvényhíváskor alakul ki. Ez a kontextus egy végrehajtási verembe, egy műveletsorrendbe helyezi magát. Az ebben a veremben mindig első elem a globális végrehajtási kontextus. Következnek a függvények által létrehozott összefüggések.

Ezek a végrehajtási kontextusok rendelkeznek tulajdonságokkal, egy aktiválási objektummal és egy „ez” összerendeléssel. Az „ez” összerendelés visszaemlékezés erre a végrehajtási környezetre. Az aktiválási objektum a következőket tartalmazza: átadott paraméterek, deklarált változók és függvénydeklarációk.

Tehát minden alkalommal, amikor új kontextust helyezünk el a veremben, általában minden megvan, ami a kód végrehajtásához szükséges.

Miért mondom általában ?

Rekurzióval más végrehajtási összefüggésekből származó visszatérési értékeket várunk. Ezek a többi kontextus magasabbak a veremben. Amikor a verem utolsó eleme befejezi a végrehajtást, az adott kontextus visszatérési értéket generál. Ez a visszatérési érték visszatérési értékként kerül átadásra a rekurzív esetből a következő elemre. Ez a végrehajtási kontextus ezután leugrik a veremről.

Rekurzió

Mi tehát a rekurzió?

A rekurzív függvény olyan funkció, amely addig hívja magát, amíg az „alapfeltétel” igaz, és a végrehajtás leáll.

Bár hamis, végrehajtási összefüggéseket helyezünk el a verem tetején. Ez addig történhet, amíg nem lesz „verem túlcsordulás”. A verem túlcsordulása az, amikor elfogy a memória, hogy elemeket tároljunk a veremben.

Általában egy rekurzív függvénynek legalább két része van: alapfeltétel és legalább egy rekurzív eset.

Nézzünk meg egy klasszikus példát.

Faktoriális

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

Itt próbálunk 5-öt találni! (öt tényező). A faktoriális függvény az összes pozitív egész szám szorzata, amely kisebb vagy egyenlő az argumentumával.

Az első feltétel kimondja: "ha a megadott paraméter értéke 0 vagy 1, akkor kilépünk és 1-et adunk vissza".

Ezután a rekurzív eset áll:

"Ha a paraméter nem 0 vagy 1, akkor átadjuk annak numa visszatérési értéknek a szorzatát, num-1amikor újra meghívjuk ezt a függvényt argumentumként".

Tehát, ha hívunk factorial(0), a függvény értéke 1, és soha nem éri el a rekurzív esetet.

Ugyanez vonatkozik a factorial(1).

Láthatjuk, mi történik, ha behelyezünk egy hibakereső utasítást a kódba, és a devtools segítségével lépünk rá, és figyeljük a hívásveremot.

  1. A végrehajtási verem factorial()5-szel kerül az argumentum átadásakor. Az alapeset hamis, ezért adja meg a rekurzív feltételt.
  2. A végrehajtási verem factorial()másodszor helyezi el num-1= 4 argumentummal. Az alap-eset hamis, adja meg a rekurzív feltételt.
  3. A végrehajtási verem factorial()harmadszor helyezi num-1el argumentumként a (4–1) = 3 értéket. Az alap-eset hamis, adja meg a rekurzív feltételt.
  4. A végrehajtási verem factorial()negyedik alkalommal helyezi num-1el argumentumként a (3–1) = 2 értéket. Az alap-eset hamis, adja meg a rekurzív feltételt.
  5. A végrehajtási verem factorial()egy ötödik időt helyez num-1el argumentumként (2–1) = 1 argumentummal. Most az alapeset igaz, ezért adja vissza az 1-et.

Ekkor minden függvényhíváson eggyel csökkentettük az argumentumot, amíg el nem érjük az 1-es visszatérés feltételét.

6. Innen az utolsó végrehajtási kontextus befejeződik num === 1, így a függvény 1-et ad vissza.

7. Ezután num === 2a visszatérési érték 2. (1 × 2).

8. Ezután a num === 3visszatérési érték 6, (2 × 3).

Eddig 1 × 2 × 3 van.

9. Ezután, num === 4(4 × 6). A 24. a következő kontextus visszatérési értéke.

10. Végül, num === 5(5 × 24), és a végső érték 120.

A rekurzió nagyon szép, igaz?

Megtehettük volna ugyanezt egy vagy egy darab hurokkal. De a rekurzió használata elegáns, olvashatóbb megoldást eredményez.

Ezért rekurzív megoldásokat alkalmazunk.

Sokszor a kisebb részekre bontott probléma hatékonyabb. A probléma kisebb részekre osztása elősegíti annak meghódítását. Ezért a rekurzió megosztani és meghódítani megközelítés a problémák megoldásában.

  • Sub-problems are easier to solve than the original problem
  • Solutions to sub-problems are combined to solve the original problem

“Divide-and-conquer” is most often used to traverse or search data structures such as binary search trees, graphs, and heaps. It also works for many sorting algorithms, like quicksort and heapsort.

Let’s work through the following examples. Use devtools to get a conceptual grasp of what’s happening where and when. Remember to use debugger statements and step though each process.

Fibonacci

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

Recursive arrays

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

Reversing a string

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

Practicing recursive techniques is important. For nested data structures like trees, graphs, and heaps, recursion is invaluable.

In a future article, I will discuss tail-call optimization and memoization techniques as they relate to recursion. Thanks for reading!

Further resources

Wikipedia

Software Engineering

Another good article

M.I.T. open courseware