Ovaj detaljni vodič o rekurziji u Javi objašnjava što je rekurzija s primjerima, vrstama i povezanim konceptima. Također pokriva rekurziju u odnosu na iteraciju:
Iz naših ranijih udžbenika u Javi, vidjeli smo iterativni pristup u kojem deklariramo petlju i zatim prolazimo kroz podatkovnu strukturu na iterativni način uzimajući jedan element na vrijeme.
Također smo vidjeli uvjetni tijek gdje opet zadržavamo jednu varijablu petlje i ponavljamo dio koda dok varijabla petlje ne ispuni uvjet. Kada su u pitanju pozivi funkcija, istražili smo i iterativni pristup za pozive funkcija.
U ovom vodiču raspravljat ćemo o drugačijem pristupu programiranju, tj. rekurzivnom pristupu.
Što je rekurzija u Javi?
Rekurzija je proces kojim funkcija ili metoda uvijek iznova poziva samu sebe. Ova funkcija koja se uvijek iznova poziva izravno ili neizravno naziva se "rekurzivna funkcija".
Vidjet ćemo razne primjere za razumijevanje rekurzije. Sada da vidimo sintaksu rekurzije.
Sintaksa rekurzije
Svaka metoda koja implementira rekurziju ima dva osnovna dijela:
- Poziv metode koja može samu sebe nazvati, tj. rekurzivna
- Preduvjet koji će zaustaviti rekurziju.
Imajte na umu da je preduvjet neophodan za svaku rekurzivnu metodu jer, ako ne razbitirekurzija tada će nastaviti raditi beskonačno i rezultirati preljevom stoga.
Opća sintaksa rekurzije je sljedeća:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Imajte na umu da se preduvjet također naziva osnovno stanje. Raspravit ćemo više o osnovnom stanju u sljedećem odjeljku.
Razumijevanje rekurzije u Javi
U ovom odjeljku pokušat ćemo razumjeti proces rekurzije i vidjeti kako se odvija. Naučit ćemo o osnovnom uvjetu, preljevu stoga i vidjeti kako se određeni problem može riješiti rekurzijom i sličnim detaljima.
Osnovni uvjet rekurzije
Dok pišemo rekurzivni program, trebali bismo prvo dajte rješenje za osnovni slučaj. Tada veći problem izražavamo u terminima manjih problema.
Kao primjer, možemo uzeti klasični problem izračunavanja faktorijela broja. Zadani je broj n, moramo pronaći faktorijel od n označen s n!
Sada implementirajmo program za izračunavanje faktorijela n (n!) pomoću 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); } }Izlaz
U ovom programu možemo vidjeti da je uvjet (n=1) osnovni uvjet i kada se taj uvjet postigne, funkcija vraća 1 Drugi dio funkcije je rekurzivni poziv. Ali svaki put kad se pozove rekurzivna metoda, n se smanjuje za 1.
Dakle, možemo zaključiti da će u konačnici vrijednost n postati 1 ili manja od 1 i u ovom trenutkutočka, metoda će vratiti vrijednost 1. Ovaj osnovni uvjet će biti dostignut i funkcija će se zaustaviti. Imajte na umu da vrijednost n može biti bilo što sve dok zadovoljava osnovni uvjet.
Rješavanje problema korištenjem rekurzije
Osnovna ideja iza korištenja rekurzije je izraziti veći problem u terminima manjih problema. Također, moramo dodati jedan ili više osnovnih uvjeta kako bismo mogli izaći iz rekurzije.
Ovo je već pokazano u gornjem primjeru faktorijela. U ovom programu smo faktorijel n (n!) izrazili u smislu manjih vrijednosti i imali osnovni uvjet (n =1) tako da kada n dosegne 1, možemo napustiti rekurzivnu metodu.
Pogreška prekoračenja stoga u rekurziji
Svjesni smo da kada se pozove bilo koja metoda ili funkcija, stanje funkcije pohranjuje se na stog i dohvaća se kada se funkcija vrati. Stog se također koristi za rekurzivnu metodu.
Ali u slučaju rekurzije, problem bi se mogao pojaviti ako ne definiramo osnovni uvjet ili kada osnovni uvjet nekako nije postignut ili izvršen. Ako se ova situacija dogodi, može doći do prelijevanja stoga.
Razmotrimo sljedeći primjer faktorijelne notacije.
Ovdje smo dali pogrešan osnovni uvjet, 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); } }Dakle, kada je n>gt; 100 metoda će vratiti 1, ali rekurzija se neće zaustaviti. Vrijednost n nastavit će se smanjivati u nedoglednema drugog uvjeta da se to zaustavi. Ovo će se nastaviti sve dok se stog ne prelije.
Drugi slučaj je kada vrijednost n 100. U ovom slučaju također metoda nikada neće izvršiti osnovni uvjet i rezultirati preljevom stoga.
Primjeri rekurzije u Javi
U ovom odjeljku ćemo implementirati sljedeće primjere koristeći rekurzija.
#1) Fibonaccijev niz koji koristi rekurziju
Fibonaccijev niz je dat prema,
1,1,2,3,5,8,13,21, 34,55,…
Gornji niz pokazuje da je trenutni element zbroj prethodna dva elementa. Također, prvi element u Fibonaccijevom nizu je 1.
Dakle, općenito ako je n trenutni broj, tada je dan zbrojem (n-1) i (n-2). Budući da je trenutni element izražen u smislu prethodnih elemenata, ovaj problem možemo izraziti pomoću rekurzije.
Program za implementaciju Fibonaccijevog niza dan je u nastavku:
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) + " "); } } } Izlaz
#2) Provjerite je li broj palindrom pomoću rekurzije
Palindrom je niz koji je jednak kada čitajte ga slijeva nadesno ili zdesna nalijevo.
Za dan broj 121, vidimo da je jednak kada ga čitamo slijeva nadesno i zdesna nalijevo. Stoga je broj 121 palindrom.
Uzmimo još jedan broj, 1242. Kada ga čitamo s lijeva na desno, to je 1242, a kada se čita s desna na lijevo, čita se kao 2421. Dakle, ovo nije palindrom.
Miimplementirati program palindroma okretanjem znamenki brojeva i rekurzivno uspoređujući zadani broj s njegovom obrnutom reprezentacijom.
Program u nastavku implementira program za provjeru 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."); } } }Izlaz
#3) Obrnuta rekurzija niza Java
S obzirom na niz "Hello" moramo ga obrnuti tako da rezultirajući niz je “olleH”.
To se radi pomoću rekurzije. Počevši od posljednjeg znaka u nizu, rekurzivno ispisujemo svaki znak dok se svi znakovi u nizu ne potroše.
Program u nastavku koristi rekurziju za preokret zadanog 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); } } Izlaz
#4) Java rekurzija binarnog pretraživanja
Algoritam binarnog pretraživanja je poznati algoritam za pretraživanje. U ovom algoritmu, s obzirom na sortirani niz od n elemenata, tražimo u tom nizu dani ključni element. Na početku, dijelimo niz na dvije polovice pronalaženjem srednjeg elementa niza.
Zatim, ovisno o tome je li ključni mid, ograničavamo našu pretragu na prvu ili drugu polovicu niza. Na ovaj način se isti postupak ponavlja dok se ne pronađe lokacija ključnih elemenata.
Ovdje ćemo implementirati ovaj algoritam korištenjem 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); } } Izlaz
#5) Pronađite minimalnu vrijednost u nizu pomoću rekurzije
Koristeći rekurziju također možemo pronaći minimalnu vrijednost u nizu.
TheJava program za pronalaženje minimalne vrijednosti u nizu dan je ispod.
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) + "\n"); } }Izlaz
Ovo su neki od primjeri rekurzije. Osim ovih primjera, mnogi drugi problemi u softveru mogu se implementirati korištenjem rekurzivnih tehnika.
Vrste rekurzije
Rekurzija ima dvije vrste na temelju toga kada se upućuje poziv rekurzivna metoda.
Oni su:
#1) Repna rekurzija
Kada je poziv rekurzivne metode zadnja izjava izvršava se unutar rekurzivne metode, naziva se "Repna rekurzija".
U repnoj rekurziji, naredba rekurzivnog poziva obično se izvršava zajedno s naredbom return metode.
opća sintaksa za repnu rekurziju dana je ispod:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Glavna rekurzija
Glavna rekurzija je svaki rekurzivni pristup koji nije repna rekurzija. Dakle, čak i opća rekurzija je rekurzija unaprijed.
Sintaksa rekurzije glave je sljedeća:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Rekurzija naspram iteracije u Javi
| Rekurzija | Iteracija |
|---|---|
| Rekurzija je proces u kojem metoda sama sebe poziva više puta dok se ne ispuni osnovni uvjet. | Iteracija je proces kojim se dio koda opetovano izvršava konačni broj puta ili dok se ne ispuni uvjet. |
| Je li aplikacija za funkcije. | Je li primjenjivo for petlje. |
| Dobro radi zamanja veličina koda. | Dobro radi za veću veličinu koda. |
| Koristi više memorije jer se svaki rekurzivni poziv gura na stog | Relativno manje memorije se koristi. |
| Teško za otklanjanje pogrešaka i održavanje | Lakše za otklanjanje pogrešaka i održavanje |
| Rezultira preljevom stoga ako baza uvjet nije naveden ili nije postignut. | Može se izvršavati beskonačno, ali će na kraju zaustaviti izvršenje s bilo kojom pogreškom memorije |
| Vremenska složenost je vrlo visoka. | Vremenska složenost je relativno niža. |
Često postavljana pitanja
P #1) Kako rekurzija radi u Javi?
Odgovor: U rekurziji, rekurzivna funkcija sama sebe poziva više puta dok se ne zadovolji osnovni uvjet. Memorija za pozvanu funkciju gura se na stog na vrhu memorije za pozivajuću funkciju. Za svaki poziv funkcije izrađuje se zasebna kopija lokalnih varijabli.
P #2) Zašto se koristi rekurzija?
Odgovor: Rekurzija se koristi za rješavanje onih problema koji se mogu rastaviti na manje i cijeli problem se može izraziti u terminima manjeg problema.
Rekurzija se također koristi za one probleme koji su previše kompleks koji treba riješiti korištenjem iterativnog pristupa. Osim problema za koje vremenska složenost nije problem, koristite rekurziju.
P #3) Koje su prednostiRekurzija?
Odgovor:
Prednosti rekurzije uključuju:
- Rekurzija smanjuje redundantne pozive funkcije.
- Rekurzija nam omogućuje jednostavno rješavanje problema u usporedbi s iterativnim pristupom.
P #4) Što je bolje – rekurzija ili iteracija?
Odgovor: Rekurzija ponavlja pozive dok se ne dosegne osnovna funkcija. Stoga postoji opterećenje memorije jer se memorija za svaki poziv funkcije gura na stog.
Iteracija s druge strane nema puno opterećenja memorije. Izvršenje rekurzije je sporije od iterativnog pristupa. Rekurzija smanjuje veličinu koda dok iterativni pristup čini kod velikim.
P #5) Koje su prednosti rekurzije u odnosu na iteraciju?
Odgovor:
- Rekurzija čini kod jasnijim i kraćim.
- Rekurzija je bolja od iterativnog pristupa za probleme poput Hanojskog tornja, stabla traversals, itd.
- Kako svaki poziv funkcije ima memoriju gurnutu na stog, rekurzija koristi više memorije.
- Izvedba rekurzije je sporija od iterativnog pristupa.
Zaključak
Rekurzija je vrlo važan koncept u softveru bez obzira na programski jezik. Rekurzija se uglavnom koristi u rješavanju problema strukture podataka kao što su hanojski tornjevi, obilaženja stabala, povezani popisi itd. Iako zahtijeva više memorije,rekurzija čini kôd jednostavnijim i jasnijim.
Istražili smo sve o rekurziji u ovom vodiču. Također smo implementirali brojne primjere programiranja za bolje razumijevanje koncepta.