Tento podrobný výukový kurz o rekurzi v jazyce Java vysvětluje, co je to rekurze s příklady, typy a souvisejícími pojmy. Zahrnuje také rekurzi a iteraci:
V dřívějších výukových lekcích Javy jsme se seznámili s iterativním přístupem, kdy deklarujeme smyčku a poté iterativně procházíme datovou strukturu tak, že bereme jeden prvek po druhém.
Viděli jsme také podmíněný tok, kdy opět udržujeme jednu proměnnou smyčky a opakujeme kus kódu, dokud proměnná smyčky nesplní podmínku. Pokud jde o volání funkcí, prozkoumali jsme iterativní přístup i pro volání funkcí.
V tomto tutoriálu se budeme zabývat jiným přístupem k programování, a to rekurzivním přístupem.
Co je rekurze v jazyce Java?
Rekurze je proces, při kterém funkce nebo metoda volá sama sebe znovu a znovu. Tato funkce, která je volána znovu a znovu buď přímo, nebo nepřímo, se nazývá "rekurzivní funkce".
Ukážeme si různé příklady pro pochopení rekurze. Nyní se podíváme na syntaxi rekurze.
Syntaxe rekurze
Každá metoda implementující rekurzi má dvě základní části:
- Volání metody, která může volat sama sebe, tj. rekurzivní volání
- Předpoklad, který zastaví rekurzi.
Všimněte si, že předběžná podmínka je nezbytná pro každou rekurzivní metodu, protože pokud rekurzi nepřerušíme, bude probíhat donekonečna a dojde k přetečení zásobníku.
Obecná syntaxe rekurze je následující:
methodName (T parameters...) { if (precondition == true) //předpoklad nebo základní podmínka { return result; } return methodName (T parameters...); //rekurzivní volání } Všimněte si, že předběžná podmínka se také nazývá základní podmínka. O základní podmínce si řekneme více v následující části.
Porozumění rekurzi v jazyce Java
V této části se pokusíme pochopit proces rekurze a zjistit, jak probíhá. Seznámíme se s bázovou podmínkou, přetečením zásobníku, podíváme se, jak lze konkrétní problém řešit pomocí rekurze a další podobné detaily.
Základní podmínka rekurze
Při psaní rekurzivního programu bychom měli nejprve uvést řešení pro základní případ. Poté vyjádříme větší problém v podobě menších problémů.
Jako příklad, můžeme vzít klasický problém výpočtu faktoriálu čísla. Je dáno číslo n, máme najít faktoriál čísla n označený n!
Nyní implementujme program pro výpočet n faktoriálu (n!) pomocí rekurze.
public class Main{ static int fact(int n) { if (n == 1) // základní podmínka 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 programu vidíme, že podmínka (n<=1) je základní podmínkou a při jejím splnění funkce vrátí 1. Část else funkce je rekurzivní volání. Při každém volání rekurzivní metody se však n zmenší o 1.
Můžeme tedy usoudit, že nakonec hodnota n bude 1 nebo menší než 1 a v tomto okamžiku metoda vrátí hodnotu 1. Této základní podmínky bude dosaženo a funkce se zastaví. Všimněte si, že hodnota n může být jakákoli, pokud splňuje základní podmínku.
Řešení problémů pomocí rekurze
Základní myšlenkou použití rekurze je vyjádřit větší problém pomocí menších problémů. Také musíme přidat jednu nebo více základních podmínek, abychom mohli z rekurze vyjít.
To jsme si již ukázali ve výše uvedeném příkladu s faktoriálem. V tomto programu jsme vyjádřili faktoriál n (n!) v menších hodnotách a měli jsme základní podmínku (n <=1), takže když n dosáhne 1, můžeme rekurzivní metodu ukončit.
Chyba přetečení zásobníku při rekurzi
Víme, že při volání jakékoliv metody nebo funkce je její stav uložen na zásobníku a při návratu funkce se z něj načítá. Zásobník se používá i pro rekurzivní metody.
V případě rekurze však může nastat problém, pokud nedefinujeme základní podmínku nebo pokud se základní podmínka nějakým způsobem nedosáhne nebo neprovede. Pokud tato situace nastane, může dojít k přetečení zásobníku.
Uvažujme následující příklad faktoriálního zápisu.
Zde jsme uvedli špatnou základní podmínku, n==100.
public class Main { static int fact(int n) { if (n == 100) // základní podmínka, která vede k přetečení zásobníku 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 když n> 100, metoda vrátí 1, ale rekurze se nezastaví. Hodnota n se bude donekonečna zmenšovat, protože neexistuje žádná jiná podmínka, která by ji zastavila. To bude pokračovat, dokud zásobník nepřetéká.
Dalším případem bude situace, kdy hodnota n <100. Ani v tomto případě metoda nikdy neprovede základní podmínku a dojde k přetečení zásobníku.
Příklady rekurze v jazyce Java
V této části budeme implementovat následující příklady pomocí rekurze.
#1) Fibonacciho řada pomocí rekurze
Fibonacciho řada je dána vztahem,
1,1,2,3,5,8,13,21,34,55,…
Z výše uvedené posloupnosti vyplývá, že aktuální prvek je součtem předchozích dvou prvků. Také první prvek Fibonacciho řady je 1.
Obecně tedy platí, že pokud je n aktuální číslo, pak je dáno součtem (n-1) a (n-2). Protože aktuální prvek je vyjádřen pomocí předchozích prvků, můžeme tento problém vyjádřit pomocí rekurze.
Program pro implementaci Fibonacciho řady je uveden níže:
public class Main { //metoda pro výpočet fibonacciho řady 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; //výpis prvních 10 čísel fibonacciho řady System.out.println ("Fibonacciho řada: Prvních 10 čísel:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Výstup
#2) Zkontrolujte, zda je číslo palindrom pomocí rekurze
Palindrom je posloupnost, která je stejná, čteme-li ji zleva doprava nebo zprava doleva.
Dáme-li číslo 121, vidíme, že když ho čteme zleva doprava a zprava doleva, je stejné. Číslo 121 je tedy palindrom.
Vezměme si jiné číslo, 1242. Když ho čteme zleva doprava, je to 1242, a když ho čteme zprava doleva, čte se jako 2421. Nejedná se tedy o palindrom.
Program palindromu implementujeme tak, že převrátíme číslice čísel a rekurzivně porovnáme dané číslo s jeho převrácenou reprezentací.
Níže uvedený program implementuje program pro kontrolu palindromu.
import java.io.*; import java.util.*; public class Main { // kontrola, zda num obsahuje pouze jednu číslici 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í podmínka; return if num=0 if (num == 0) { return revNum; } else { //callutilitní funkce rekurzivně revNum = isPalindrome_util(num / 10, revNum); } // Zkontrolujte, zda se první číslice num a revNum rovnají if (num % 10 == revNum % 10) { // pokud ano, revNum se posune s num return revNum / 10; } else { // exit throw new Exception(); } } //metoda pro kontrolu, zda je dané číslo palindrom pomocí palindrom utilitní funkce 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("Ano, dané číslo " + n + " je palindrom."); } catch (Exception e) { System.out.println("Ne, dané číslo " + n + " není palindrom."); } n = 1221; try { isPalindrome(n);System.out.println("Ano, dané číslo " + n + " je palindrom."); } catch (Výjimka e) { System.out.println("Ne, dané číslo " + n + " není palindrom."); } } } }. Výstup
#3) Reverzní řetězcová rekurze Java
Při zadání řetězce "Hello" jej musíme obrátit tak, aby výsledný řetězec byl "olleH".
To se provádí pomocí rekurze. Počínaje posledním znakem v řetězci rekurzivně vypisujeme každý znak, dokud nejsou všechny znaky v řetězci vyčerpány.
Níže uvedený program používá rekurzi k obrácení zadaného řetězce.
class String_Reverse { //rekurzivní metoda pro obrácení zadaného řetězce void reverseString(String str) { //základní podmínka; vrátí, pokud je řetězec null nebo má 1 nebo méně znaků if ((str==null)} } } třída Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Zadaný řetězec: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Obrácený řetězec: "); obj.reverseString(inputstr); } } } Výstup
#4) Binární vyhledávání Java rekurze
Binární vyhledávací algoritmus je známým algoritmem pro vyhledávání. V tomto algoritmu je dáno setříděné pole o n prvcích a v tomto poli hledáme daný klíčový prvek. Na začátku rozdělíme pole na dvě poloviny tak, že najdeme prostřední prvek pole.
Poté podle toho, zda je klíč uprostřed, omezíme hledání v první nebo druhé polovině pole. Tímto způsobem se stejný postup opakuje, dokud není nalezeno umístění klíčových prvků.
Tento algoritmus zde implementujeme pomocí rekurze.
import java.util.*; class Binary_Search { // rekurzivní binární vyhledávání int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //vypočítáme střed pole int mid = left + (right - left) / 2; // pokud je klíč v mid, vrátíme mid if (numArray[mid] == key) return mid; // pokud key key) return binarySearch(numArray, left, mid - 1, key); // Jinak rekurzivně vyhledáváme veright subarray return binarySearch(numArray, mid + 1, right, key); } // v poli nejsou žádné prvky, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //prohlášení a vypsání pole int numArray[] = { 4,6,12,16,22}; System.out.println("Dané pole : " + Arrays.toString(numArray)); int len = numArray.length; //délka poleint 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) Nalezení minimální hodnoty v poli pomocí rekurze
Pomocí rekurze můžeme také najít minimální hodnotu v poli.
Program v jazyce Java pro zjištění minimální hodnoty v poli je uveden níže.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //vrátí první prvek, pokud je v poli jen jeden prvek nebo minimum prvků 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("Zadané pole : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Minimální prvek pole: " + getMin(numArray, 0, n) + "\n"); } } Výstup
To jsou některé z příkladů rekurze. Kromě těchto příkladů lze pomocí rekurzivních technik realizovat mnoho dalších problémů v softwaru.
Typy rekurze
Rekurze se dělí na dva typy podle toho, kdy je rekurzivní metoda volána.
Jsou to:
#1) Rekurze na ocase
Pokud je volání rekurzivní metody posledním příkazem provedeným uvnitř rekurzivní metody, nazývá se "rekurze na konci".
Při rekurzi na chvostu se příkaz rekurzivního volání obvykle provádí společně s návratovým příkazem metody.
Obecná syntaxe pro rekurzi na chvostu je uvedena níže:
methodName ( T parameters...){ { if (base_condition == true) { return result; } return methodName (T parameters ...) //tail recursion } #2) Rekurze hlavy
Přední rekurze je jakýkoli rekurzivní přístup, který není zadní rekurzí. Takže i obecná rekurze je přední rekurze.
Syntaxe rekurze hlavy je následující:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Rekurze a iterace v jazyce Java
| Rekurze | Iterace |
|---|---|
| Rekurze je proces, při kterém metoda opakovaně volá sama sebe, dokud není splněna základní podmínka. | Iterace je proces, při kterém se část kódu opakovaně provádí určitý početkrát nebo dokud není splněna určitá podmínka. |
| Je aplikace pro funkce. | Platí pro smyčky. |
| Funguje dobře pro menší velikost kódu. | Funguje dobře pro větší velikost kódu. |
| Využívá více paměti, protože každé rekurzivní volání je přesunuto na zásobník. | Využívá se relativně méně paměti. |
| Obtížné ladění a údržba | Snadnější ladění a údržba |
| Pokud není zadána základní podmínka nebo jí není dosaženo, dojde k přetečení zásobníku. | Může se provádět donekonečna, ale nakonec se zastaví při jakékoli chybě v paměti. |
| Časová náročnost je velmi vysoká. | Časová náročnost je relativně nižší. |
Často kladené otázky
Otázka č. 1) Jak funguje rekurze v jazyce Java?
Odpověď: Při rekurzi rekurzivní funkce opakovaně volá sama sebe, dokud není splněna základní podmínka. Paměť pro volanou funkci se přesune na zásobník na vrchol paměti pro volající funkci. Pro každé volání funkce se vytvoří samostatná kopie lokálních proměnných.
Q #2) Proč se rekurze používá?
Odpověď: Rekurze se používá k řešení těch problémů, které lze rozdělit na menší a celý problém lze vyjádřit pomocí menšího problému.
Rekurze se používá také u těch problémů, které jsou příliš složité na to, aby se daly řešit iteračním přístupem. Kromě problémů, u kterých časová složitost nehraje roli, používejte rekurzi.
Q #3) Jaké jsou výhody rekurze?
Odpověď:
Mezi výhody rekurze patří:
- Rekurze omezuje nadbytečné volání funkce.
- Rekurze nám umožňuje snadnější řešení problémů ve srovnání s iteračním přístupem.
Otázka č. 4) Který z nich je lepší - rekurze nebo iterace?
Odpověď: Rekurze provádí opakovaná volání, dokud se nedosáhne základní funkce. Tím vzniká paměťová režie, protože se na zásobník přenáší paměť pro každé volání funkce.
Iterace na druhou stranu nemá velkou paměťovou režii. Provádění rekurze je pomalejší než iterativní přístup. Rekurze zmenšuje velikost kódu, zatímco iterativní přístup kód zvětšuje.
Q #5) Jaké jsou výhody rekurze oproti iteraci?
Odpověď:
- Díky rekurzi je kód přehlednější a kratší.
- Rekurze je lepší než iterativní přístup pro problémy, jako je Hanojská věž, procházení stromů atd.
- Vzhledem k tomu, že při každém volání funkce se paměť přesune na zásobník, rekurze využívá více paměti.
- Rekurzivní přístup je pomalejší než iterativní přístup.
Závěr
Rekurze je v softwaru velmi důležitým konceptem bez ohledu na programovací jazyk. Rekurze se většinou používá při řešení problémů datových struktur, jako jsou hanojské věže, procházení stromů, propojené seznamy atd. I když rekurze zabírá více paměti, kód je díky ní jednodušší a přehlednější.
V tomto tutoriálu jsme prozkoumali vše o rekurzi. Pro lepší pochopení tohoto konceptu jsme také implementovali řadu příkladů programování.