Ky tutorial i thelluar mbi rekursionin në Java shpjegon se çfarë është rekursioni me shembuj, lloje dhe koncepte të ngjashme. Ai gjithashtu mbulon Recursion vs Iteration:
Nga mësimet tona të mëparshme në Java, ne kemi parë qasjen përsëritëse ku ne deklarojmë një lak dhe më pas kalojmë nëpër një strukturë të dhënash në një mënyrë përsëritëse duke marrë një element në një kohë.
Ne kemi parë gjithashtu rrjedhën e kushtëzuar ku përsëri mbajmë një variabël lak dhe përsërisim një pjesë të kodit derisa ndryshorja e ciklit të plotësojë kushtin. Kur bëhet fjalë për thirrjet e funksioneve, ne kemi eksploruar edhe qasjen përsëritëse për thirrjet e funksioneve.
Në këtë tutorial, ne do të diskutojmë një qasje të ndryshme ndaj programimit, pra qasjen rekursive.
Çfarë është rekursioni në Java?
Rekursioni është një proces me anë të të cilit një funksion ose një metodë thërret veten vazhdimisht. Ky funksion që thirret vazhdimisht ose direkt ose indirekt quhet "funksion rekurziv".
Do të shohim shembuj të ndryshëm për të kuptuar rekursionin. Tani le të shohim sintaksën e rekursionit.
Sintaksa e rekursionit
Çdo metodë që zbaton rekursionin ka dy pjesë themelore:
- Thirrja e metodës që mund ta quajë veten d.m.th. rekurzive
- Një parakusht që do të ndalojë rekursionin.
Vini re se një parakusht është i nevojshëm për çdo metodë rekursive pasi, nëse nuk e bëjmë thyejnërekursion atëherë ai do të vazhdojë të funksionojë pafundësisht dhe do të rezultojë në një tejmbushje të stivit.
Sintaksa e përgjithshme e rekursionit është si më poshtë:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Vini re se parakushti quhet gjithashtu gjendja bazë. Ne do të diskutojmë më shumë rreth kushtit bazë në seksionin tjetër.
Kuptimi i rekursionit në Java
Në këtë seksion, ne do të përpiqemi të kuptojmë procesin e rekursionit dhe të shohim se si ndodh ai. Ne do të mësojmë rreth kushtit bazë, tejmbushjes së stivës dhe do të shohim se si mund të zgjidhet një problem i veçantë me rekursion dhe detaje të tjera të tilla.
Kushti bazë i rekursionit
Gjatë shkrimit të programit rekurziv, ne duhet së pari jepni zgjidhjen për rastin bazë. Më pas e shprehim problemin më të madh në terma të problemeve më të vogla.
Si shembull, mund të marrim një problem klasik të llogaritjes së faktorialit të një numri. Duke pasur një numër n, duhet të gjejmë një faktorial prej n të shënuar me n!
Tani le të zbatojmë programin për të llogaritur faktorialin n (n!) duke përdorur rekursionin.
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); } }Prodhimi
Në këtë program, ne mund të shohim se kushti (n=1) është kushti bazë dhe kur arrihet ky kusht, funksioni kthen 1 Pjesa tjetër e funksionit është thirrja rekursive. Por sa herë që thirret metoda rekursive, n zvogëlohet me 1.
Kështu mund të konkludojmë se në fund vlera e n do të bëhet 1 ose më e vogël se 1 dhe në këtëpikë, metoda do të kthejë vlerën 1. Ky kusht bazë do të arrihet dhe funksioni do të ndalojë. Vini re se vlera e n mund të jetë çdo gjë për sa kohë që plotëson kushtin bazë.
Zgjidhja e problemit duke përdorur rekursionin
Ideja bazë pas përdorimit të rekursionit është të shprehni problemin më të madh në termat e probleme më të vogla. Gjithashtu, duhet të shtojmë një ose më shumë kushte bazë në mënyrë që të mund të dalim nga rekursioni.
Kjo u demonstrua tashmë në shembullin faktorial të mësipërm. Në këtë program, ne shprehëm n faktorialin (n!) në terma të vlerave më të vogla dhe kishim një kusht bazë (n =1) në mënyrë që kur n të arrijë 1, ne mund të dalim nga metoda rekursive.
Gabim i tejmbushjes së stivës në rekursion
Ne jemi të vetëdijshëm se kur thirret ndonjë metodë ose funksion, gjendja e funksionit ruhet në pirg dhe merret kur funksioni kthehet. Stack-i përdoret gjithashtu për metodën rekursive.
Por në rastin e rekursionit, një problem mund të ndodhë nëse nuk përcaktojmë kushtin bazë ose kur kushti bazë nuk arrihet ose ekzekutohet disi. Nëse kjo situatë ndodh, atëherë mund të lindë tejmbushja e pirgut.
Le të shqyrtojmë shembullin e mëposhtëm të shënimit faktorial.
Këtu kemi dhënë një kusht bazë të gabuar, 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); } }Pra, kur n > 100 metoda do të kthejë 1 por rekursioni nuk do të ndalet. Vlera e n-së do të vazhdojë të zvogëlohet pafundësisht si atjenuk është kusht tjetër për ta ndaluar atë. Kjo do të vazhdojë derisa pirgu të tejmbushet.
Një rast tjetër do të jetë kur vlera e n 100. Në këtë rast, metoda nuk do të ekzekutojë kurrë kushtin bazë dhe do të rezultojë në një tejmbushje të stivit.
Shembuj të rekursionit në Java
Në këtë seksion, ne do të zbatojmë shembujt e mëposhtëm duke përdorur rekursioni.
#1) Seritë Fibonacci duke përdorur rekursionin
Seria Fibonacci jepet nga,
1,1,2,3,5,8,13,21, 34,55,…
Sekuenca e mësipërme tregon se elementi aktual është shuma e dy elementëve të mëparshëm. Gjithashtu, elementi i parë në serinë Fibonacci është 1.
Pra në përgjithësi nëse n është numri aktual, atëherë ai jepet nga shuma e (n-1) dhe (n-2). Meqenëse elementi aktual shprehet në terma të elementeve të mëparshme, ne mund ta shprehim këtë problem duke përdorur rekursionin.
Programi për zbatimin e serisë Fibonacci është dhënë më poshtë:
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) + " "); } } } Dalja
#2) Kontrolloni nëse një numër është një palindrom duke përdorur rekursionin
Një palindrom është një sekuencë që është e barabartë kur ne lexoni atë nga e majta në të djathtë ose nga e djathta në të majtë.
Duke pasur parasysh numrin 121, shohim se kur e lexojmë nga e majta në të djathtë dhe nga e djathta në të majtë, ai është i barabartë. Prandaj numri 121 është një palindrom.
Le të marrim një numër tjetër, 1242. Kur e lexojmë nga e majta në të djathtë është 1242 dhe kur lexohet nga e djathta në të majtë lexohet si 2421. Pra, ky nuk është një palindrom.
Nezbatoni programin palindrom duke kthyer mbrapsht shifrat e numrave dhe krahasoni në mënyrë rekursive numrin e dhënë me paraqitjen e tij të kundërt.
Programi i mëposhtëm zbaton programin për të kontrolluar palindromin.
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."); } } }Dalja
#3) Rekursioni i vargut të kundërt Java
Duke dhënë një varg "Përshëndetje" ne duhet ta kthejmë atë në mënyrë që të vargu rezultues është "olleH".
Kjo bëhet duke përdorur rekursionin. Duke u nisur nga karakteri i fundit në varg, ne printojmë në mënyrë rekursive çdo karakter derisa të shteren të gjitha karakteret në varg.
Programi i mëposhtëm përdor rekursionin për të kthyer një varg të caktuar.
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); } } Dalja
#4) Kërkimi binar Java Rekursioni
Një algoritëm kërkimi binar është një algoritëm i famshëm për kërkim. Në këtë algoritëm, duke pasur parasysh një grup të renditur prej n elementësh, ne kërkojmë këtë grup për elementin kyç të dhënë. Në fillim, ne e ndajmë grupin në dy gjysma duke gjetur elementin e mesit të grupit.
Më pas, në varësi të faktit nëse çelësi është në mes, ne kufizojmë kërkimin tonë në gjysmën e parë ose të dytë të grupit. Në këtë mënyrë i njëjti proces përsëritet derisa të gjendet vendndodhja e elementeve kryesore.
Ne do ta zbatojmë këtë algoritëm duke përdorur rekursionin këtu.
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); } } Output
#5) Gjeni vlerën minimale në grup duke përdorur rekursionin
Duke përdorur rekursionin mund të gjejmë gjithashtu vlerën minimale në grup.
0> TëProgrami Java për të gjetur vlerën minimale në grup është dhënë më poshtë.
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"); } }Output
Këto janë disa nga shembujt e rekursionit. Përveç këtyre shembujve, shumë probleme të tjera në softuer mund të zbatohen duke përdorur teknika rekursive.
Llojet e rekursionit
Rekursioni është dy llojesh bazuar në kohën kur bëhet thirrja në metoda rekursive.
Ato janë:
#1) Rekursioni i bishtit
Kur thirrja në metodën rekursive është deklarata e fundit ekzekutuar brenda metodës rekursive, quhet "Tail Recursion".
Në rekursionin e fundit, deklarata e thirrjes rekursive zakonisht ekzekutohet së bashku me deklaratën kthyese të metodës.
The Sintaksa e përgjithshme për rekursionin e bishtit është dhënë më poshtë:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Rekursioni i kokës
Rekursioni i kokës është çdo qasje rekursive që nuk është rekursion i bishtit. Pra, edhe rekursioni i përgjithshëm është rekursion përpara.
Sintaksa e rekursionit të kokës është si më poshtë:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Rekursion kundër përsëritjes në Java
| Rekursioni | Përsëritja |
|---|---|
| Rekursioni është një proces ku një metodë thërret veten në mënyrë të përsëritur derisa të plotësohet një kusht bazë. | Përsëritja është një proces me të cilin një pjesë kodi ekzekutohet në mënyrë të përsëritur për një numër të fundëm herë ose derisa të plotësohet një kusht. |
| A është aplikacioni për funksionet. | A është e zbatueshme për sythe. |
| Funksionon mirë përmadhësia më e vogël e kodit. | Funksionon mirë për madhësinë më të madhe të kodit. |
| Përdor më shumë memorie pasi çdo thirrje rekursive shtyhet në pirg | Krahasisht më pak memorie përdoret. |
| Vështirë për të korrigjuar dhe mirëmbajtur | Më e lehtë për të korrigjuar dhe mirëmbajtur |
| Rezulton në tejmbushje të pirgut nëse baza kushti nuk është specifikuar ose nuk arrihet. | Mund të ekzekutohet pafundësisht, por përfundimisht do të ndalojë ekzekutimin me ndonjë gabim në memorie |
| Kompleksiteti kohor është shumë i lartë. | Kompleksiteti kohor është relativisht në anën e poshtme. |
Pyetjet e bëra më shpesh
P #1) Si funksionon Rekursioni në Java?
Përgjigje: Në rekursion, funksioni rekurziv thërret veten në mënyrë të përsëritur derisa të plotësohet një kusht bazë. Kujtesa për funksionin e thirrur shtyhet në pirg në krye të memories për funksionin thirrës. Për çdo thirrje funksioni, bëhet një kopje e veçantë e variablave lokale.
P #2) Pse përdoret Recursion?
Përgjigje: Rekursioni përdoret për të zgjidhur ato probleme që mund të ndahen në më të vogla dhe i gjithë problemi mund të shprehet në termat e një problemi më të vogël.
Rekursioni përdoret gjithashtu për ato probleme që janë shumë kompleks për t'u zgjidhur duke përdorur një qasje përsëritëse. Përveç problemeve për të cilat kompleksiteti kohor nuk është problem, përdorni rekursionin.
P #3) Cilat janë përfitimet eRekursioni?
Përgjigje:
Përfitimet e Rekursionit përfshijnë:
- Rekursioni redukton thirrjet e tepërta i funksionit.
- Rekursioni na lejon t'i zgjidhim problemet lehtësisht kur krahasohet me qasjen përsëritëse.
P #4) Cili është më i mirë - Rekursioni apo Përsëritja?
Përgjigje: Rekursioni bën thirrje të përsëritura derisa të arrihet funksioni bazë. Kështu ka një memorie të lartë pasi një memorie për çdo thirrje funksioni shtyhet në stek.
Përsëritja nga ana tjetër nuk ka shumë memorie të tepërt. Ekzekutimi i rekursionit është më i ngadalshëm se qasja përsëritëse. Rekursioni zvogëlon madhësinë e kodit ndërsa qasja përsëritëse e bën kodin të madh.
P #5) Cilat janë avantazhet e rekursionit ndaj përsëritjes?
Përgjigja:
- Rekursioni e bën kodin më të qartë dhe më të shkurtër.
- Rekursioni është më i mirë se qasja përsëritëse për probleme si Kulla e Hanoi, pema kalimet, etj.
- Meqë çdo thirrje funksioni ka memorie të shtyrë në stek, Rekursioni përdor më shumë memorie.
- Performanca e rekursionit është më e ngadaltë se qasja përsëritëse.
Përfundim
Rekursioni është një koncept shumë i rëndësishëm në softuer, pavarësisht nga gjuha e programimit. Rekursioni përdoret më së shumti në zgjidhjen e problemeve të strukturës së të dhënave si kullat e Hanoit, kalimet e pemëve, listat e lidhura, etj. Edhe pse kërkon më shumë memorie,rekursioni e bën kodin më të thjeshtë dhe më të qartë.
Ne kemi eksploruar gjithçka rreth Rekursionit në këtë tutorial. Ne kemi zbatuar edhe shembuj të shumtë programimi për një kuptim më të mirë të konceptit.