recursion java tutorial with examples
Tento podrobný kurz rekurze v Javě vysvětluje, co je rekurze s příklady, typy a souvisejícími koncepty. Pokrývá také rekurzi Vs Iterace:
Z našich dřívějších výukových programů v Javě jsme viděli iterativní přístup, při kterém deklarujeme smyčku a poté procházíme datovou strukturou iterativním způsobem tak, že vezmeme jeden prvek najednou.
Viděli jsme také podmíněný tok, kde opět udržujeme jednu proměnnou smyčky a opakujeme část 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í.
=> Zkontrolujte VŠECHNY výukové programy Java zde.
V tomto tutoriálu probereme jiný přístup k programování, tj. Rekurzivní přístup.
Co se naučíte:
- Co je rekurze v Javě?
- Rekurze V Iterace v Javě
- Závěr
Co je rekurze v Javě?
Rekurze je proces, při kterém se funkce nebo metoda volá znovu a znovu. Tato funkce, která se znovu a znovu volá přímo nebo nepřímo, se nazývá „rekurzivní funkce“.
Uvidíme různé příklady k pochopení rekurze. Nyní se podívejme na syntaxi rekurze.
Syntaxe rekurze
Jakákoli metoda, která implementuje rekurzi, má dvě základní části:
- Volání metody, které se může nazývat samo, tj. Rekurzivní
- Předpoklad, který zastaví rekurzi.
Všimněte si, že předpoklad je nezbytný pro jakoukoli rekurzivní metodu, protože pokud neporušíme rekurzi, bude pokračovat v chodu nekonečně a vyústí v přetečení zásobníku.
Obecná syntaxe rekurze je následující:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call }
Všimněte si, že podmínka se také nazývá základní podmínka. O základní podmínce budeme diskutovat v další části.
Porozumění rekurzi v Javě
V této části se pokusíme porozumět procesu rekurze a zjistit, jak probíhá. Dozvíme se o základní podmínce, přetečení zásobníku a uvidíme, jak lze konkrétní problém vyřešit pomocí rekurze a dalších podobných podrobností.
Rekurzivní základní podmínka
Při psaní rekurzivního programu bychom měli nejprve poskytnout řešení pro základní případ. Pak větší problém vyjádříme z hlediska menších problémů.
Jako příklad, můžeme vzít klasický problém výpočtu faktoriálu čísla. Vzhledem k číslu n musíme najít faktoriál n označený n!
Nyní provedeme program pro výpočet n faktoriálu (n!) Pomocí rekurze.
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 programu vidíme, že podmínka (č<=1) is the base condition and when this condition is reached, the function returns 1. The else part of the function is the recursive call. But every time the recursive method is called, n is decremented by 1.
Můžeme tedy dojít k závěru, že nakonec se hodnota n stane 1 nebo menší než 1 a v tomto okamžiku způsob vrátí hodnotu 1. Tato základní podmínka bude dosažena a funkce se zastaví. Hodnota n může být cokoli, 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 z hlediska menších problémů. Také musíme přidat jednu nebo více základních podmínek, abychom mohli vyjít z rekurze.
To již bylo prokázáno ve výše uvedeném faktoriálním příkladu. V tomto programu jsme vyjádřili n faktoriál (n!) Z hlediska menších hodnot a měli základní podmínku (n<=1) so that when n reaches 1, we can quit the recursive method.
Chyba přetečení zásobníku při rekurzi
Jsme si vědomi, že při volání jakékoli metody nebo funkce se stav funkce uloží do zásobníku a načte se, když se funkce vrátí. Zásobník se používá také pro rekurzivní metodu.
jak spustit testování automatizace od nuly
V případě rekurze však může nastat problém, pokud nedefinujeme základní podmínku nebo pokud základní podmínku nějak nedosáhneme nebo nevykonáme. Pokud k této situaci dojde, může dojít k přetečení zásobníku.
Uvažujme níže uvedený příklad faktoriálního zápisu.
Zde jsme dali špatnou základní podmínku, n == 100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println('10! = ' + result); } }
Když tedy n> 100, metoda vrátí 1, ale rekurze se nezastaví. Hodnota n se bude neustále snižovat, protože neexistuje žádná další podmínka, která by ji zastavila. To bude pokračovat, dokud přetečení zásobníku.
Jiným případem bude, když hodnota n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
Příklady rekurze v Javě
V této části implementujeme následující příklady pomocí rekurze.
# 1) Fibonacciho série pomocí rekurze
Série Fibonacci je dána,
1,1,2,3,5,8,13,21,34,55, ...
Výše uvedená sekvence ukazuje, že aktuální prvek je součtem předchozích dvou prvků. První prvek v řadě Fibonacci je také 1.
sql dotaz otázky a odpovědi pro zkušené pdf
Obecně tedy platí, že pokud n je aktuální číslo, pak je dáno součtem (n-1) a (n-2). Protože aktuální prvek je vyjádřen z hlediska předchozích prvků, můžeme tento problém vyjádřit pomocí rekurze.
Program implementace řady Fibonacci je uveden níže:
public class Main { //method to calculate fibonacci series 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; //print first 10 numbers of fibonacci series System.out.println ('Fibonacci Series: First 10 numbers:'); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + ' '); } } }
Výstup
# 2) Pomocí rekurze zkontrolujte, zda je číslo palindromem
Palindrom je sekvence, která je stejná, když ji čteme zleva doprava nebo zprava doleva.
Vzhledem k číslu 121 vidíme, že když to čteme zleva doprava a zprava doleva, je to stejné. Proto je číslo 121 palindrom.
Vezměme si další číslo, 1242. Když čteme zleva doprava, je to 1242 a když čteme zprava doleva, čte se to jako 2421. Nejedná se tedy o palindrom.
Program palindromu implementujeme obrácením číslic čísel a rekurzivně porovnáváme dané číslo s jeho obrácenou reprezentací.
Níže uvedený program implementuje program ke kontrole palindromu.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit 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 { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { 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('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } n = 1221; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } } }
Výstup
# 3) Reverzní řetězec rekurze Java
Vzhledem k řetězci „Hello“ jej musíme obrátit, aby výsledný řetězec byl „olleH“.
To se provádí pomocí rekurze. Počínaje od posledního znaku v řetězci rekurzivně tiskneme každý znak, dokud nejsou vyčerpány všechny znaky v řetězci.
Níže uvedený program používá rekurzi k obrácení daného řetězce.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() <= 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String[] args) { String inputstr = 'SoftwareTestingHelp'; System.out.println('The given string: ' + inputstr); String_Reverse obj = new String_Reverse(); System.out.print('The reversed string: '); obj.reverseString(inputstr); } }
Výstup
# 4) Binární vyhledávání Java rekurze
Algoritmus binárního vyhledávání je slavný algoritmus pro vyhledávání. V tomto algoritmu, vzhledem k seřazenému poli n prvků, prohledáme toto pole pro daný klíčový prvek. Na začátku rozdělíme pole na dvě poloviny vyhledáním středního prvku pole.
Pak v závislosti na tom, zda klíč uprostřed omezíme naše hledání v první nebo druhé polovině pole. Tímto způsobem se opakuje stejný proces, dokud není nalezeno umístění klíčových prvků.
Zde implementujeme tento algoritmus pomocí rekurze.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray[], int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray[mid] == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray[] = { 4,6,12,16,22}; System.out.println('The given array : ' + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched 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) Najděte minimální hodnotu v poli pomocí rekurze
Pomocí rekurze můžeme také najít minimální hodnotu v poli.
Níže je uveden program Java pro zjištění minimální hodnoty v poli.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //return first element if only one element or minimum of the array elements 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('Given Array : ' + Arrays.toString(numArray)); int n = numArray.length; System.out.print('Minimum element of array: ' + getMin(numArray, 0, n) + '
'); } }
Výstup
Toto jsou některé z příkladů rekurze. Kromě těchto příkladů lze pomocí rekurzivních technik implementovat mnoho dalších problémů v softwaru.
Typy rekurze
Rekurze je dvou typů založených na tom, kdy je provedeno volání rekurzivní metody.
Oni jsou:
# 1) Ocasní rekurze
Když je volání rekurzivní metody posledním příkazem provedeným uvnitř rekurzivní metody, nazývá se „Tail Recursion“.
V rekurzi ocasu se příkaz rekurzivního volání obvykle provádí společně s návratovým příkazem metody.
Obecná syntaxe pro rekurzi ocasu je uvedena níže:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion }
# 2) Rekurze hlavy
Rekurze hlavy je jakýkoli rekurzivní přístup, který není rekurzí ocasu. Takže i obecná rekurze je před rekurzí.
Syntaxe rekurze hlavy je následující:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; }
Rekurze V Iterace v Javě
Rekurze | Opakování |
---|---|
Časová složitost je velmi vysoká. | Časová složitost je relativně na spodní straně. |
Rekurze je proces, při kterém se metoda opakovaně volá, dokud není splněna základní podmínka. | Iterace je proces, při kterém se část kódu opakovaně provádí po konečný počet opakování nebo do splnění podmínky. |
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, když se každé rekurzivní volání posílá do zásobníku | Využívá se relativně méně paměti. |
Je obtížné ladit a udržovat | Snadnější ladění a údržba |
Výsledek přetečení zásobníku, pokud není zadána nebo nedosažena základní podmínka. | Může se spouštět nekonečně, ale nakonec zastaví provádění s případnými chybami paměti |
Často kladené otázky
Otázka č. 1) Jak funguje rekurze v Javě?
Odpovědět: V rekurzi se rekurzivní funkce opakovaně volá, dokud není splněna základní podmínka. Paměť pro volanou funkci se vloží do zásobníku v horní části paměti pro volající funkci. Pro každé volání funkce se vytvoří samostatná kopie místních proměnných.
Otázka č. 2) Proč se používá rekurze?
Odpovědět: 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 také používá u těch problémů, které jsou příliš složité na to, aby je bylo možné vyřešit pomocí iterativního přístupu. Kromě problémů, pro které není časová složitost problémem, použijte rekurzi.
Otázka č. 3) Jaké jsou výhody rekurze?
Odpovědět:
Mezi výhody rekurze patří:
- Rekurze snižuje nadbytečné volání funkce.
- Rekurze nám umožňuje snadno vyřešit problémy ve srovnání s iterativním přístupem.
Otázka č. 4) Který z nich je lepší - rekurze nebo iterace?
Odpovědět: Rekurze provádí opakovaná volání, dokud není dosaženo základní funkce. Existuje tedy režie paměti, protože paměť pro každé volání funkce je přenesena do zásobníku.
Iterace na druhé straně nemá mnoho paměti nad hlavou. Provádění rekurze je pomalejší než iterativní přístup. Rekurze zmenšuje velikost kódu, zatímco iterativní přístup zvětšuje kód.
Otázka č. 5) Jaké jsou výhody rekurze při iteraci?
Odpovědět:
nejlepší převodník z youtube na mp3 pro mac
- Rekurze činí kód jasnějším a kratším.
- Rekurze je lepší než iterativní přístup k problémům, jako je Hanojská věž, procházení stromů atd.
- Protože každé volání funkce má paměť vloženou do zásobníku, využívá rekurze více paměti.
- Rekurzivní výkon je pomalejší než iterativní přístup.
Závěr
Rekurze je velmi důležitý pojem v softwaru bez ohledu na programovací jazyk. Rekurze se většinou používá při řešení problémů s datovými strukturami, jako jsou věže v Hanoji, procházení stromů, propojené seznamy atd. I když to vyžaduje více paměti, rekurze činí kód jednodušším a jasnějším.
V tomto tutoriálu jsme prozkoumali vše o rekurzi. Také jsme implementovali řadu příkladů programování pro lepší pochopení konceptu.
=> Přečtěte si řadu Easy Java Training Series.
Doporučené čtení
- Rekurze v C ++
- Java Iterator: Naučte se používat Iterátory v Javě s příklady
- Rozhraní ListIterator v Javě s příklady
- Výukový program JAVA pro začátečníky: 100+ praktických výukových programů Java Video
- Výukový program Java pro smyčku s příklady programů
- Java While Loop - výukový program s příklady programování
- Java dělá smyčku - výukový program s příklady
- Jagged Array In Java - výukový program s příklady