A rekurzió az egy olyan módszer, amit fejlesztőként mindenképp az eszköztáradban kell tartanod.
Rekurzió alatt azt értjük, amikor egy adott probléma megoldására írt függvény úgy állítja össze a végeredményt, hogy saját magát hívja meg a részeredmények kiszámolásához.
Ezért a rekurzióval megoldható problémákra igaz, hogy rejlik bennük valami önhasonló mintázat, amit a megoldás során ki lehet használni.
Tegyük fel, hogy szeretnénk egy függvényt, amibe elég csak bedobni egy számot és az visszaadja ennek a számnak a faktoriálisát.
Például ha 5-öt dobunk bele akkor az 5 * 4 * 3 * 2 * 1-et tehát 120-at.
Ha belegondolsz ebben a feladatban a mintázat az az, hogy
A faktoriális(5) az egyenlő 5 * faktoriális(4)-gyel,
De egyenlő 5 * 4 * faktoriális(3)-mal is, és így tovább…
Tehát a részprobléma megoldásához ugyanazok a lépések szükségesek mint a teljes probléma megoldásához.
Egy rekurzív függvény implementációja során két dolgot kell csak megadnunk.
A rekurzív hívást, a részproblémára vonatkozó adattal és az úgynevezett base case-t magyarul alapesetet, ahol véget akarunk vetni a rekurziónak
Ha meghívjuk a függvényt 5-tel a következő történik:
A function elkezd futni és megkapja paraméterként az 5-ös számot.
Az 5 === 1 kifejezés false-ra értékelődik ki, így a rekurzív ágba jutunk.
Ebben az ágban a függvény meghívja önmagát és bepasszolja paraméterként a kapott számot - 1-et tehát 4-et.
A külső function ami ezt meghívta, annak a futása ekkor le van blokkolva, mert átadta a kontrollt ennek a függvénynek és egészen addig nem tudja folytatni a futást, amíg ennek a függvénynek a működése véget nem ért.
És mit csinál ez a függvény?
Miután ugyanaz a definíciója, mint annak ami meghívta, azt csinálja mint az előbb.
A különbség annyi, hogy ezúttal a részproblémára vonatkozó érték érkezett bemenetként.
Tehát kiértékeli a 4 === 1 kifejezést; ez false-ra értékelődik, aminek során ismét a rekurzív ágba jutunk.
Itt pedig meghívja önmagát, ezúttal hármat bedobva paraméterként.
És ez így folytatódik egészen addig, amíg el nem érjük a base case-t.
Ezen a ponton már 5 függvény várja, hogy visszatérhessen értékkel.
Láthatjuk, hogy a base case azért fontos, mert nélküle a rekurzív függvényhívások végtelenségig folytatódnának; illetve a gyakorlatban programunk hibát dobna a maximális call stack méret túllépésére hivatkozva.
A base case-ben futó kód visszaküld értéket, így a kontroll visszaadódik az őt meghívó function-nek.
Ebben a függvényben megtörténik a szorzás és visszatér egy részeredménnyel.
A függvények ehhez hasonlóan szolgáltatnak részeredményeket mindig az őket meghívó függvények, egészen addig amíg a legkülsőbb function is lefutott
Ekkor a kezünkbe kerül a végeredmény.
Tehát azért tudtuk használni a rekurziót faktoriális esetében, mert a problémában létezett egy beazonosító részprobléma, ami ugyanúgy volt megoldható, mint a teljes probléma.
Fejlesztőként leggyakrabban a fastruktúrák kapcsán találkozhatsz rekurzív függvényekkel.
A fa az egy olyan adatstruktúra, amivel elemek közötti hierarchikus viszonyt lehet reprezentálni.
A rekurzív jelleg abból adódik, hogy a fa egy gyökér elemből kiiduló node-ok sokaságából épül fel, amik között szülő-gyermek viszony van.
Bármelyik node-ot veszed alapul, az onnan induló kis fa, struktúráját tekintve ugyanúgy néz ki mint a teljes fa.
Ha egy ilyen struktúra minden elemét be akarod járni, akkor a base case-ed az, amikor az adott node-nak nincsen gyermekeleme.
A rekurzív hívás során pedig a gyermekelemkre kell lefuttatnod a függvényt.
Teljes videó:
Ajánlott cikk: A leghasznosabb tömbfüggvények