Ovaj detaljni vodič o rekurziji u Javi objašnjava što je rekurzija s primjerima, tipovima i srodnim konceptima. Takođe pokriva rekurziju protiv iteracije:
Iz naših ranijih tutorijala u Javi, vidjeli smo iterativni pristup u kojem deklariramo petlju, a zatim prelazimo kroz strukturu podataka na iterativni način uzimajući jedan element na vrijeme.
Također smo vidjeli uvjetni tok gdje opet zadržavamo jednu varijablu petlje i ponavljamo dio koda dok varijabla petlje ne ispuni uslov. Kada je riječ o pozivima funkcija, istražili smo iterativni pristup za pozive funkcija.
U ovom vodiču ćemo raspravljati o drugačijem pristupu programiranju, tj. rekurzivnom pristupu.
Šta je rekurzija u Javi?
Rekurzija je proces kojim funkcija ili metoda poziva sebe iznova i iznova. Ova funkcija koja se poziva iznova i iznova, direktno ili indirektno, naziva se “rekurzivna funkcija”.
Vidjet ćemo razne primjere da bismo razumjeli rekurziju. Sada da vidimo sintaksu rekurzije.
Sintaksa rekurzije
Svaka metoda koja implementira rekurziju ima dva osnovna dijela:
- Poziv metode koji se može nazvati, tj. rekurzivni
- Preduslov koji će zaustaviti rekurziju.
Napominjemo da je preduslov neophodan za bilo koju rekurzivnu metodu, jer ako ne break therekurzija onda će nastaviti da radi beskonačno i rezultirati prelivanjem steka.
Opšta sintaksa rekurzije je sljedeća:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Primijetite da se preduslov također naziva osnovno stanje. Više ćemo razgovarati o osnovnom stanju u sljedećem odjeljku.
Razumijevanje rekurzije u Javi
U ovom odeljku ćemo pokušati razumjeti proces rekurzije i vidjeti kako se on odvija. Naučit ćemo o osnovnom stanju, prekoračenju steka i vidjeti kako se određeni problem može riješiti rekurzijom i drugim 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 faktorijala broja. S obzirom na broj n, moramo pronaći faktorijel od n označen sa n!
Sada implementirajmo program za izračunavanje n faktorijala (n!) korištenjem 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); } }Output
U ovom programu možemo vidjeti da je uvjet (n=1) osnovni uvjet i kada se ovaj uvjet postigne, funkcija vraća 1 Drugi dio funkcije je rekurzivni poziv. Ali svaki put kada se pozove rekurzivna metoda, n se smanjuje za 1.
Tako možemo zaključiti da će na kraju vrijednost n postati 1 ili manja od 1 i na ovomtač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 koja sve dok zadovoljava osnovni uvjet.
Rješavanje problema pomoću rekurzije
Osnovna ideja iza upotrebe rekurzije je izraziti veći problem u smislu manji problemi. Također, moramo dodati jedan ili više osnovnih uvjeta kako bismo mogli izaći iz rekurzije.
Ovo je već demonstrirano u gornjem primjeru faktorijala. U ovom programu, izrazili smo faktorijel n (n!) u terminima manjih vrijednosti i imali smo osnovni uvjet (n =1) tako da kada n dostigne 1, možemo napustiti rekurzivnu metodu.
Greška prekoračenja steka u rekurziji
Svjesni smo da kada se pozove bilo koja metoda ili funkcija, stanje funkcije se pohranjuje u stog i dohvaća se kada se funkcija vrati. Stek se koristi i za rekurzivnu metodu.
Ali u slučaju rekurzije, može doći do problema ako ne definiramo osnovni uvjet ili kada osnovni uvjet na neki način nije dostignut ili izvršen. Ako dođe do ove situacije, može doći do prekoračenja steka.
Razmotrimo donji primjer faktorijalne 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 > 100 metoda će vratiti 1, ali rekurzija se neće zaustaviti. Vrijednost n će nastaviti da se smanjuje na neodređeno vrijemenema drugog uslova da se to zaustavi. Ovo će se nastaviti do prekoračenja steka.
Drugi slučaj će biti kada vrijednost n 100. U ovom slučaju, također, metoda nikada neće izvršiti osnovni uvjet i rezultirati prekoračenjem steka.
Primjeri rekurzije u Javi
U ovom dijelu ćemo implementirati sljedeće primjere koristeći rekurzija.
#1) Fibonačijev niz koji koristi rekurziju
Fibonačijev niz je dat sa,
1,1,2,3,5,8,13,21, 34,55,…
Navedeni niz pokazuje da je trenutni element zbir prethodna dva elementa. Takođe, prvi element u Fibonačijevom nizu je 1.
Dakle, generalno, ako je n trenutni broj, onda je dat zbirom (n-1) i (n-2). Kako je trenutni element izražen u terminima prethodnih elemenata, ovaj problem možemo izraziti pomoću rekurzije.
Program za implementaciju Fibonačijevog niza je dat 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 s lijeva na desno ili zdesna na lijevo.
S obzirom na broj 121, vidimo da kada ga čitamo s lijeva na desno i zdesna na lijevo, on je jednak. Dakle, broj 121 je palindrom.
Uzmimo drugi 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.
Miimplementirajte program palindroma obrnuvši znamenke brojeva i rekurzivno uporedite dati broj sa obrnutim prikazom.
Donji program 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
Dati niz “Hello” moramo ga obrnuti tako da rezultirajući niz je “olleH”.
Ovo se radi pomoću rekurzije. Počevši od posljednjeg znaka u nizu rekurzivno ispisujemo svaki znak sve dok se svi znakovi u nizu ne iscrpe.
Program ispod koristi rekurziju da preokrene dati niz.
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 ovaj niz za dati ključni element. U početku, dijelimo niz na dvije polovine pronalaženjem srednjeg elementa niza.
Zatim u zavisnosti od toga da li je ključna sredina ograničavamo našu pretragu u prvoj ili drugoj polovini niza. Na ovaj način se isti proces ponavlja dok se ne pronađe lokacija ključnih elemenata.
Ovaj algoritam ćemo implementirati koristeći rekurziju ovdje.
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 je dat 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 primjere rekurzije. Osim ovih primjera, mnogo drugih problema u softveru može se implementirati korištenjem rekurzivnih tehnika.
Tipovi rekurzije
Rekurzija je dva tipa zasnovana na tome kada se upućuje poziv rekurzivna metoda.
Oni su:
#1) Repna rekurzija
Kada je poziv rekurzivne metode posljednji izraz Izvršena unutar rekurzivne metode, naziva se “rekurzija repa”.
U repnoj rekurziji, naredba rekurzivnog poziva se obično izvršava zajedno s povratnom naredbom metode.
Opća sintaksa za repnu rekurziju je data u nastavku:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Rekurzija glave
Rekurzija glave je svaki rekurzivni pristup koji nije repna rekurzija. Dakle, čak je i opća rekurzija ispred rekurzije.
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 poziva sebe više puta dok se ne ispuni osnovni uvjet. | Iteracija je proces kojim se dio koda uzastopno izvršava konačan broj puta ili dok se ne ispuni uvjet. |
| Je li aplikacija za funkcije. | Primjenjiva je za petlje. |
| Dobro radi zamanja veličina koda. | Dobro radi za veću veličinu koda. |
| Koristi više memorije kako se svaki rekurzivni poziv gura u stog | Relativno manje memorije se koristi. |
| Teško za otklanjanje grešaka i održavanje | Lakše za otklanjanje grešaka i održavanje |
| Rezultira prekoračenjem steka ako je baza uslov nije specificiran ili nije postignut. | Može se izvršavati beskonačno, ali će na kraju zaustaviti izvršenje sa bilo kakvim memorijskim greškama |
| Vremenska složenost je vrlo visoka. | Vremenska složenost je relativno na nižoj strani. |
Često postavljana pitanja
P #1) Kako rekurzija radi u Javi?
Odgovor: U rekurziji, rekurzivna funkcija poziva samu sebe više puta sve dok osnovni uvjet nije zadovoljen. Memorija za pozvanu funkciju se gura u stog na vrhu memorije za funkciju koja poziva. Za svaki poziv funkcije pravi se posebna kopija lokalnih varijabli.
Q #2) Zašto se koristi rekurzija?
Odgovor: Rekurzija se koristi za rješavanje onih problema koji se mogu podijeliti 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 kompleksa koji se rješava korištenjem iterativnog pristupa. Osim problema za koje složenost vremena nije problem, koristite rekurziju.
P #3) Koje su prednostiRekurzija?
Odgovor:
Prednosti rekurzije uključuju:
- Rekurzija smanjuje suvišno pozivanje funkcije.
- Rekurzija nam omogućava da lako rješavamo probleme u poređenju s iterativnim pristupom.
P #4) Što je bolje – rekurzija ili iteracija?
Odgovor: Rekurzija vrši ponovljene pozive dok se ne dostigne osnovna funkcija. Prema tome, postoji nadopterećenje memorije jer se memorija za svaki poziv funkcije gura u stog.
Iteracija s druge strane nema mnogo memorije. Izvršenje rekurzije je sporije od iterativnog pristupa. Rekurzija smanjuje veličinu koda dok iterativni pristup čini kôd velikim.
Q #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 Hanojske kule, stabla prelasci, itd.
- Kako svaki poziv funkcije ima memoriju gurnutu u 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 tornjevi u Hanoju, obilaženje stabala, povezane liste, itd. Iako zahtijeva više memorije,rekurzija čini kod jednostavnijim i jasnijim.
Istražili smo sve o rekurziji u ovom vodiču. Također smo implementirali brojne primjere programiranja za bolje razumijevanje koncepta.