Tento podrobný výukový program o rekurzii v jazyku Java vysvetľuje, čo je rekurzia s príkladmi, typmi a súvisiacimi pojmami. Zahŕňa aj rekurziu a iteráciu:
V predchádzajúcich učebniciach jazyka Java sme sa oboznámili s iteračným prístupom, v ktorom deklarujeme cyklus a potom iteračne prechádzame dátovou štruktúrou tak, že berieme jeden prvok za druhým.
Videli sme aj podmienený tok, kde opäť udržiavame jednu premennú cyklu a opakujeme časť kódu, kým premenná cyklu nesplní podmienku. Pokiaľ ide o volanie funkcií, skúmali sme iteračný prístup aj pre volanie funkcií.
V tomto učebnom texte sa budeme venovať inému prístupu k programovaniu, t. j. rekurzívnemu prístupu.
Čo je rekurzia v jazyku Java?
Rekurzia je proces, pri ktorom funkcia alebo metóda volá samu seba znova a znova. Táto funkcia, ktorá sa volá znova a znova buď priamo, alebo nepriamo, sa nazýva "rekurzívna funkcia".
Ukážeme si rôzne príklady na pochopenie rekurzie. Teraz si ukážeme syntax rekurzie.
Syntax rekurzie
Každá metóda, ktorá implementuje rekurziu, má dve základné časti:
- Volanie metódy, ktorá môže volať sama seba, t. j. rekurzívne
- Predpoklad, ktorý zastaví rekurziu.
Všimnite si, že prekurzívna podmienka je nevyhnutná pre každú rekurzívnu metódu, pretože ak rekurziu neprerušíme, bude prebiehať donekonečna a povedie k pretečeniu zásobníka.
Všeobecná syntax rekurzie je nasledovná:
methodName (T parameters...) { if (precondition == true) //precondition alebo base condition { return result; } return methodName (T parameters...); //rekurzívne volanie } Všimnite si, že základná podmienka sa nazýva aj bázická podmienka. O bázickej podmienke si povieme viac v nasledujúcej časti.
Pochopenie rekurzie v jazyku Java
V tejto časti sa pokúsime pochopiť proces rekurzie a uvidíme, ako prebieha. Dozvieme sa o základnej podmienke, pretečení zásobníka, uvidíme, ako sa dá konkrétny problém vyriešiť pomocou rekurzie a ďalšie podobné detaily.
Základná podmienka rekurzie
Pri písaní rekurzívneho programu by sme mali najprv uviesť riešenie pre základný prípad. Potom väčší problém vyjadríme pomocou menších problémov.
Ako príklad, môžeme vziať klasický problém výpočtu faktoriálu čísla. Pri danom čísle n musíme nájsť faktoriál čísla n označený n!
Teraz implementujme program na výpočet n-násobku (n!) pomocou rekurzie.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Výstup
V tomto programe vidíme, že podmienka (n<=1) je základná podmienka a po jej splnení funkcia vráti 1. Časť else funkcie je rekurzívne volanie. Pri každom volaní rekurzívnej metódy sa však n zmenší o 1.
Môžeme teda konštatovať, že nakoniec hodnota n bude 1 alebo menšia ako 1 a v tomto okamihu metóda vráti hodnotu 1. Táto základná podmienka bude dosiahnutá a funkcia sa zastaví. Všimnite si, že hodnota n môže byť akákoľvek, pokiaľ spĺňa základnú podmienku.
Riešenie problémov pomocou rekurzie
Základnou myšlienkou použitia rekurzie je vyjadriť väčší problém pomocou menších problémov. Taktiež musíme pridať jednu alebo viac základných podmienok, aby sme mohli z rekurzie vyjsť.
To sme si už ukázali v predchádzajúcom príklade s faktoriálom. V tomto programe sme vyjadrili n faktoriál (n!) v podobe menších hodnôt a mali sme základnú podmienku (n <=1), takže keď n dosiahne hodnotu 1, môžeme rekurzívnu metódu ukončiť.
Chyba Stack Overflow v rekurzii
Vieme, že pri volaní ľubovoľnej metódy alebo funkcie sa stav funkcie ukladá na zásobník a získava sa pri návrate funkcie. Zásobník sa používa aj pri rekurzívnej metóde.
V prípade rekurzie však môže nastať problém, ak nedefinujeme základnú podmienku alebo ak sa základná podmienka nejakým spôsobom nedosiahne alebo nevykoná. Ak nastane takáto situácia, môže vzniknúť pretečenie zásobníka.
Pozrime sa na nasledujúci príklad faktoriálneho zápisu.
Tu sme uviedli nesprávnu základnú podmienku, n==100.
public class Main { static int fact(int n) { if (n == 100) // základná podmienka vedúca k pretečeniu zásobníka return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } Takže keď n> 100, metóda vráti 1, ale rekurzia sa nezastaví. Hodnota n sa bude dekrementovať donekonečna, pretože neexistuje žiadna iná podmienka, ktorá by ju zastavila. Toto bude pokračovať, kým sa zásobník nepreplní.
Ďalším prípadom bude, keď hodnota n <100. Aj v tomto prípade metóda nikdy nevykoná základnú podmienku a dôjde k pretečeniu zásobníka.
Príklady rekurzie v jazyku Java
V tejto časti budeme implementovať nasledujúce príklady pomocou rekurzie.
#1) Fibonacciho rad pomocou rekurzie
Fibonacciho rad je daný,
1,1,2,3,5,8,13,21,34,55,…
Z uvedenej postupnosti vyplýva, že aktuálny prvok je súčtom predchádzajúcich dvoch prvkov. Aj prvý prvok Fibonacciho radu je 1.
Takže vo všeobecnosti, ak n je aktuálne číslo, potom je dané súčtom (n-1) a (n-2). Keďže aktuálny prvok je vyjadrený pomocou predchádzajúcich prvkov, môžeme tento problém vyjadriť pomocou rekurzie.
Program na implementáciu Fibonacciho radu je uvedený nižšie:
public class Main { //metóda na výpočet fibonacciho radu static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int number = 10; //vypíšeme prvých 10 čísel fibonacciho radu System.out.println ("Fibonacciho rad: Prvých 10 čísel:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Výstup
#2) Kontrola, či je číslo palindróm pomocou rekurzie
Palindróm je postupnosť, ktorá je rovnaká, keď ju čítame zľava doprava alebo sprava doľava.
Ak máme dané číslo 121, vidíme, že keď ho čítame zľava doprava a sprava doľava, je rovnaké. Číslo 121 je teda palindróm.
Vezmime si iné číslo, 1242. Keď ho čítame zľava doprava, je to 1242 a keď ho čítame sprava doľava, číta sa ako 2421. Nejde teda o palindróm.
Program palindrómu implementujeme tak, že obrátime číslice čísel a rekurzívne porovnáme dané číslo s jeho obrátenou reprezentáciou.
Nižšie uvedený program implementuje program na kontrolu palindrómu.
import java.io.*; import java.util.*; public class Main { // kontrola, či num obsahuje len jednu číslicu public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // základná podmienka; return if num=0 if (num == 0) { return revNum; } else { //callutilitárna funkcia rekurzívne revNum = isPalindrome_util(num / 10, revNum); } // skontrolujte, či sa prvá číslica num a revNum rovná if (num % 10 == revNum % 10) { // ak áno, revNum sa posunie spolu s num return revNum / 10; } else { // exit throw new Exception(); } } //metóda na kontrolu, či je dané číslo palindrom pomocou palindromovej utilitárnej funkcie public static int isPalindrome(int num) throwsException { if (num <0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Áno, dané číslo " + n + " je palindróm."); } catch (Exception e) { System.out.println("Nie, dané číslo " + n + " nie je palindróm."); } n = 1221; try { isPalindrome(n);System.out.println("Áno, dané číslo " + n + " je palindróm."); } catch (Výnimka e) { System.out.println("Nie, dané číslo " + n + " nie je palindróm."); } } } } Výstup
#3) Reverzná rekurzia reťazca Java
Pri danom reťazci "Hello" ho musíme obrátiť tak, aby výsledný reťazec bol "olleH".
Toto sa vykonáva pomocou rekurzie. Počnúc posledným znakom v reťazci rekurzívne vypíšeme každý znak, kým sa nevyčerpajú všetky znaky v reťazci.
Nasledujúci program používa rekurziu na reverziu daného reťazca.
class String_Reverse { //rekurzívna metóda na reverziu daného reťazca void reverseString(String str) { //základná podmienka; return ak je reťazec null alebo s 1 alebo menej znakmi if ((str==null)} } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Zadaný reťazec: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Obrátený reťazec: "); obj.reverseString(inputstr); } } } Výstup
#4) Binárne vyhľadávanie Java Rekurzia
Binárny vyhľadávací algoritmus je známy algoritmus na vyhľadávanie. V tomto algoritme, ak je dané zoradené pole s n prvkami, hľadáme v tomto poli daný kľúčový prvok. Na začiatku rozdelíme pole na dve polovice tak, že nájdeme stredný prvok poľa.
Potom v závislosti od toho, či je kľúč v polovici, obmedzíme vyhľadávanie v prvej alebo druhej polovici poľa. Takto sa rovnaký postup opakuje, kým sa nenájde umiestnenie kľúčových prvkov.
Tento algoritmus tu implementujeme pomocou rekurzie.
import java.util.*; class Binary_Search { // rekurzívne binárne vyhľadávanie int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //vypočítaj stred poľa int mid = left + (right - left) / 2; // ak je kľúč v strede, vráť mid if (numArray[mid] == key) return mid; // ak kľúč key) return binarySearch(numArray, left, mid - 1, key); // Inak rekurzívne vyhľadávanie vpravé podmnožina return binarySearch(numArray, mid + 1, right, key); } // v poli nie sú žiadne prvky, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //vyhlásenie a výpis poľa int numArray[] = { 4,6,12,16,22}; System.out.println("Dané pole : " + Arrays.toString(numArray)); int len = numArray.length; //dĺžka poľaint key = 16; //key to be search int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " not present"); else System.out.println("Element " + key + " found at index " + result); } } Výstup
#5) Nájsť minimálnu hodnotu v poli pomocou rekurzie
Pomocou rekurzie môžeme nájsť aj minimálnu hodnotu v poli.
Program v jazyku Java na zistenie minimálnej hodnoty v poli je uvedený nižšie.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //vráti prvý prvok, ak je v poli len jeden prvok alebo minimum prvkov return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Dané pole : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Minimálny prvok poľa: " + getMin(numArray, 0, n) + "\n"); } } Výstup
Toto sú niektoré z príkladov rekurzie. Okrem týchto príkladov možno pomocou rekurzívnych techník implementovať aj množstvo ďalších problémov v softvéri.
Typy rekurzie
Rekurzia je dvojakého typu podľa toho, kedy sa volá rekurzívna metóda.
Sú to:
#1) Rekurzia na chvoste
Ak je volanie rekurzívnej metódy posledným príkazom vykonaným vo vnútri rekurzívnej metódy, nazýva sa to "Tail Recursion".
Pri chvostovej rekurzii sa príkaz rekurzívneho volania zvyčajne vykonáva spolu s príkazom návratu metódy.
Všeobecná syntax pre chvostovú rekurziu je uvedená nižšie:
methodName ( T parameters...){ { if (base_condition == true) { return result; } return methodName (T parameters ...) //tail recursion } #2) Rekurzia hlavy
Hlavná rekurzia je akýkoľvek rekurzívny prístup, ktorý nie je chvostovou rekurziou. Takže aj všeobecná rekurzia je rekurziou dopredu.
Syntax rekurzie hlavy je nasledujúca:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Rekurzia a iterácia v jazyku Java
| Rekurzia | Iterácia |
|---|---|
| Rekurzia je proces, pri ktorom sa metóda opakovane volá, kým nie je splnená základná podmienka. | Iterácia je proces, pri ktorom sa časť kódu opakovane vykonáva určitý početkrát alebo kým sa nesplní určitá podmienka. |
| Je aplikácia pre funkcie. | Platí pre slučky. |
| Funguje dobre pre menšiu veľkosť kódu. | Funguje dobre pri väčšej veľkosti kódu. |
| Využíva viac pamäte, pretože každé rekurzívne volanie sa presúva na zásobník | Využíva sa relatívne menej pamäte. |
| Náročné na ladenie a údržbu | Jednoduchšie ladenie a údržba |
| Výsledkom je pretečenie zásobníka, ak nie je zadaná základná podmienka alebo nie je dosiahnutá. | Môže sa vykonávať donekonečna, ale nakoniec sa zastaví pri akejkoľvek chybe v pamäti |
| Časová náročnosť je veľmi vysoká. | Časová náročnosť je relatívne nižšia. |
Často kladené otázky
Otázka č. 1) Ako funguje rekurzia v jazyku Java?
Odpoveď: Pri rekurzii sa rekurzívna funkcia volá opakovane, kým nie je splnená základná podmienka. Pamäť pre volanú funkciu sa presúva na zásobník na vrchol pamäte pre volajúcu funkciu. Pre každé volanie funkcie sa vytvára samostatná kópia lokálnych premenných.
Q #2) Prečo sa používa rekurzia?
Odpoveď: Rekurzia sa používa na riešenie tých problémov, ktoré sa dajú rozdeliť na menšie a celý problém sa dá vyjadriť pomocou menšieho problému.
Rekurzia sa používa aj pri tých problémoch, ktoré sú príliš zložité na to, aby sa dali vyriešiť pomocou iteračného prístupu. Okrem problémov, pri ktorých časová zložitosť nie je problém, používajte aj rekurziu.
Q #3) Aké sú výhody rekurzie?
Odpoveď:
Medzi výhody rekurzie patria:
- Rekurzia redukuje nadbytočné volanie funkcie.
- Rekurzia nám v porovnaní s iteračným prístupom umožňuje jednoduchšie riešenie problémov.
Otázka č. 4) Ktorý z nich je lepší - rekurzia alebo iterácia?
Odpoveď: Rekurzia vykonáva opakované volania, až kým sa nedosiahne základná funkcia. Dochádza teda k pamäťovej réžii, pretože pamäť pre každé volanie funkcie sa presúva na zásobník.
Iterácia na druhej strane nemá veľkú pamäťovú réžiu. Vykonávanie rekurzie je pomalšie ako iteračný prístup. Rekurzia zmenšuje veľkosť kódu, zatiaľ čo iteračný prístup spôsobuje, že kód je veľký.
Q #5) Aké sú výhody rekurzie oproti iterácii?
Odpoveď:
- Rekurzia robí kód prehľadnejším a kratším.
- Rekurzia je lepšia ako iteračný prístup pri problémoch, ako je Hanojská veža, prechádzanie stromov atď.
- Keďže pri každom volaní funkcie sa na zásobník presúva pamäť, rekurzia využíva viac pamäte.
- Výkonnosť rekurzie je pomalšia ako pri iteračnom prístupe.
Záver
Rekurzia je veľmi dôležitý koncept v softvéri bez ohľadu na programovací jazyk. Rekurzia sa väčšinou používa pri riešení problémov dátových štruktúr, ako sú Hanojské veže, prechádzanie stromov, prepojené zoznamy atď. Hoci zaberá viac pamäte, rekurzia zjednodušuje a sprehľadňuje kód.
V tomto učebnom texte sme preskúmali všetko o rekurzii. Implementovali sme aj množstvo príkladov programovania pre lepšie pochopenie tohto konceptu.