Bevezetés
A rekurzió erőteljes programozási fogalom: lényege, hogy egy függvény önmagát hívja meg.
Elsőre kicsit nehéz lehet megérteni, de ha egyszer megérted az alapokat, értékes eszközzé válik az összetett problémák megoldásában.
Ebben az útmutatóban könnyen érthető példákon keresztül fedezzük fel a rekurziót JavaScriptben.
Mi a rekurzió?
Rekurzióról akkor beszélünk, amikor egy függvény önmagát hívja meg, közvetlenül vagy közvetve.
Hasonlít egy ciklushoz, de itt egy problémát kisebb, könnyebben kezelhető részproblémákra bontunk.
1. példa: Visszaszámlálás
Kezdjük egy egyszerű példával: egy visszaszámláló függvénnyel.
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
Ebben a példában:
-
Alapeset: Amikor a
num értéke 0 vagy annál kisebb lesz, a függvény kiírja, hogy „Blastoff!”, és nem hívja meg többé önmagát.
-
Rekurzív eset: A függvény kiírja az aktuális
num értékét, majd meghívja önmagát num - 1 értékkel.
2. példa: Faktoriális
Most nézzünk egy klasszikus rekurziós példát: egy szám faktoriálisának kiszámítását.
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
Ebben a példában:
-
Alapeset: Amikor az
n értéke 0 vagy 1, a függvény 1-et ad vissza.
-
Rekurzív eset: A függvény megszorozza
n-t az n - 1 faktoriálisával.
Kulcsfogalmak
Alapeset
Minden rekurzív függvénynek kell legalább egy alapesete: egy feltétel, amelynél a függvény leáll, és nem hívja meg többé önmagát.
Alapeset nélkül a rekurzió a végtelenségig folytatódna, ami veremtúlcsorduláshoz vezet.
Rekurzív eset
A rekurzív eset határozza meg, hogyan hívja meg a függvény önmagát a probléma kisebb vagy egyszerűbb változatával.
A rekurzió előnyei és hátrányai
Előnyök:
- Elegáns megoldás bizonyos problémákra.
- A matematikai indukció elvét tükrözi.
Hátrányok:
- Kevésbé lehet hatékony, mint az iteratív megoldások.
- Mély rekurziónál veremtúlcsorduláshoz vezethet.
Összegzés
A rekurzió értékes technika, amely leegyszerűsítheti az összetett problémákat azzal, hogy kisebb, könnyebben kezelhető részproblémákra bontja őket.
Az alapesetek és a rekurzív esetek megértése elengedhetetlen ahhoz, hogy hatékony rekurzív megoldásokat írj JavaScriptben.
Tudj meg többet:
Utasítások
Pizzériát vezetsz, és háromféle pizzát kínálsz:
- Margherita: $7
- Caprese: $9
- Formaggio: $10
Ha a vendégek kérik, korlátlan számú extra feltétet adhatnak hozzá: vagy „ExtraSauce”-ot 1 dollárért, vagy „ExtraToppings”-ot 2 dollárért.
A feladatod, hogy olyan kódot írj, amely segít a vásárlónak kiszámolni, mennyibe kerül neki a pizza.
Számítsd ki egy pizza árát
Az első argumentum a pizza neve, ezt korlátlan számú extra feltét követi. Számítsd ki a pizza árát dollárban.
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
Számítsd ki egy rendelés teljes árát
A függvényedet egy PizzaOrder-okból álló listával hívják meg, és vissza kell adnia a rendelés teljes árát dollárban.
Minden PizzaOrder-nak van egy pizza tulajdonsága, ami a pizza neve, és egy extras tulajdonsága, ami az extra feltétek listája.
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
Rá fogsz jönni, hogy ezt nem tudod rekurzióval megírni, mert egy olyan teszt, amelyben rengeteg rendelés van, Maximum call stack size exceeded hibát dob.
Ne aggódj, ez szándékos: próbáld meg ezt a függvényt imperatív ciklussal megvalósítani!
Sok lehetőség közül választhatsz, például használhatod a reduce-ot vagy egy for ciklust, de nem kizárólag ezeket.
Amikor a JavaScript-értelmező futtatja a JavaScript-kódot, nyilván tartja egy „verem” nevű adatszerkezeten, hogy mely függvényekbe lépett be (kezdte el meghívni).
Amikor a függvény visszatér (véget ér), lekerül a veremről.
A verem mérete azonban korlátozott.
A leggyakoribb hiba egy soha véget nem érő rekurzív függvény.
Minden hívás felkerül a veremre, de mielőtt visszatérne, egy újabb hívás kerül a veremre.
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
A hiba veremnyomában ugyanaz a sor ismétlődik újra meg újra, ami logikus, hiszen a függvény önmagát hívja.
Bár a legtöbb esetben nincs igazi gyakorlati haszna, megtudhatod, milyen mélyre nőhet ez a verem.
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
Egy szinkron rekurzív függvény okozta hívási verem hibájára csak két járható megoldás van:
- gondoskodj róla, hogy a függvények a verem korlátjának elérése előtt visszatérjenek, általában egy báziseset hozzáadásával vagy javításával.
- írd át a rekurzív függvényt imperatív ciklussá, amely a ciklus törzsét hajtja végre anélkül, hogy belépne egy függvénybe, és így nem növeli a vermet.
Tanulófeladat
