Rekurzia v Jave

1. Úvod

V tomto článku sa zameriame na základný koncept v akomkoľvek programovacom jazyku - rekurziu.

Vysvetlíme vlastnosti a rekurzívna funkcia a ukážeme, ako používať rekurziu na riešenie rôznych problémov v prostredí Java.

2. Pochopte rekurziu

2.1. Definícia

V Jave podporuje mechanizmus volania funkcie možnosť samotného volania metódy. Táto funkcia je známa ako rekurzia.

Predpokladajme napríklad, že chceme spočítať celé čísla od 0 do nejakej hodnoty n:

public int sum (int n) {if (n> = 1) {return sum (n - 1) + n; } návrat n; }

Rekurzívna funkcia má dve hlavné požiadavky:

  • Stav zastavenia - funkcia vráti hodnotu, keď je splnená určitá podmienka, bez ďalšieho rekurzívneho volania
  • Rekurzívne volanie - funkcia si hovorí pomocou vstup čo je o krok bližšie k stavu stop

Každé rekurzívne volanie pridá nový rámec do zásobníkovej pamäte JVM. Takže ak nebudeme venovať pozornosť tomu, ako hlboko sa môže naše rekurzívne volanie ponoriť, môže sa vyskytnúť výnimka z nedostatku pamäte.

Tento potenciálny problém je možné odvrátiť využitím optimalizácie chvostovej rekurzie.

2.2. Rekurzia chvosta versus rekurzia hlavy

Rekurzívnu funkciu označujeme ako chvost-rekurziakeď je rekurzívne volanie to posledné, čo funkcia vykoná. Inak je to známe ako rekurzia hlavy.

Naša implementácia nad rámec suma () funkcia je príkladom rekurzie hlavy a je možné ju zmeniť na rekurziu chvosta:

public int tailSum (int currentSum, int n) {if (n <= 1) {return currentSum + n; } návrat tailSum (currentSum + n, n - 1); }

S rekurziou chvosta, rekurzívne volanie je posledná vec, ktorú metóda robí, takže v rámci aktuálnej funkcie nezostáva nič, čo by sa dalo vykonať.

Logicky teda nie je potrebné ukladať rámec zásobníka aktuálnej funkcie.

Aj keď kompilátor môcť využiť tento bod na optimalizáciu pamäte, je potrebné poznamenať, že Kompilátor Java sa nateraz neoptimalizuje pre chvostovú rekurziu.

2.3. Rekurzia verzus iterácia

Rekurzia môže pomôcť zjednodušiť implementáciu niektorých komplikovaných problémov tým, že urobí kód jasnejším a čitateľnejším.

Ale ako sme už videli, rekurzívny prístup často vyžaduje viac pamäte, pretože požadovaná pamäť zásobníka sa zvyšuje s každým rekurzívnym volaním.

Alternatívne, ak môžeme vyriešiť problém s rekurziou, môžeme ho vyriešiť aj iteráciou.

Napríklad náš súčet metódu je možné implementovať pomocou iterácie:

public int iterativeSum (int n) {int sum = 0; if (n <0) {návrat -1; } for (int i = 0; i <= n; i ++) {sum + = i; } vratna suma; }

V porovnaní s rekurziou by iteračný prístup mohol potenciálne poskytnúť lepší výkon. Ako už bolo povedané, iterácia bude komplikovanejšia a ťažšie pochopiteľná v porovnaní s rekurziou, napríklad: prechod binárnym stromom.

Správna voľba medzi rekurziou hlavy, rekurziou chvosta a iteračným prístupom závisí od konkrétneho problému a situácie.

3. Príklady

Teraz sa pokúsime vyriešiť niektoré problémy rekurzívnym spôsobom.

3.1. Nájdenie N-tej sily desiatich

Predpokladajme, že musíme vypočítať n-th mocnina 10. Tu je náš vstup n. Keď premýšľame rekurzívnym spôsobom, môžeme vypočítať (n-1)- piata sila desiatich a výsledok sa vynásobí číslom 10.

Potom pre výpočet (n-1)-tou silou 10 bude (n-2)- desiata mocnina 10 a výsledok vynásobte 10 atď. Takto budeme pokračovať, až kým sa nedostaneme do bodu, kde budeme musieť vypočítať (n-n) -tu mocninu 10, čo je 1.

Ak by sme to chceli implementovať v Jave, napísali by sme:

public int powerOf10 (int n) {if (n == 0) {return 1; } návratnosť powerOf10 (n-1) * 10; }

3.2. Nájdenie N-tého prvku Fibonacciho sekvencie

Počnúc 0 a 1, the Fibonacciho postupnosť je postupnosť čísel, kde každé číslo je definované ako súčet dvoch čísel, ktoré za ním nasledujú: 0 1 1 2 3 5 8 13 21 34 55

Takže dané číslo n, naším problémom je nájsť n-tý prvok Fibonacciho postupnosť. Ak chcete implementovať rekurzívne riešenie, musíme prísť na to Stav zastavenia a Rekurzívne volanie.

Našťastie je to naozaj priame.

Zavoláme f (n) the n-tá hodnota sekvencie. Potom budeme mať f (n) = f (n-1) + f (n-2) (the Rekurzívne volanie).

Medzitým f (0) = 0 a f (1) = 1 ( Stav zastavenia).

Potom je pre nás skutočne zrejmé definovať rekurzívnu metódu riešenia problému:

public int fibonacci (int n) {if (n <= 1) {return n; } návrat fibonacci (n-1) + fibonacci (n-2); }

3.3. Prevod z desatinného na binárny

Uvažujme teraz o probléme prevodu desatinného čísla na binárne. Požiadavka je implementovať metódu, ktorá dostane kladné celé číslo n a vráti binárny súbor String zastúpenie.

Jedným z prístupov na prevod desatinného čísla na binárne je rozdelenie hodnoty o 2, zaznamenanie zvyšku a pokračovanie v delení kvocientu o 2.

Stále takto delíme, až kým nedostaneme kvocient 0. Potom vypísaním všetkých zvyškov v rezervnom poradí získame binárny reťazec.

Našim problémom je teda napísať metódu, ktorá vráti tieto zvyšky v rezervnom poradí:

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

3.4. Výška binárneho stromu

Výška binárneho stromu je definovaná ako počet hrán od koreňa po najhlbší list. Našim problémom teraz je vypočítať túto hodnotu pre daný binárny strom.

Jeden jednoduchý prístup by bol nájsť najhlbší list a potom počítať okraje medzi koreňom a listom.

Ale keď sa pokúsime myslieť na rekurzívne riešenie, môžeme preformulovať definíciu výšky binárneho stromu ako maximálnu výšku ľavej vetvy koreňa a pravej vetvy koreňa plus 1.

Ak koreň nemá ľavú a pravú vetvu, je jej výška nula.

Tu je naša implementácia:

public int countTreeHeight (BinaryNode root) {if (root! = null) {if (root.getLeft ()! = null || root.getRight ()! = null) {return 1 + max (CalcTreeHeight (root.left), vypočítaťTreeHeight (root.right)); }} vratit 0; }

Preto to vidíme niektoré problémy je možné vyriešiť pomocou rekurzie skutočne jednoduchým spôsobom.

4. Záver

V tomto tutoriáli sme predstavili koncept rekurzie v Jave a demonštrovali ho na niekoľkých jednoduchých príkladoch.

Implementáciu tohto článku nájdete na serveri Github.


$config[zx-auto] not found$config[zx-overlay] not found