recursion java tutorial with examples
Ta poglobljena vadnica o rekurziji v Javi pojasnjuje, kaj je rekurzija s primeri, vrstami in sorodnimi koncepti. Obsega tudi rekurzijo proti ponovitvi:
Iz naših prejšnjih vadnic v Javi smo videli iterativni pristop, pri katerem razglasimo zanko in nato iterativno prehodimo skozi podatkovno strukturo tako, da vzamemo en element naenkrat.
Opazili smo tudi pogojni tok, kjer spet obdržimo eno spremenljivko zanke in ponavljamo kos kode, dokler spremenljivka zanke ne izpolni pogoja. Ko gre za klice funkcij, smo preučili iterativni pristop tudi za klice funkcij.
=> Tukaj preverite VSE Vadnice za Java.
V tej vadnici bomo obravnavali drugačen pristop k programiranju, tj. Rekurzivni pristop.
Kaj se boste naučili:
- Kaj je rekurzija v Javi?
- Rekurzija vs iteracija v Javi
- Zaključek
Kaj je rekurzija v Javi?
Rekurzija je postopek, s katerim se funkcija ali metoda vedno znova pokliče. Ta funkcija, ki se vedno znova kliče neposredno ali posredno, se imenuje 'rekurzivna funkcija'.
Naprave modela osi uporabljajo vsako plast
Videli bomo različne primere za razumevanje rekurzije. Zdaj pa poglejmo sintakso rekurzije.
Sintaksa ponovitve
Vsaka metoda, ki izvaja rekurzijo, ima dva osnovna dela:
- Klic metode, ki se lahko pokliče, tj. Rekurzivno
- Predpogoj, ki bo zaustavil rekurzijo.
Upoštevajte, da je za katero koli rekurzivno metodo potreben predpogoj, saj če rekurzije ne prekinemo, se bo nadaljevala neskončno in povzročila prelivanje skladovnice.
Splošna sintaksa rekurzije je naslednja:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Upoštevajte, da se predpogoj imenuje tudi osnovni pogoj. Več o osnovnem stanju bomo obravnavali v naslednjem poglavju.
Razumevanje rekurzije v Javi
V tem poglavju bomo poskušali razumeti postopek rekurzije in si ogledati, kako poteka. Spoznali bomo osnovno stanje, prelivanje skladov in videli, kako je mogoče določeno težavo rešiti z rekurzijo in drugimi takimi podrobnostmi.
Osnovno stanje rekurzije
Med pisanjem rekurzivnega programa bi morali najprej zagotoviti rešitev za osnovni primer. Nato večji problem izrazimo z manjšimi problemi.
Kot na primer, lahko vzamemo klasičen problem izračuna faktorja števila. Glede na število n moramo poiskati faktorijel n, ki ga označujemo z n!
Zdaj pa izvedimo program za izračun n faktorja (n!) Z uporabo rekurzije.
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); } }Izhod
V tem programu lahko vidimo, da je pogoj (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.
Tako lahko sklepamo, da bo vrednost n končno postala 1 ali manj kot 1 in v tem trenutku bo metoda vrnila vrednost 1. Ta osnovni pogoj bo dosežen in funkcija se bo ustavila. Upoštevajte, da je vrednost n lahko karkoli, če izpolnjuje osnovni pogoj.
Reševanje težav z uporabo rekurzije
Osnovna ideja uporabe rekurzije je izraziti večji problem z manjšimi. Prav tako moramo dodati enega ali več osnovnih pogojev, da bomo lahko prišli iz rekurzije.
To je bilo že prikazano v zgornjem faktorskem primeru. V tem programu smo izrazili n faktorijel (n!) Z manjšimi vrednostmi in imeli osnovni pogoj (n<=1) so that when n reaches 1, we can quit the recursive method.
Napaka pri prelivanju skladb v ponovitvi
Zavedamo se, da se ob klicu katere koli metode ali funkcije stanje funkcije shrani v sklad in se po vrnitvi funkcije pridobi. Sklop se uporablja tudi za rekurzivno metodo.
Toda v primeru rekurzije lahko pride do težave, če ne definiramo osnovnega stanja ali če osnovnega stanja nekako ne dosežemo ali izvedemo. Če pride do te situacije, lahko pride do prelivanja sklada.
Upoštevajmo spodnji primer faktorskega zapisa.
Tu smo podali napačen osnovni pogoj, 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); } }Torej, ko je n> 100, bo metoda vrnila 1, vendar se rekurzija ne bo ustavila. Vrednost n se bo še naprej neomejeno zmanjševala, saj ni nobenega drugega pogoja, da bi jo ustavili. To se bo nadaljevalo, dokler se sklad ne prelije.
Drug primer bo, ko bo vrednost n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
Primeri rekurzije v Javi
V tem poglavju bomo z uporabo rekurzije izvedli naslednje primere.
# 1) Fibonaccijeve serije z uporabo rekurzije
Serijo Fibonacci podaja,
1,1,2,3,5,8,13,21,34,55, ...
Zgornje zaporedje kaže, da je trenutni element vsota prejšnjih dveh elementov. Tudi prvi element v Fibonaccijevi seriji je 1.
Torej na splošno, če je n trenutno število, potem je podano z vsoto (n-1) in (n-2). Ker je trenutni element izražen v smislu prejšnjih elementov, lahko to težavo izrazimo z uporabo rekurzije.
Program za izvedbo Fibonaccijeve serije je podan spodaj:
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) + ' '); } } } Izhod
# 2) Preverite, ali je številka palindrom z uporabo rekurzije
Palindrom je zaporedje, ki je enako, ko ga beremo od leve proti desni ali od desne proti levi.
Glede na številko 121 vidimo, da je, ko jo beremo od leve proti desni in od desne proti levi, enaka. Številka 121 je torej palindrom.
Vzemimo drugo številko, 1242. Ko jo beremo od leve proti desni, je 1242, pri branju od desne proti levi pa 2421. Torej to ni palindrom.
vprašanja in odgovori za testiranje spletnih aplikacij
Program palindrom izvajamo tako, da obrnemo števke števil in rekurzivno primerjamo dano število z njegovo obratno predstavitvijo.
Spodnji program izvaja program za preverjanje palindroma.
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.'); } } }Izhod
# 3) Reverzija niza Java
Glede na niz »Hello« ga moramo obrniti, tako da je nastali niz »olleH«.
To se naredi z uporabo rekurzije. Od zadnjega znaka v nizu rekurzivno natisnemo vsak znak, dokler niso vsi znaki v nizu izčrpani.
Spodnji program uporablja rekurzijo za obrat določenega niza.
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); } } Izhod
# 4) Rekurzija binarnega iskanja Java
Binarni algoritem iskanja je znan algoritem za iskanje. V tem algoritmu, glede na razvrščeno matriko n elementov, v tej matriki iščemo dani ključni element. Na začetku matriko razdelimo na dve polovici, tako da najdemo sredinski element matrike.
Nato, odvisno od tega, ali je tipka mid, omejimo iskanje v prvi ali drugi polovici polja. Na ta način se isti postopek ponavlja, dokler ne najdemo lokacije ključnih elementov.
Ta algoritem bomo tukaj uporabili z uporabo rekurzije.
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); } } Izhod
# 5) Poiščite najmanjšo vrednost v matriki z uporabo rekurzije
Z uporabo rekurzije lahko najdemo tudi najmanjšo vrednost v matriki.
Program Java za iskanje najmanjše vrednosti v matriki je podan spodaj.
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) + '
'); } }Izhod
To je nekaj primerov rekurzije. Poleg teh primerov lahko z uporabo rekurzivnih tehnik izvedemo še veliko drugih težav v programski opremi.
Vrste rekurzije
Rekurzija je dve vrsti glede na to, kdaj je bil klic opravljen z rekurzivno metodo.
To so:
# 1) Rekurzija repa
Ko je klic rekurzivne metode zadnji stavek, izveden znotraj rekurzivne metode, se imenuje 'Rekurzija repa'.
V rekurziji repa se rekurzivni klic običajno izvede skupaj z vrnitvijo stavka metode.
Splošna sintaksa za rekurzijo repa je podana spodaj:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } # 2) Rekurzija glave
Rekurzija glave je vsak rekurzivni pristop, ki ni rekurzija repa. Torej je celo splošna rekurzija pred rekurzijo.
Sintaksa rekurzije glave je naslednja:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Rekurzija vs iteracija v Javi
| Rekurzija | Ponavljanje |
|---|---|
| Časovna zapletenost je zelo velika. | Zapletenost časa je razmeroma na spodnji strani. |
| Rekurzija je postopek, pri katerem se metoda večkrat pokliče, dokler ni izpolnjen osnovni pogoj. | Iteracija je postopek, pri katerem se del kode večkrat izvede končno število krat ali dokler ni izpolnjen pogoj. |
| Je aplikacija za funkcije. | Se uporablja za zanke. |
| Dobro deluje pri manjši velikosti kode. | Dobro deluje pri večji velikosti kode. |
| Izkoristi več pomnilnika, ko je vsak rekurzivni klic potisnjen v sklad | Uporablja se razmeroma manj pomnilnika. |
| Težko odpraviti napake in vzdrževati | Lažje odpravljanje napak in vzdrževanje |
| Rezultat je prelivanje skladov, če osnovno stanje ni določeno ali ni doseženo. | Lahko se izvaja neskončno, vendar bo na koncu ustavil izvajanje z morebitnimi napakami v pomnilniku |
Pogosto zastavljena vprašanja
V # 1) Kako Rekurzija deluje v Javi?
Odgovor: V rekurziji se rekurzivna funkcija večkrat pokliče, dokler ni izpolnjen osnovni pogoj. Spomin za poklicano funkcijo se potisne v sklad na vrhu pomnilnika za klicno funkcijo. Za vsak klic funkcije se naredi ločena kopija lokalnih spremenljivk.
Q # 2) Zakaj se uporablja rekurzija?
Odgovor: Rekurzija se uporablja za reševanje tistih problemov, ki jih je mogoče razčleniti na manjše, celoten problem pa izraziti z manjšim problemom.
Rekurzija se uporablja tudi za tiste težave, ki so preveč zapletene, da bi jih bilo mogoče rešiti z iterativnim pristopom. Poleg težav, za katere časovna zapletenost ni problem, uporabite rekurzijo.
Q # 3) Kakšne so prednosti rekurzije?
Odgovor:
Prednosti rekurzije vključujejo:
- Rekurzija zmanjša odvečno klicanje funkcije.
- Rekurzija nam omogoča enostavno reševanje problemov v primerjavi z iterativnim pristopom.
V # 4) Kateri je boljši - rekurzija ali ponovitev?
Odgovor: Rekurzija ponavlja klice, dokler ni dosežena osnovna funkcija. Tako pride do režijske porabe pomnilnika, saj se pomnilnik za vsak klic funkcije potisne v sklad.
Ponavljanje po drugi strani nima veliko pomnilnika. Izvajanje rekurzije je počasnejše od iterativnega pristopa. Rekurzija zmanjša velikost kode, medtem ko iterativni pristop poveča kodo.
V # 5) Kakšne so prednosti rekurzije pred ponovitvijo?
Odgovor:
- Rekurzija naredi kodo jasnejšo in krajšo.
- Rekurzija je boljša od iterativnega pristopa pri težavah, kot so stolp v Hanoju, prehojevanje dreves itd.
- Ker ima vsak funkcijski klic pomnilnik potisnjen v sklad, Recursion porabi več pomnilnika.
- Rekurzija je počasnejša od iterativnega pristopa.
Zaključek
Rekurzija je zelo pomemben koncept v programski opremi, ne glede na programski jezik. Rekurzija se večinoma uporablja pri reševanju problemov s podatkovno strukturo, kot so stolpi v Hanoju, prečkanje dreves, povezani seznami itd. Čeprav zahteva več pomnilnika, koda postane preprostejša in jasnejša.
V tej vadnici smo raziskali vse o rekurziji. Za boljše razumevanje koncepta smo izvedli tudi številne primere programiranja.
=> Preberite serijo Easy Java Training Series.
Priporočeno branje
- Rekurzija v C ++
- Java Iterator: Naučite se uporabljati iteratorje v Javi s primeri
- ListIterator vmesnik v Javi s primeri
- JAVA Vadnica za začetnike: 100+ praktičnih Javnih video vadnic
- Vadnica Java za zanke s primeri programov
- Java While Loop - Vadnica s primeri programiranja
- Java Do While Loop - Vadnica s primeri
- Nazobčan niz v Javi - Vadnica s primeri