"A rekurzió megértéséhez először meg kell értenünk a rekurziót."
A rekurzió nehezen érthető - különösen az új programozók számára. A legegyszerűbb formájában a rekurzív függvény az, amely önmagát hívja. Hadd próbáljam meg elmagyarázni egy példával.
Képzelje el, hogy kinyitja a hálószoba ajtaját, és bezárva van. Hároméves fiad beugrik a sarok mögül, és tudatja veled, hogy az egyetlen kulcsot egy dobozba rejtette. („Csakúgy, mint ő”, gondolja.) Késik a munkából, és valóban be kell lépnie a szobába, hogy megszerezze az ingét.
Csak akkor nyitja meg a dobozt, hogy további ... dobozokat találjon. Dobozok a dobozok belsejében. És nem tudod, melyiknél van a kulcs! Hamarosan meg kell szereznie azt az inget, ezért jó algoritmusra kell gondolnia a kulcs megtalálásához.
Két fő megközelítés létezik e probléma algoritmusának létrehozására: iteratív és rekurzív. Itt van mindkét megközelítés, mint folyamatábrák:
Melyik megközelítés tűnik könnyebbnek az Ön számára?
Az első megközelítés egy while ciklust használ. Amíg a halom nem üres, fogjon meg egy dobozt, és nézze át. Itt van néhány JavaScript ihletésű álkód, amely megmutatja, mi történik. (Az álkódot kódként írják, de inkább az emberi beszédhez hasonlít.)
function look_for_key(main_box) { let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) { box = pile.grab_a_box(); for (item in box) { if (item.is_a_box()) { pile.append(item) } else if (item.is_a_key()) { console.log("found the key!") } } }}A második út rekurziót használ. Ne feledje, hogy a rekurzió az, ahol a függvény önmagát hívja. Ez az álkód második módja.
function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } }Mindkét megközelítés ugyanazt valósítja meg. A rekurzív megközelítés alkalmazásának fő célja, hogy miután megértette, érthetőbbé válik az olvasása. A rekurzió használatának valójában nincs teljesítményelőnye. A ciklusokkal végzett iteratív megközelítés néha gyorsabb lehet. De főként a rekurzió egyszerűségét részesítik előnyben.
Továbbá, mivel sok algoritmus rekurziót használ, fontos megérteni a működését. Ha a rekurzió még mindig nem tűnik egyszerűnek számodra, ne aggódj: áttekintek még néhány példát.
Alap- és rekurzív eset
Valami, amire figyelned kell, amikor rekurzív függvényt írsz, egy végtelen ciklus. Ekkor a funkció folyamatosan hívja magát ... és soha nem hagyja abba magát!
Például érdemes felírni egy visszaszámláló függvényt. Rekurzívan így írhatta JavaScript-be:
// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1)} countdown(5); // This is the initial call to the function.
Ez a funkció örökké számolni fog. Ha véletlenül végtelen ciklussal futtat kódot, akkor a „Ctrl-C” megnyomásával megöli a szkriptet. (Vagy, ha néha olyan CodePent használ, mint én, akkor hozzá kell adnia a „? Turn_off_js = true” szót az URL végéhez.)
A rekurzív függvénynek mindig meg kell mondania, hogy mikor kell abbahagyni az ismétlést. A rekurzív függvénynek mindig két részből kell állnia: a rekurzív és az alapesetben. Rekurzív eset, amikor a függvény hívja magát. Az alapeset az, amikor a függvény leállítja önmagát. Ez megakadályozza a végtelen hurkokat.
Itt van ismét a visszaszámlálás függvény, egy alapesettel:
function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1); } } countdown(5); // This is the initial call to the function.
Lehet, hogy nem nyilvánvaló, hogy pontosan mi történik ebben a funkcióban. Végigmegyek, mi történik, ha meghívjuk a visszaszámláló függvényt, amely „5” betűvel megy.
Kezdjük azzal, hogy kinyomtatjuk az 5-ös számot console.log. Mivel öt nem kisebb vagy egyenlő nullával, az else utasításra térünk. Ott ismét meghívjuk a visszaszámláló függvényt a négyes számmal (5–1 = 4?).
Mi jelentkezzen száma 4. Ismét ia nem kevesebb, vagy egyenlő, mint nulla, így megyünk a else és call visszaszámlálás 3. Ez addig folytatódik, amíginulla. Amikor ez megtörténik, akkor jelentkezzen a szám nulla, majd ia kisebb vagy egyenlő nullával. Végül elérjük a return utasítást, és kibukkanunk a függvényből.
A Call Stack
A rekurzív funkciók úgynevezett „hívásköteget” használnak. Amikor egy program meghív egy funkciót, ez a függvény a hívásverem tetejére kerül. Ez hasonló egy halom könyvhöz. Egyenként ad hozzá dolgokat. Ezután, amikor készen áll arra, hogy levegyen valamit, mindig leveszi a felső elemet.
Megmutatom a hívásverem factorialműködését a funkcióval. factorial(5)5-ként van írva! és ez így van meghatározva: 5! = 5 * 4 * 3 * 2 * 1. Itt van egy rekurzív függvény a szám faktoriálisának kiszámításához:
function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } }Most nézzük meg, mi történik, ha felhívja fact(3)az ábrát. A szemléltető ábra bemutatja, hogyan változik a verem soronként. A verem legfelső mezője megmondja fact, hogy éppen milyen hívást kezdeményez .
Figyelje meg, hogy az egyes hívásoknak hogyan factvan saját példánya x. Ez nagyon fontos a rekurzió működéséhez. Nem férhet hozzá egy másik funkció másolatához x.
Megtalálta már a kulcsot?
Térjünk vissza röviden az eredeti példára, amely szerint beágyazott dobozokban kereshetünk egy kulcsot. Ne feledje, hogy az első módszer a ciklusokat használó iteratív volt. Ezzel a módszerrel készít egy halom mezőt a kereséshez, így mindig tudja, milyen dobozokban kell még keresnie.
De a rekurzív megközelítésben nincs halom. Honnan tudja algoritmusa, hogy mely mezőkre kell még néznie? A „doboz halom” el van mentve a veremben. Ez egy halom félig befejezett függvényhívás, mindegyiknek megvan a maga félig teljes listája az átnézendő dobozokról. A verem nyomon követi a dobozok halmát az Ön számára!
És a rekurziónak köszönhetően végre megtalálhatja a kulcsot és megszerezheti az ingét!
Megnézheti ezt az 5 perces videót is, amelyet a rekurzióról készítettem. Meg kell erősítenie ezeket a rekurziós koncepciókat.
Következtetés
Remélem, hogy ez a cikk több egyértelműséget hozott Önnek a rekurzióval kapcsolatban a programozás során. Ez a cikk a Manning Publications új videotanfolyamom tanulságán alapul, Algorithms in Motion címmel. A tanfolyam (és ez a cikk is) Adit Bhargava csodálatos Grokking Algorithms című könyvén alapul. Ő rajzolta ki a cikk összes szórakoztató illusztrációját.
Ha a könyvek segítségével tanulsz a legjobban, szerezd be a könyvet! Ha videók révén tanulsz a legjobban, fontold meg a tanfolyamom megvásárlását.
39% kedvezményt kap a tanfolyamomból a ' 39carnes ' kód használatával !
És végül, hogy valóban megérthesse a rekurziót, újra el kell olvasnia ezt a cikket. ?