Ang Malalim na Tutorial na ito sa Recursion sa Java ay nagpapaliwanag kung ano ang Recursion na may mga Halimbawa, Uri, at Mga Kaugnay na Konsepto. Sinasaklaw din nito ang Recursion Vs Iteration:
Mula sa aming mga naunang tutorial sa Java, nakita namin ang umuulit na diskarte kung saan nagdedeklara kami ng isang loop at pagkatapos ay tumawid sa isang istraktura ng data sa isang umuulit na paraan sa pamamagitan ng pagkuha ng isang elemento sa isang oras.
Nakita rin namin ang conditional flow kung saan muli naming pinapanatili ang isang loop variable at inuulit ang isang piraso ng code hanggang ang loop variable ay matugunan ang kundisyon. Pagdating sa mga function na tawag, ginalugad din namin ang umuulit na diskarte para sa mga function na tawag.
Sa tutorial na ito, tatalakayin natin ang ibang diskarte sa programming i.e. ang Recursive approach.
Ano ang Recursion Sa Java?
Ang recursion ay isang proseso kung saan paulit-ulit na tinatawag ng isang function o isang paraan ang sarili nito. Ang function na ito na paulit-ulit na tinatawag na direkta o hindi direkta ay tinatawag na "recursive function".
Makakakita tayo ng iba't ibang halimbawa upang maunawaan ang recursive. Ngayon tingnan natin ang syntax ng recursion.
Recursion Syntax
Anumang paraan na nagpapatupad ng Recursion ay may dalawang pangunahing bahagi:
- Paraan ng tawag na maaaring tumawag sa sarili nito i.e. recursive
- Isang paunang kondisyon na hihinto sa recursion.
Tandaan na ang isang paunang kondisyon ay kinakailangan para sa anumang recursive na paraan bilang, kung hindi namin gagawin basagin angrecursion pagkatapos ay patuloy itong tatakbo nang walang hanggan at magreresulta sa isang stack overflow.
Ang pangkalahatang syntax ng recursion ay ang sumusunod:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Tandaan na ang precondition ay tinatawag din batayang kondisyon. Tatalakayin pa natin ang tungkol sa batayang kundisyon sa susunod na seksyon.
Pag-unawa sa Recursion Sa Java
Sa seksyong ito, susubukan naming maunawaan ang proseso ng recursion at tingnan kung paano ito nagaganap. Malalaman natin ang tungkol sa batayang kondisyon, stack overflow, at tingnan kung paano malulutas ang isang partikular na problema gamit ang recursion at iba pang mga detalye.
Recursion Base Condition
Habang isinusulat ang recursive program, dapat nating ibigay muna ang solusyon para sa base case. Pagkatapos ay ipinapahayag namin ang mas malaking problema sa mga tuntunin ng mas maliliit na problema.
Bilang isang halimbawa, maaari kaming kumuha ng klasikong problema sa pagkalkula ng factorial ng isang numero. Dahil sa isang numero n, kailangan nating maghanap ng factorial ng n na tinutukoy ng n!
Ngayon, ipatupad natin ang programa para kalkulahin ang n factorial (n!) gamit ang recursion.
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
Sa program na ito, makikita natin na ang kundisyon (n=1) ay ang batayang kundisyon at kapag naabot ang kundisyong ito, ang function ay nagbabalik ng 1 Ang ibang bahagi ng function ay ang recursive na tawag. Ngunit sa tuwing tatawagin ang recursive method, ang n ay nababawasan ng 1.
Kaya maaari nating tapusin na sa huli ang halaga ng n ay magiging 1 o mas mababa sa 1 at ditopoint, ang paraan ay magbabalik ng halaga 1. Ang batayang kondisyon na ito ay maaabot at ang function ay titigil. Tandaan na ang halaga ng n ay maaaring maging anuman basta't natutugunan nito ang batayang kondisyon.
Paglutas ng Problema Gamit ang Recursion
Ang pangunahing ideya sa likod ng paggamit ng recursion ay upang ipahayag ang mas malaking problema sa mga tuntunin ng mas maliliit na problema. Gayundin, kailangan nating magdagdag ng isa o higit pang batayang kundisyon para makaalis tayo sa recursion.
Naipakita na ito sa factorial na halimbawa sa itaas. Sa programang ito, ipinahayag namin ang n factorial (n!) sa mga tuntunin ng mas maliliit na halaga at nagkaroon ng batayang kundisyon (n =1) upang kapag umabot ang n sa 1, maaari naming ihinto ang recursive method.
Stack Overflow Error Sa Recursion
Alam namin na kapag tinawag ang anumang paraan o function, ang estado ng function ay iniimbak sa stack at kinukuha kapag bumalik ang function. Ginagamit din ang stack para sa recursive method.
Ngunit sa kaso ng recursion, maaaring magkaroon ng problema kung hindi namin tinukoy ang batayang kundisyon o kapag ang batayang kundisyon ay hindi naabot o naisakatuparan. Kung mangyari ang sitwasyong ito, maaaring lumitaw ang stack overflow.
Isaalang-alang natin ang halimbawa sa ibaba ng factorial notation.
Dito nagbigay kami ng maling baseng kundisyon, 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); } }Kaya kapag n > 100 ang pamamaraan ay magbabalik ng 1 ngunit ang recursion ay hindi titigil. Ang halaga ng n ay patuloy na bababa nang walang katiyakan gaya doonay walang ibang kundisyon para pigilan ito. Magpapatuloy ito hanggang sa umapaw ang stack.
Ang isa pang kaso ay kapag ang halaga ng n 100. Sa kasong ito, pati na rin ang pamamaraan ay hindi kailanman ipapatupad ang batayang kundisyon at magreresulta sa isang stack overflow.
Mga Halimbawa ng Recursion Sa Java
Sa seksyong ito, ipapatupad namin ang mga sumusunod na halimbawa gamit ang recursion.
#1) Fibonacci Series Gamit ang Recursion
Ang Fibonacci series ay ibinibigay ng,
1,1,2,3,5,8,13,21, 34,55,…
Ipinapakita ng sequence sa itaas na ang kasalukuyang elemento ay ang kabuuan ng nakaraang dalawang elemento. Gayundin, ang unang elemento sa seryeng Fibonacci ay 1.
Kaya sa pangkalahatan kung n ang kasalukuyang numero, ito ay ibinibigay ng kabuuan ng (n-1) at (n-2). Dahil ang kasalukuyang elemento ay ipinahayag sa mga tuntunin ng mga nakaraang elemento, maaari naming ipahayag ang problemang ito gamit ang recursion.
Ibinigay sa ibaba ang program para ipatupad ang seryeng Fibonacci:
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) + " "); } } } Output
#2) Suriin Kung Ang Numero Ay Palindrome Gamit ang Recursion
Ang palindrome ay isang sequence na pantay kapag tayo basahin ito mula kaliwa pakanan o kanan pakaliwa.
Sa isang numerong 121, makikita natin na kapag binasa natin ito mula kaliwa pakanan at kanan pakaliwa, ito ay pantay. Kaya naman ang numero 121 ay isang palindrome.
Kunin natin ang isa pang numero, 1242. Kapag binasa natin ito mula kaliwa hanggang kanan ito ay 1242 at kapag binasa mula kanan pakaliwa ito ay magiging 2421. Kaya hindi ito isang palindrome.
Kamiipatupad ang palindrome program sa pamamagitan ng pag-reverse ng mga digit ng mga numero at recursively na ihambing ang ibinigay na numero sa reverse representation nito.
Ang programa sa ibaba ay nagpapatupad ng program upang suriin ang palindrome.
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."); } } }Output
#3) Reverse String Recursion Java
Binigyan ng string na “Hello” kailangan nating baligtarin ito upang ang Ang resultang string ay “olleH”.
Ginagawa ito gamit ang recursion. Simula sa huling character sa string, paulit-ulit naming ipi-print ang bawat character hanggang maubos ang lahat ng character sa string.
Ang programa sa ibaba ay gumagamit ng recursion upang baligtarin ang isang ibinigay na string.
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); } } Output
#4) Binary Search Java Recursion
Ang binary search algorithm ay isang sikat na algorithm para sa paghahanap. Sa algorithm na ito, na binigyan ng pinagsunod-sunod na hanay ng n elemento, hinahanap namin ang array na ito para sa ibinigay na pangunahing elemento. Sa simula, hinahati namin ang array sa dalawang hati sa pamamagitan ng paghahanap sa mid element ng array.
Pagkatapos, depende kung ang key mid ay nililimitahan namin ang aming paghahanap sa una o ikalawang kalahati ng array. Sa ganitong paraan mauulit ang parehong proseso hanggang sa matagpuan ang lokasyon ng mga pangunahing elemento.
Ipapatupad namin ang algorithm na ito gamit ang recursion dito.
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) Maghanap ng Minimum na Value Sa Array Gamit ang Recursion
Gamit ang recursion mahahanap din natin ang minimum na value sa array.
AngAng Java program upang mahanap ang pinakamababang halaga sa array ay ibinibigay sa ibaba.
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
Ito ang ilan sa ang mga halimbawa ng recursion. Bukod sa mga halimbawang ito, maraming iba pang problema sa software ang maaaring ipatupad gamit ang mga recursive technique.
Mga Uri ng Recursion
Ang recursion ay may dalawang uri batay sa kung kailan ginawa ang tawag sa ang recursive method.
Sila ay:
#1) Tail Recursion
Kapag ang tawag sa recursive method ay ang huling statement isinagawa sa loob ng recursive method, ito ay tinatawag na "Tail Recursion".
Sa tail recursion, ang recursive call statement ay karaniwang ginagawa kasama ng return statement ng method.
Ang Ang pangkalahatang syntax para sa tail recursion ay ibinigay sa ibaba:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Head Recursion
Ang head recursion ay anumang recursive na diskarte na hindi isang tail recursion. Kaya kahit na ang pangkalahatang recursion ay nauuna sa recursion.
Ang syntax ng head recursion ay ang sumusunod:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Recursion Vs Iteration Sa Java
| Recursion | Iteration |
|---|---|
| Ang recursion ay isang proseso kung saan paulit-ulit na tinatawag ng isang method ang sarili hanggang sa matugunan ang isang batayang kundisyon. | Ang iteration ay isang proseso kung saan paulit-ulit na isinasagawa ang isang piraso ng code para sa isang tiyak na bilang ng beses o hanggang sa matugunan ang isang kundisyon. |
| Ang application ba ay para sa mga function. | Aplikable ba para sa mga loop. |
| Gumagana nang maayos para samas maliit na laki ng code. | Mahusay na gumagana para sa mas malaking laki ng code. |
| Gumagamit ng mas maraming memory habang ang bawat recursive na tawag ay itinutulak sa stack | Mas kaunting memorya ay ginagamit. |
| Mahirap i-debug at mapanatili | Mas madaling i-debug at mapanatili |
| Magreresulta sa stack overflow kung ang base hindi tinukoy o hindi naabot ang kundisyon. | Maaaring isagawa nang walang hanggan ngunit sa huli ay titigil sa pagpapatupad sa anumang mga error sa memorya |
| Napakataas ng pagiging kumplikado ng oras. | Ang pagiging kumplikado ng oras ay medyo nasa ibabang bahagi. |
Mga Madalas Itanong
Q #1) Paano gumagana ang Recursion sa Java?
Sagot: Sa recursion, paulit-ulit na tumatawag ang recursive function sa sarili hanggang sa masiyahan ang isang batayang kundisyon. Ang memorya para sa tinatawag na function ay itinutulak sa stack sa tuktok ng memorya para sa calling function. Para sa bawat function call, isang hiwalay na kopya ng mga lokal na variable ang ginagawa.
Q #2) Bakit ginagamit ang Recursion?
Sagot: Ginagamit ang recursion upang malutas ang mga problemang iyon na maaaring hatiin sa mas maliliit at ang buong problema ay maaaring ipahayag sa mga tuntunin ng isang mas maliit na problema.
Ginagamit din ang recursion para sa mga problemang iyon na masyadong kumplikadong lutasin gamit ang isang umuulit na diskarte. Bukod sa mga problema kung saan ang pagiging kumplikado ng oras ay hindi isang isyu, gumamit ng recursion.
Q #3) Ano ang mga pakinabang ngRecursion?
Sagot:
Kabilang sa mga benepisyo ng Recursion ang:
- Pinababawasan ng recursion ang paulit-ulit na pagtawag ng function.
- Pinapayagan kami ng recursion na malutas ang mga problema nang madali kapag inihambing sa umuulit na diskarte.
Q #4) Alin ang mas mahusay – Recursion o Iteration?
Sagot: Ang recursion ay gumagawa ng mga paulit-ulit na tawag hanggang sa maabot ang base function. Kaya mayroong memory overhead habang ang memorya para sa bawat function na tawag ay itinutulak sa stack.
Ang pag-ulit sa kabilang banda ay walang gaanong memory overhead. Ang pagpapatupad ng recursion ay mas mabagal kaysa sa umuulit na diskarte. Binabawasan ng recursion ang laki ng code habang ginagawang malaki ng umuulit na diskarte ang code.
Q #5) Ano ang Mga Bentahe ng Recursion kaysa sa Pag-ulit?
Sagot:
- Ang recursion ay ginagawang mas malinaw at mas maikli ang code.
- Ang recursion ay mas mahusay kaysa sa umuulit na diskarte para sa mga problema tulad ng Tower of Hanoi, tree traversals, atbp.
- Dahil ang bawat function na tawag ay may memory na itinutulak sa stack, ang Recursion ay gumagamit ng mas maraming memory.
- Ang pagganap ng recursion ay mas mabagal kaysa sa umuulit na diskarte.
Konklusyon
Ang recursion ay isang napakahalagang konsepto sa software anuman ang programming language. Ang recursion ay kadalasang ginagamit sa paglutas ng mga problema sa istruktura ng data tulad ng mga tower ng Hanoi, mga tree traversal, mga naka-link na listahan, atbp. Kahit na nangangailangan ito ng mas maraming memorya,ginagawang mas simple at malinaw ng recursion ang code.
Na-explore namin ang lahat tungkol sa Recursion sa tutorial na ito. Nagpatupad din kami ng maraming halimbawa ng programming para sa mas mahusay na pag-unawa sa konsepto.