streamalism.org

1. Bemutatkozás

Ebben a cikkben a programozási nyelv egyik alapkoncepciójára - a rekurzióra - fogunk koncentrálni.

Megmagyarázzuk az a jellemzőit rekurzív funkció és mutassa meg, hogyan lehet rekurziót használni a Java különböző problémáinak megoldására.

2. A rekurzió megértése

2.1. A meghatározás

Java-ban a function-call mechanizmus támogatja annak lehetősége, hogy maga hívjon metódust. Ez a funkcionalitás néven ismert rekurzió.

Tegyük fel például, hogy az egész számokat 0-ból szeretnénk összegezni valamilyen értékre n:

public int összeg (int n) {if (n> = 1) {visszatérési összeg (n - 1) + n; } return n; }

A rekurzív függvénynek két fő követelménye van:

• Stop feltétel - a függvény értéket ad vissza, ha egy bizonyos feltétel teljesül, további rekurzív hívás nélkül
• A rekurzív hívás - a függvény hívja magát egy bemenet ami egy lépéssel közelebb van a megállási feltételhez

Minden rekurzív hívás új keretet ad a JVM verem memóriájához. Így, ha nem figyelünk arra, hogy rekurzív hívásunk milyen mélyen merülhet el, memórián kívüli kivétel léphet fel.

Ez a lehetséges probléma elhárítható a farok-rekurzió optimalizálásának kihasználásával.

2.2. Farok rekurzió versus fej rekurzió

Rekurzív függvényre hivatkozunk farok-rekurzióamikor a rekurzív hívás az utolsó dolog, amelyet a funkció végrehajt. Egyébként úgy hívják fej-rekurzió.

Végrehajtásunk a összeg() függvény egy példa a fej rekurziójára, és farok rekurzióvá változtatható:

public int tailSum (int currentSum, int n) {if (n <= 1) {return currentSum + n; } visszatérő tailSum (currentSum + n, n - 1); }

Farok rekurzióval, a rekurzív hívás az utolsó dolog, amit a módszer elvégez, tehát az aktuális függvényen belül nincs mit végrehajtani.

Így logikusan nincs szükség az aktuális függvény veremkeretének tárolására.

Bár a fordító tud használja ezt a pontot a memória optimalizálásához, meg kell jegyezni, hogy a A Java fordító egyelőre nem optimalizálja a farokrekurziót.

2.3. Rekurzió versus iteráció

A rekurzió megkönnyítheti néhány bonyolult probléma végrehajtását azáltal, hogy világosabbá és olvashatóbbá teszi a kódot.

De amint már láthattuk, a rekurzív megközelítés gyakran több memóriát igényel, mivel a szükséges verem memória minden egyes rekurzív hívással növekszik.

Alternatív megoldásként, ha rekurzióval megoldhatunk egy problémát, akkor iterációval is megoldhatjuk.

Például a mi összeg módszer iterációval valósítható meg:

public int iterativeSum (int n) {int összeg = 0; if (n <0) {return -1; } for (int i = 0; i <= n; i ++) {összeg + = i; } visszatérési összeg; }

A rekurzióhoz képest az iteratív megközelítés potenciálisan jobb teljesítményt nyújthat. Ennek ellenére az iteráció bonyolultabb és nehezebben érthető a rekurzióhoz képest, például: bináris fán való áthaladás.

A fejrekurzió, a farokrekurzió és az iteratív megközelítés közötti helyes megválasztás az adott problémától és helyzettől függ.

3. Példák

Most próbáljunk meg néhány problémát rekurzív módon megoldani.

3.1. Az N-edik tízes hatvány megtalálása

Tegyük fel, hogy ki kell számolnunk a n-edik hatványa. Itt a bemenetünk n. Rekurzív módon gondolkodva kiszámíthatjuk (n-1)- először a 10-es hatványt, és szorozzuk meg az eredményt 10-gyel.

Ezután a (n-1)10-edik hatványa lesz a (n-2)- a 10-edik hatvány és ezt az eredményt megszorozzuk 10-gyel stb. Addig folytatjuk így, amíg el nem jutunk egy olyan pontig, ahol ki kell számolnunk a 10 (n-n) -edik hatványát, ami 1.

Ha ezt Java-ban szeretnénk megvalósítani, akkor ezt írjuk:

public int powerOf10 (int n) {if (n == 0) {return 1; } visszatérő teljesítményOf10 (n-1) * 10; }

3.2. A Fibonacci-szekvencia N-edik elemének megtalálása

Kezdve 0 és 1, a Fibonacci szekvencia olyan számsorozat, ahol minden számot az azt folytató két szám összegeként definiálunk: 0 1 1 2 3 5 8 13 21 34 55 …

Tehát adott egy szám n, a problémánk az, hogy megtaláljuk a nelemének Fibonacci szekvencia. Rekurzív megoldás megvalósításához ki kell találnunk a Stop feltétel és a Rekurzív hívás.

Szerencsére valóban egyszerű.

Hívjuk f (n) a na szekvencia negyedik értéke. Akkor meglesz f (n) = f (n-1) + f (n-2) (a Rekurzív hívás).

Közben, f (0) = 0 és f (1) = 1 ( Stop feltétel).

Aztán nagyon nyilvánvaló számunkra egy rekurzív módszer meghatározása a probléma megoldására:

public int fibonacci (int n) {if (n <= 1) {return n; } visszatér fibonacci (n-1) + fibonacci (n-2); }

3.3. Átalakítás decimálisról binárisra

Vizsgáljuk meg a tizedes szám binárisra konvertálásának problémáját. A követelmény egy olyan módszer megvalósítása, amely pozitív egész értéket kap n és bináris értéket ad vissza Húr reprezentáció.

A tizedes szám binárisra konvertálásának egyik megközelítése az, hogy az értéket elosztjuk 2-vel, feljegyezzük a maradékot, és tovább osztjuk a hányadost 2-vel.

Folyamatosan osztunk így, amíg meg nem kapjuk a hányadost 0. Ezután az összes maradék tartalék sorrendben való kiírásával megkapjuk a bináris karakterláncot.

Ezért a problémánk egy olyan módszer megírása, amely ezeket a maradékokat tartalék sorrendben adja vissza:

public String toBinary (int n) {if (n <= 1) {return String.valueOf (n); } return toBinary (n / 2) + String.valueOf (n% 2); }

3.4. Egy bináris fa magassága

A bináris fa magasságát a gyökértől a legmélyebb levélig terjedő élek számaként határozzuk meg. A problémánk most az, hogy kiszámoljuk ezt az értéket egy adott bináris fára.

Az egyik egyszerű megközelítés a legmélyebb levél megkeresése, majd a gyökér és a levél közötti élek számlálása.

De megpróbálva rekurzív megoldásra gondolni, megismételhetjük a bináris fa magasságának definícióját, mint a gyökér bal és a gyökér jobb ágának maximális magasságát, plusz 1.

Ha a gyökérnek nincs bal és jobb ága, akkor a magassága nulla.

Itt van a megvalósításunk:

public int calcTreeHeight (BinaryNode root) {if (root! = null) {if (root.getLeft ()! = null || root.getRight ()! = = null) {return 1 + max (calcTreeHeight (root.left), calcTreeHeight (root.jobb)); }} visszatér 0; }

Ezért látjuk ezt egyes problémák rekurzióval nagyon egyszerű módon megoldhatók.

4. Következtetés

Ebben az oktatóanyagban bemutattuk a rekurzió fogalmát a Java-ban, és néhány egyszerű példával bemutattuk.

A cikk megvalósítása a Github oldalon található.