Þetta ítarlega kennsluefni um endurkomu í Java útskýrir hvað er endurtekning með dæmum, gerðum og skyldum hugtökum. Það fjallar einnig um endurtekningu vs endurtekningu:
Úr fyrri námskeiðum okkar í Java höfum við séð endurtekna nálgun þar sem við lýsum yfir lykkju og förum síðan í gegnum gagnaskipulag á endurtekinn hátt með því að taka einn þátt á tíma.
Við höfum líka séð skilyrta flæðið þar sem við höldum aftur einni lykkjubreytu og endurtökum kóða þar til lykkjubreytan uppfyllir skilyrðið. Þegar kemur að aðgerðaköllum könnuðum við einnig endurtekna nálgun fyrir aðgerðaköll.
Í þessari kennslu munum við fjalla um aðra nálgun við forritun, þ.e. endurkvæma nálgunina.
Hvað er endurtekning í Java?
Recursion er ferli þar sem fall eða aðferð kallar sig aftur og aftur. Þessi aðgerð sem er kölluð aftur og aftur annað hvort beint eða óbeint er kölluð „endurkvæmt fall".
Við munum sjá ýmis dæmi til að skilja endurkomu. Nú skulum við sjá setningafræði endurtekningar.
Recursion setningafræði
Sérhver aðferð sem útfærir endurtekningu hefur tvo grunnhluta:
- Aðferðarkall sem getur kallað sig t.d. endurkvæmt
- Forsenda sem mun stöðva endurkomuna.
Athugaðu að forsenda er nauðsynleg fyrir hverja endurkvæma aðferð eins og ef við gerum það ekki brjótaendurtekningu þá mun það halda áfram að keyra endalaust og leiða til þess að stafla flæðir.
Almenn setningafræði endurtekningar er sem hér segir:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Athugið að forsenda er einnig kölluð grunn ástand. Við munum ræða meira um grunnskilyrðið í næsta kafla.
Skilningur á endurkomu í Java
Í þessum kafla munum við reyna að skilja endurkomuferlið og sjá hvernig það á sér stað. Við munum læra um grunnástandið, yfirflæði stafla og sjá hvernig hægt er að leysa tiltekið vandamál með endurkomu og öðrum slíkum smáatriðum.
Endurkoma grunnskilyrði
Á meðan við skrifum endurkvæma forritið ættum við að gefðu fyrst lausnina fyrir grunnmálið. Þá tjáum við stærra vandamálið í skilmálar af smærri vandamálum.
Sem dæmi, getum við tekið klassískt vandamál að reikna þáttatölu. Að gefnu númeri n, verðum við að finna þáttahlutfall af n táknað með n!
Nú skulum við útfæra forritið til að reikna út n þáttaþátt (n!) með endurkomu.
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); } }Úttak
Í þessu forriti getum við séð að skilyrðið (n=1) er grunnskilyrðið og þegar þessu ástandi er náð skilar fallið 1 Hinn hluti aðgerðarinnar er endurkvæma kallið. En í hvert sinn sem endurkvæma aðferðin er kölluð lækkar n um 1.
Þannig getum við ályktað að á endanum verði gildi n 1 eða minna en 1 og við þettalið mun aðferðin skila gildi 1. Þessu grunnskilyrði verður náð og aðgerðin hættir. Athugið að gildi n getur verið hvað sem er svo framarlega sem það uppfyllir grunnskilyrðið.
Vandamálalausn með endurkomu
Grunnhugmyndin á bak við notkun endurtekningar er að tjá stærra vandamálið m.t.t.t. minni vandamál. Einnig þurfum við að bæta við einni eða fleiri grunnskilyrðum svo við getum komist út úr endurtekningu.
Þetta var þegar sýnt í þáttadæminu hér að ofan. Í þessu forriti gáfum við n þáttinn (n!) í skilmálar af smærri gildum og höfðum grunnskilyrði (n =1) þannig að þegar n nær 1 getum við hætt endurkvæmu aðferðinni.
Stack Overflow Error In Recursion
Við erum meðvituð um að þegar einhver aðferð eða aðgerð er kölluð, er ástand fallsins geymt á staflanum og er sótt þegar fallið kemur aftur. Staflan er einnig notuð fyrir endurkvæmu aðferðina.
En ef um endurtekningu er að ræða gæti vandamál komið upp ef við skilgreinum ekki grunnskilyrðið eða þegar grunnskilyrðinu er einhvern veginn ekki náð eða framkvæmt. Ef þessi staða kemur upp gæti staflaflæðið komið upp.
Lítum á dæmið hér að neðan um þáttaskil.
Hér höfum við gefið rangt grunnskilyrði, 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); } }Svo þegar n > 100 mun aðferðin skila 1 en endurkoma hættir ekki. Gildi n mun halda áfram að lækka endalaust eins og þarer ekkert annað skilyrði til að stöðva það. Þetta mun halda áfram þar til staflan flæðir yfir.
Annað tilvik verður þegar gildi n 100. Í þessu tilviki mun aðferðin líka aldrei framkvæma grunnskilyrðið og leiða til yfirflæðis í stafla.
Endurtekningadæmi í Java
Í þessum hluta munum við útfæra eftirfarandi dæmi með því að nota endurtekning.
#1) Fibonacci röð með endurtekningu
Fibonacci röðin er gefin af,
1,1,2,3,5,8,13,21, 34,55,…
Röðin hér að ofan sýnir að núverandi þáttur er summan af fyrri þáttunum tveimur. Einnig er fyrsta þátturinn í Fibonacci röðinni 1.
Þannig að almennt ef n er núverandi tala, þá er hún gefin af summan af (n-1) og (n-2). Þar sem núverandi þáttur er gefinn upp í skilmálar af fyrri þáttum, getum við tjáð þetta vandamál með endurtekningu.
Forritið til að innleiða Fibonacci röðina er gefið upp hér að neðan:
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) Athugaðu hvort tala sé palindrome með endurkomu
Palindrome er röð sem er jöfn þegar við lesið það frá vinstri til hægri eða hægri til vinstri.
Gefið töluna 121 sjáum við að þegar við lesum hana frá vinstri til hægri og hægri til vinstri er hún jöfn. Þess vegna er talan 121 palindrome.
Tökum aðra tölu, 1242. Þegar við lesum hana frá vinstri til hægri er hún 1242 og þegar lesin er frá hægri til vinstri er hún 2421. Þannig er þetta ekki palindrome.
Viðinnleiða palindrome forritið með því að snúa við tölustöfum talna og bera saman tiltekna tölu við öfuga framsetningu þess.
Næsta forritið útfærir forritið til að athuga 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."); } } }Úttak
#3) Reverse String Recursion Java
Gefin streng „Halló“ verðum við að snúa honum við þannig að strengur sem myndast er “olleH”.
Þetta er gert með endurkomu. Byrjað er á síðasta stafnum í strengnum og við prentum hvern staf með endurhverfum hætti þar til allir stafirnir í strengnum eru uppurnir.
Nefnt forrit notar endurkomu til að snúa við tilteknum streng.
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
Tvíundarleitaralgrím er frægt reiknirit til að leita. Í þessari reiknirit, gefið flokkað fylki af n þáttum, leitum við í þetta fylki að tilteknu lykilatriði. Í upphafi skiptum við fylkinu í tvo helminga með því að finna miðhluta fylkisins.
Síðan fer eftir því hvort lykillinn midur takmörkum leit okkar í fyrri eða seinni hluta fylkisins. Þannig er sama ferlið endurtekið þar til staðsetning lykilþáttanna finnst.
Við munum innleiða þetta reiknirit með því að nota endurtekningu hér.
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) Finndu lágmarksgildi í fylki með því að nota endurkomu
Með því að nota endurkomu getum við líka fundið lágmarksgildi í fylkinu.
TheJava forrit til að finna lágmarksgildi í fylkinu er gefið upp hér að neðan.
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
Þetta eru nokkrar af dæmin um endurkomu. Fyrir utan þessi dæmi er hægt að útfæra fullt af öðrum vandamálum í hugbúnaðinum með endurkvæmri tækni.
Endurkvæmnitegundir
Endurtekning er tvenns konar sem byggist á því hvenær hringt er í endurkvæma aðferðina.
Þau eru:
#1) Tail Recursion
Þegar kallið á endurkvæmu aðferðina er síðasta staðhæfingin keyrð innan endurkvæmrar aðferðar, hún er kölluð „Tail Recursion“.
Í tail recursion er endurkvæma kalla yfirlýsingin venjulega keyrð ásamt return yfirlýsingu aðferðarinnar.
The tail recursion. almenn setningafræði fyrir hala endurkomu er gefin upp hér að neðan:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Höfuðsnúningur
Höfuðsnúningur er hvers kyns endurhverf nálgun sem er ekki afturhvarf. Þannig að jafnvel almenn endurkoma er á undan endurtekningu.
Syntax of head recursion er sem hér segir:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Recursion Vs Iteration In Java
| Recursion | Iteration |
|---|---|
| Recursion er ferli þar sem aðferð kallar sig endurtekið þar til grunnskilyrði er uppfyllt. | Iteration er ferli þar sem stykki af kóða er endurtekið keyrt í takmarkaðan fjölda sinnum eða þar til skilyrði er uppfyllt. |
| Er forritið fyrir föll. | Á við. fyrir lykkjur. |
| Virkar vel fyrirminni kóðastærð. | Virkar vel fyrir stærri kóðastærð. |
| Nýtir meira minni þar sem hverju endurkvæma símtali er ýtt í staflan | Tiltölulega minna minni er notað. |
| Erfitt að kemba og viðhalda | Auðveldara að kemba og viðhalda |
| Legir af sér staflaflæði ef grunnurinn skilyrði er ekki tilgreint eða ekki náð. | Gæti keyrt óendanlega en mun að lokum stöðva framkvæmd með minnisvillum |
| Tímaflæki er mjög mikill. | Tímaflókinn er tiltölulega í lægri kantinum. |
Algengar spurningar
Sp. #1) Hvernig virkar endurtekning í Java?
Svar: Í endurkomu kallar endurkvæma fallið sig endurtekið þar til grunnskilyrði er uppfyllt. Minninu fyrir aðgerðina sem kallað er á er ýtt á staflan efst á minninu fyrir aðgerðina sem hringt er í. Fyrir hvert fallkall er sérstakt afrit af staðbundnum breytum gert.
Sp. #2) Hvers vegna er endurtekning notuð?
Svar: Endurkoma er notað til að leysa þau vandamál sem hægt er að skipta niður í smærri og allt vandamálið má tjá sem smærra vandamál.
Recursion er einnig notað fyrir þau vandamál sem eru of flókið til að leysa með endurtekinni nálgun. Fyrir utan vandamálin þar sem flókið tíma skiptir ekki máli, notaðu endurkomu.
Sp. #3) Hver er ávinningurinn afEndurtekning?
Svar:
Ávinningurinn af endurtekningu eru meðal annars:
- Endurtekning dregur úr óþarfa símtölum af virkni.
- Endurtekning gerir okkur kleift að leysa vandamál auðveldlega í samanburði við endurtekna nálgun.
Sp #4) Hvort þeirra er betra – endurtekið eða endurtekið?
Svar: Recursion hringir ítrekað þar til grunnaðgerðinni er náð. Þannig er minniskostnaður þar sem minni fyrir hvert fallkall er ýtt á staflan.
Endurtekning hefur aftur á móti ekki mikið minniskostnaður. Framkvæmd endurtekningar er hægari en endurtekin nálgun. Endurtekning minnkar stærð kóðans á meðan endurtekin nálgun gerir kóðann stóran.
Sp. #5) Hverjir eru kostir endurtekningar fram yfir endurtekningu?
Svar:
- Endurtekning gerir kóðann skýrari og styttri.
- Endurtekning er betri en endurtekin nálgun fyrir vandamál eins og Hanoi-turninn, tré yfirferð o.s.frv.
- Þar sem minni er ýtt inn í staflann í hverju fallkalli, notar endurtekningar meira minni.
- Afköst endurtekningar eru hægari en endurtekningaraðferðin.
Niðurstaða
Recursion er mjög mikilvægt hugtak í hugbúnaði óháð forritunarmáli. Endurtekning er aðallega notuð til að leysa vandamál með uppbyggingu gagna eins og turna í Hanoi, yfirferð trjáa, tengda lista osfrv. Þó það þurfi meira minni,endurtekning gerir kóða einfaldari og skýrari.
Við höfum kannað allt um endurtekningu í þessari kennslu. Við höfum einnig innleitt fjölmörg forritunardæmi til að skilja hugtakið betur.