Rekurzió

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