Menu

Rekurzia v Jave - návod s príkladmi

recursion java tutorial with examples

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Tento podrobný návod na rekurziu v Jave vysvetľuje, čo je rekurzia s príkladmi, typmi a súvisiacimi konceptmi. Zahŕňa tiež rekurziu Vs iteráciu:

Z našich predchádzajúcich tutoriálov v Jave sme videli iteračný prístup, pri ktorom deklarujeme slučku a potom prechádzame dátovou štruktúrou iteračným spôsobom tak, že berieme po jednom prvku.

Tiež sme videli podmienený tok, kde opäť ponechávame jednu premennú slučky a opakujeme kúsok kódu, kým premenná slučky nespĺňa podmienku. Pokiaľ ide o volanie funkcií, preskúmali sme iteračný prístup aj pre volanie funkcií.

=> Skontrolujte VŠETKY návody Java tu.

Rekurzia v Jave

V tomto tutoriáli sa budeme zaoberať iným prístupom k programovaniu, t. J. Rekurzívnym prístupom.

Čo sa dozviete:

Čo je rekurzia v prostredí Java?

Rekurzia je proces, pri ktorom sa funkcia alebo metóda volá znova a znova. Táto funkcia, ktorá sa opakovane volá priamo alebo nepriamo, sa nazýva „rekurzívna funkcia“.

Uvidíme rôzne príklady na pochopenie rekurzie. Teraz sa pozrime na syntax rekurzie.

Syntax rekurzie

Každá metóda, ktorá implementuje rekurziu, má dve základné časti:

  1. Volanie metódy, ktoré sa môže nazývať samo, tzn
  2. Predpoklad, ktorý zastaví rekurziu.

Všimnite si, že pre každú rekurzívnu metódu je nevyhnutný predpoklad, pretože ak rekurziu neporušíme, bude pokračovať v chode nekonečne dlho a vyústi do pretečenia zásobníka.

Všeobecná syntax rekurzie je nasledovná:

methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call }

Upozorňujeme, že podmienka sa nazýva aj základná podmienka. O základnej podmienke si povieme viac v nasledujúcej časti.

Pochopenie rekurzie v Jave

V tejto časti sa pokúsime porozumieť procesu rekurzie a zistiť, ako prebieha. Dozvieme sa o základnej podmienke, pretečení zásobníka a uvidíme, ako možno vyriešiť konkrétny problém pomocou rekurzie a ďalších podobných podrobností.

Základná podmienka rekurzie

Pri písaní rekurzívneho programu by sme mali najskôr poskytnúť riešenie základného prípadu. Potom väčší problém vyjadríme z hľadiska menších problémov.

Ako príklad môžeme vziať klasický problém výpočtu faktoriálu čísla. Keď dáme číslo n, musíme nájsť faktoriál n označený n!

Teraz implementujme program na výpočet n faktoriálu (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ýkon

Základná podmienka rekurzie

aplikácia na špehovanie iného telefónu

V tomto programe vidíme, že podmienka (n<=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 teda dospieť k záveru, že hodnota n sa nakoniec stane 1 alebo menšou ako 1 a v tomto okamihu spôsob vráti metódu 1. Táto základná podmienka sa dosiahne a funkcia sa zastaví. 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 z hľadiska menších problémov. Tiež musíme pridať jednu alebo viac základných podmienok, aby sme mohli vyjsť z rekurzie.

To sa už preukázalo vo vyššie uvedenom faktoriálnom príklade. V tomto programe sme n faktoriál (n!) Vyjadrili ako menšie hodnoty a mali sme základnú podmienku (n<=1) so that when n reaches 1, we can quit the recursive method.

Chyba pretečenia zásobníka v rekurzii

Sme si vedomí, že keď sa volá akákoľvek metóda alebo funkcia, stav funkcie sa uloží do zásobníka a získa sa, keď sa funkcia vráti. Zásobník sa používa aj pre rekurzívnu metódu.

Ale v prípade rekurzie môže nastať problém, ak nedefinujeme základnú podmienku alebo ak sa základná podmienka nejako nedosiahne alebo nevykoná. Ak nastane táto situácia, môže dôjsť k pretečeniu zásobníka.

Uvažujme nižšie uvedený 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) // 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); } }

Takže keď n> 100, metóda vráti 1, ale rekurzia sa nezastaví. Hodnota n bude klesať donekonečna, pretože neexistuje iná podmienka, ktorá by ju zastavila. Bude to pokračovať, kým pretečie zásobník.

Ďalším prípadom bude, keď hodnota n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.

Príklady rekurzie v Jave

V tejto časti implementujeme nasledujúce príklady pomocou rekurzie.

# 1) Fibonacciho séria pomocou rekurzie

Séria Fibonacci je daná,

1,1,2,3,5,8,13,21,34,55, ...

Vyššie uvedená postupnosť ukazuje, že aktuálny prvok je súčtom predchádzajúcich dvoch prvkov. Prvý prvok v sérii Fibonacci je tiež 1.

Všeobecne teda platí, že ak n je súčasné číslo, potom je dané súčtom (n-1) a (n-2). Pretože súčasný prvok je vyjadrený v zmysle predchádzajúcich prvkov, môžeme tento problém vyjadriť pomocou rekurzie.

Program na implementáciu série Fibonacci je uvedený nižšie:

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ýkon

Séria Fibonacci - výstup

# 2) Pomocou rekurzie skontrolujte, či je číslo palindróm

Palindróm je postupnosť, ktorá je rovnaká, keď ju čítame zľava doprava alebo sprava doľava.

Pri čísle 121 vidíme, že keď ho čítame zľava doprava a sprava doľava, je to rovnaké. Preto je číslo 121 palindróm.

Zoberme si ďalšie číslo, 1242. Keď čítame zľava doprava, je to 1242 a keď čítame sprava-zľava, čítame to ako 2421. Nejde teda o palindróm.

Program palindrómu implementujeme obrátením číslic čísel a rekurzívne porovnáme dané číslo s jeho obráteným zastúpením.

Nasledujúci program implementuje program na kontrolu palindrómu.

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ýkon

Skontrolujte, či je číslo palindróm - výstup

# 3) Reverzná reťazcová rekurzia Java

Keď dostaneme reťazec „Hello“, musíme ho obrátiť tak, aby výsledný reťazec bol „olleH“.

To sa deje pomocou rekurzie. Počnúc posledným znakom v reťazci rekurzívne tlačíme každý znak, kým nie sú vyčerpané všetky znaky v reťazci.

Nižšie uvedený program používa rekurziu na obrátenie daného reťazca.

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ýkon

Reverzná reťazcová rekurzia Java

# 4) Binárne vyhľadávanie Java rekurzie

Algoritmus binárneho vyhľadávania je slávny algoritmus na vyhľadávanie. V tomto algoritme, vzhľadom na zoradené pole n prvkov, hľadáme v tomto poli daný kľúčový prvok. Na začiatku rozdelíme pole na dve polovice vyhľadaním stredného prvku poľa.

Potom podľa toho, či kláves v strede obmedzíme naše hľadanie v prvej alebo druhej polovici poľa. Týmto spôsobom sa opakuje ten istý proces, kým sa nenájde umiestnenie kľúčových prvkov.

Tento algoritmus tu implementujeme pomocou rekurzie.

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ýkon

Binárne vyhľadávanie Java - výstup

# 5) Nájdite minimálnu hodnotu v poli pomocou rekurzie

Pomocou rekurzie nájdeme v poli aj minimálnu hodnotu.

Program Java na vyhľadanie minimálnej hodnoty v poli je uvedený nižšie.

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ýkon

minimálna hodnota v rekurzii poľa Java - výstup

Toto je niekoľko príkladov rekurzie. Okrem týchto príkladov možno pomocou rekurzívnych techník implementovať množstvo ďalších problémov v softvéri.

Typy rekurzie

Rekurzia je dvoch typov podľa toho, kedy sa volá rekurzívna metóda.

Oni sú:

# 1) chvostová rekurzia

Keď 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 rekurzii chvosta sa príkaz rekurzívneho volania zvyčajne vykonáva spolu s návratovým príkazom metódy.

Všeobecná syntax pre rekurziu chvosta je uvedená nižšie:

methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion }

# 2) Rekurzia hlavy

Rekurzia hlavy je akýkoľvek rekurzívny prístup, ktorý nie je rekurziou chvosta. Takže aj všeobecná rekurzia je pred rekurziou.

Syntax rekurzie hlavy je nasledovná:

methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; }

Iterácia rekurzie Vs v Jave

RekurziaIterácia
Časová zložitosť je veľmi veľká.Časová zložitosť je relatívne na spodnej strane.
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 po konečný počet opakovaní alebo kým nie je splnená podmienka.
Je aplikácia pre funkcie.Je použiteľné pre slučky.
Funguje dobre pre menšiu veľkosť kódu.Funguje dobre pre väčšiu veľkosť kódu.
Využíva viac pamäte pri každom rekurzívnom volaní do zásobníkaVyužíva sa porovnateľne menej pamäte.
Je ťažké odladiť a udržiavaťĽahšie ladiť a udržiavať
Výsledkom bude pretečenie zásobníka, ak nie je zadaná alebo nedosiahnutá základná podmienka.Môže sa spúšťať nekonečne, ale nakoniec zastaví vykonávanie pri akýchkoľvek chybách pamäte

často kladené otázky

Otázka č. 1) Ako funguje rekurzia v Jave?

Odpoveď: Pri rekurzii sa rekurzívna funkcia volá opakovane, kým nie je splnená základná podmienka. Pamäť pre volanú funkciu sa vloží do zásobníka v hornej časti pamäte pre volajúcu funkciu. Pre každé volanie funkcie sa vytvorí samostatná kópia miestnych premenných.

Otázka č. 2) Prečo sa používa rekurzia?

Odpoveď: Rekurzia sa používa na riešenie tých problémov, ktoré možno rozdeliť na menšie a celý problém možno vyjadriť v podobe menšieho problému.

Rekurzia sa používa aj na tie problémy, ktoré sú príliš zložité na to, aby ich bolo možné vyriešiť pomocou iteračného prístupu. Okrem problémov, pre ktoré nie je problémom časová zložitosť, použite rekurziu.

Otázka č. 3) Aké sú výhody rekurzie?

Odpoveď:

Medzi výhody rekurzie patria:

  1. Rekurzia redukuje nadbytočné volanie funkcie.
  2. Rekurzia nám umožňuje ľahko vyriešiť problémy v porovnaní s iteračným prístupom.

Otázka č. 4) Ktorý z nich je lepší - rekurzia alebo iterácia?

Odpoveď: Rekurzia opakuje hovory, kým sa nedosiahne základná funkcia. Existuje teda réžia pamäte, pretože pamäť pre každé volanie funkcie sa posúva do zásobníka.

Iterácia na druhej strane nemá veľa pamäte nad hlavou. Vykonávanie rekurzie je pomalšie ako pri iteratívnom prístupe. Rekurzia zmenšuje veľkosť kódu, zatiaľ čo iteračný prístup zväčšuje kód.

Otázka č. 5) Aké sú výhody rekurzie pri iterácii?

Odpoveď:

  • Rekurzia robí kód jasnejším a kratším.
  • Rekurzia je lepšia ako iteračný prístup k problémom, ako je Hanojská veža, priechody stromov atď.
  • Pretože každé volanie funkcie má pamäť vloženú do zásobníka, rekurzia využíva viac pamäte.
  • Výkon rekurzie je pomalší ako iteračný prístup.

Záver

Rekurzia je v softvéri veľmi dôležitý pojem bez ohľadu na programovací jazyk. Rekurzia sa väčšinou používa pri riešení problémov s dátovými štruktúrami, ako sú veže Hanoja, prechody stromov, prepojené zoznamy atď. Aj keď to vyžaduje viac pamäte, rekurzia robí kód jednoduchším a prehľadnejším.

V tomto tutoriáli sme preskúmali všetko o rekurzii. Implementovali sme tiež množstvo príkladov programovania pre lepšie pochopenie konceptu.

=> Prečítajte si sériu Easy Java Training Series.

Odporúčané čítanie

^