Mae'r Tiwtorial Manwl hwn ar Recursion yn Java yn Egluro beth yw Ailddigwyddiad gydag Enghreifftiau, Mathau, a Chysyniadau Cysylltiedig. Mae hefyd yn ymdrin â Recursion Vs Iteration:
O'n tiwtorialau cynharach yn Java, rydym wedi gweld y dull iteraidd lle rydym yn datgan dolen ac yna'n croesi trwy strwythur data mewn modd ailadroddol trwy gymryd un elfen yn tro.
Rydym hefyd wedi gweld y llif amodol lle eto rydym yn cadw un newidyn dolen ac yn ailadrodd darn o god nes bod y newidyn dolen yn cwrdd â'r amod. O ran galwadau ffwythiant, rydym hefyd wedi archwilio'r dull iterus ar gyfer galwadau ffwythiant. Yn y tiwtorial hwn, byddwn yn trafod ymagwedd wahanol at raglennu h.y. y dull Recursive.
Beth Yw Recursion Yn Java?
Proses lle mae swyddogaeth neu ddull yn galw ei hun dro ar ôl tro yw ail-ddigwyddiad. Gelwir y ffwythiant hwn a elwir dro ar ôl tro naill ai'n uniongyrchol neu'n anuniongyrchol yn “swyddogaeth recursive”.
Byddwn yn gweld enghreifftiau amrywiol i ddeall dychweliad. Nawr, gadewch i ni weld cystrawen y recursion.
Cystrawen Recursion
Mae dwy ran sylfaenol i unrhyw ddull sy'n gweithredu Recursion:
- Galwad dull sy'n gallu galw ei hun h.y. recursive
- Rhamod a fydd yn atal y dychweliad.
Sylwer bod rhagamod yn angenrheidiol ar gyfer unrhyw ddull ailadroddus fel, os na fyddwn yn gwneud hynny torri'rdychweliad yna bydd yn parhau i redeg yn anfeidrol ac yn arwain at orlif pentwr.
Mae cystrawen gyffredinol ailadroddiad fel a ganlyn:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Sylwer mai'r enw arall ar y rhagamod yw cyflwr sylfaenol. Byddwn yn trafod mwy am y cyflwr sylfaenol yn yr adran nesaf.
Deall Ailddigwyddiad Yn Java
Yn yr adran hon, byddwn yn ceisio deall y broses dychwelyd a gweld sut mae'n digwydd. Byddwn yn dysgu am y cyflwr sylfaenol, stac gorlif, ac yn gweld sut y gellir datrys problem benodol gydag ailadrodd a manylion eraill o'r fath.
Amod Sylfaen Ailgylchu
Wrth ysgrifennu'r rhaglen recursive, dylem yn gyntaf darparu'r ateb ar gyfer yr achos sylfaenol. Yna rydym yn mynegi'r broblem fwy yn nhermau problemau llai.
Fel enghraifft , gallwn gymryd problem glasurol o gyfrifo ffactoraidd rhif. O gael rhif n, mae'n rhaid i ni ddod o hyd i ffactorial o n a ddynodir gan n!
Nawr gadewch i ni weithredu'r rhaglen i gyfrifo'r ffactoraidd n (n!) gan ddefnyddio 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); } }Allbwn
Yn y rhaglen hon, gallwn weld mai'r cyflwr (n=1) yw'r cyflwr sylfaenol a phan gyrhaeddir y cyflwr hwn, mae'r ffwythiant yn dychwelyd 1 Rhan arall y swyddogaeth yw'r alwad ailadroddus. Ond bob tro y gelwir y dull ailadroddus, mae n yn cael ei ostwng gan 1.
Felly gallwn ddod i'r casgliad y bydd gwerth n yn y pen draw yn dod yn 1 neu'n llai nag 1 ac ar hyn o brydpwynt, bydd y dull yn dychwelyd gwerth 1. Bydd y cyflwr sylfaenol hwn yn cael ei gyrraedd a bydd y swyddogaeth yn dod i ben. Sylwch y gall gwerth n fod yn unrhyw beth cyn belled â'i fod yn bodloni'r cyflwr sylfaenol.
Datrys Problemau Trwy Ddefnyddio Recursion
Y syniad sylfaenol y tu ôl i ddefnyddio ailadrodd yw mynegi'r broblem fwy o ran problemau llai. Hefyd, mae angen i ni ychwanegu un neu fwy o amodau sylfaenol fel y gallwn ddod allan o'r ail dro.
Dangoswyd hyn eisoes yn yr enghraifft ffactoraidd uchod. Yn y rhaglen hon, fe wnaethom fynegi'r n ffactoraidd (n!) yn nhermau gwerthoedd llai ac roedd ganddo gyflwr sylfaenol (n =1) fel pan fydd n yn cyrraedd 1, gallwn roi'r gorau i'r dull ailadroddus.
Gwall Gorlif Pentwr yn Recursion
Rydym yn ymwybodol pan fydd unrhyw ddull neu swyddogaeth yn cael ei alw, bod cyflwr y ffwythiant yn cael ei storio ar y pentwr ac yn cael ei adfer pan fydd y ffwythiant yn dychwelyd. Mae'r stac yn cael ei ddefnyddio ar gyfer y dull ailadroddus hefyd.
Ond yn achos dychwelyd, gall problem godi os nad ydym yn diffinio'r cyflwr sylfaenol neu pan nad yw'r cyflwr sylfaenol yn cael ei gyrraedd neu ei weithredu rywsut. Os bydd y sefyllfa hon yn digwydd yna gall gorlif y pentwr godi.
Beth am i ni ystyried yr enghraifft isod o nodiant ffactoraidd.
Yma rydym wedi rhoi amod sylfaenol anghywir, 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); } }Felly pan n > 100 bydd y dull yn dychwelyd 1 ond ni fydd ailadrodd yn dod i ben. Bydd gwerth n yn parhau i ostwng am gyfnod amhenodol fel y maeNid oes unrhyw amod arall i'w atal. Bydd hwn yn mynd ymlaen nes bydd y stac yn gorlifo.
Achos arall fydd pan fydd gwerth n 100. Yn yr achos hwn, hefyd ni fydd y dull byth yn gweithredu'r cyflwr sylfaenol ac yn arwain at orlif pentwr. recursion.
#1) Cyfres Fibonacci yn Defnyddio Recursion
Rhoddir y gyfres Fibonacci gan,
1,1,2,3,5,8,13,21, 34,55,…
Mae'r dilyniant uchod yn dangos mai'r elfen gyfredol yw swm y ddwy elfen flaenorol. Hefyd, yr elfen gyntaf yn y gyfres Fibonacci yw 1.
Felly yn gyffredinol os mai n yw'r rhif cerrynt, yna mae'n cael ei roi gan swm (n-1) ac (n-2). Gan fod yr elfen gyfredol yn cael ei mynegi yn nhermau elfennau blaenorol, gallwn fynegi'r broblem hon gan ddefnyddio recursion.
Rhoddir y rhaglen i weithredu'r gyfres Fibonacci isod:
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) + " "); } } } Allbwn
#2) Gwiriwch ai Palindrom yw Rhif Gan Ddefnyddio Recursion
Mae palindrom yn ddilyniant sy'n hafal pan fyddwn ni darllenwch ef o'r chwith i'r dde neu o'r dde i'r chwith.
O ystyried rhif 121, gwelwn ei fod yn gyfartal wrth ei ddarllen o'r chwith i'r dde ac o'r dde i'r chwith. Felly palindrom yw rhif 121.
Cymerwn rif arall, 1242. Pan fyddwn yn ei ddarllen o'r chwith i'r dde mae'n 1242 ac o'i ddarllen o'r dde i'r chwith mae'n darllen fel 2421. Felly nid palindrom yw hwn.
Rydym nigweithredu'r rhaglen palindrome trwy wrthdroi'r digidau rhifau a chymharu'r rhif a roddwyd yn gyson â'i gynrychioliad wedi'i wrthdroi.
Mae'r rhaglen isod yn gweithredu'r rhaglen i wirio'r palindrom.
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."); } } }0 Allbwn 
#3) Reverse String Java Recursion
O ystyried llinyn “Helo” mae'n rhaid i ni ei wrthdroi fel bod y llinyn canlyniadol yw "olleH".
Gwneir hyn gan ddefnyddio recursion. Gan ddechrau o'r nod olaf yn y llinyn rydym yn argraffu pob nod yn gyson nes bod yr holl nodau yn y llinyn wedi dod i ben.
Mae'r rhaglen isod yn defnyddio dychweliad i wrthdroi llinyn penodol.
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); } } Allbwn
#4) Chwiliad Deuaidd Java Recursion
Algorithm chwilio deuaidd yw algorithm enwog ar gyfer chwilio. Yn yr algorithm hwn, o gael amrywiaeth wedi'i didoli o n elfen, rydym yn chwilio'r arae hon am yr elfen allweddol a roddwyd. Yn y dechrau, rydym yn rhannu'r arae yn ddau hanner trwy ddod o hyd i elfen ganol yr arae.
Yna yn dibynnu a yw canol y bysell rydym yn cyfyngu ein chwiliad yn hanner cyntaf neu ail hanner yr arae. Fel hyn mae'r un broses yn cael ei hailadrodd nes dod o hyd i leoliad yr elfennau allweddol.
Byddwn yn gweithredu'r algorithm hwn gan ddefnyddio recursion yma.
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); } } Allbwn
#5) Dod o Hyd i Isafswm Gwerth Mewn Arae Gan Ddefnyddio Recursion
Gan ddefnyddio recursion gallwn hefyd ddarganfod y gwerth lleiaf yn yr arae.
Mae'rMae rhaglen Java i ddarganfod y gwerth lleiaf yn yr arae wedi'i rhoi isod.
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"); } }Allbwn
Dyma rai o yr engreifftiau o attaliad. Ar wahân i'r enghreifftiau hyn, mae llawer o broblemau eraill yn y feddalwedd yn gallu cael eu gweithredu gan ddefnyddio technegau ailadroddus.
Mathau o Ail-ddigwyddiad
Mae ail-ddechrau o ddau fath yn seiliedig ar pryd y gwneir yr alwad i y dull ailadroddus.
Nhw yw:
#1) Ail-gyrchu Cynffon
Pan mai'r datganiad olaf yw'r alwad i'r dull ailadroddus yn cael ei weithredu y tu mewn i'r dull ailadroddus, fe'i gelwir yn “Tail Recursion”.
Mewn ailadrodd cynffon, mae'r datganiad galwad ailadroddus fel arfer yn cael ei weithredu ynghyd â datganiad dychwelyd y dull.
Y rhoddir cystrawen gyffredinol ar gyfer ail-chweliad cynffon isod:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Ail-gyrchu Pen
Mae dychweliad pen yn unrhyw ddull ailadroddus nad yw'n ailadroddiad cynffon. Felly mae hyd yn oed dychweliad cyffredinol ar y blaen.
Mae cystrawen ailgyrchu pen fel a ganlyn:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Ail-ddigwyddiad Vs Iteriad Yn Java
| Cylchdro | Iteru |
|---|---|
| Mae ail-ddigwyddiad yn broses lle mae dull yn galw ei hun dro ar ôl tro nes bod amod sylfaenol wedi'i fodloni. | Mae iteriad yn proses lle mae darn o god yn cael ei weithredu dro ar ôl tro am nifer cyfyngedig o weithiau neu hyd nes y bodlonir amod. |
| A yw'r cais am swyddogaethau. | Yn berthnasol ar gyfer dolenni. |
| Yn gweithio'n dda ar gyfermaint cod llai. | Yn gweithio'n dda ar gyfer maint cod mwy. |
| Yn defnyddio mwy o gof wrth i bob galwad ailadroddus gael ei gwthio i'r pentwr | Cymharol lai o gof yn cael ei ddefnyddio. |
| Anodd dadfygio a chynnal | Hawdd dadfygio a chynnal |
| Canlyniadau mewn gorlif stac os yw'r sylfaen cyflwr heb ei nodi neu heb ei gyrraedd. | Gallai weithredu'n anfeidrol ond yn y pen draw bydd yn stopio cyflawni gydag unrhyw wallau cof |
| Mae cymhlethdod amser yn uchel iawn. | Mae cymhlethdod amser yn gymharol ar yr ochr isaf. |
Cwestiynau a Ofynnir yn Aml
C #1) Sut mae Recursion yn gweithio yn Java?
Ateb: Mewn ailadrodd, mae'r ffwythiant ailadroddus yn galw ei hun dro ar ôl tro nes bodloni amod sylfaenol. Mae'r cof ar gyfer y swyddogaeth a elwir yn cael ei wthio ymlaen i'r pentwr ar frig y cof ar gyfer y swyddogaeth galw. Ar gyfer pob galwad ffwythiant, gwneir copi ar wahân o newidynnau lleol.
C #2) Pam mae Recursion yn cael ei ddefnyddio?
Ateb: Defnyddir ailgyrch i ddatrys y problemau hynny y gellir eu rhannu'n rhai llai a gellir mynegi'r broblem gyfan yn nhermau problem lai.
Defnyddir dychwelyd hefyd ar gyfer y problemau hynny sy'n rhy cymhleth i'w datrys gan ddefnyddio dull iteraidd. Heblaw am y problemau nad yw cymhlethdod amser yn broblem ar eu cyfer, defnyddiwch recursion.
C #3) Beth yw manteisionRecursion?
Ateb:
Mae manteision Recursion yn cynnwys:
- Recursion yn lleihau galwadau diangen ffwythiant.
- Mae dychwelyd yn ein galluogi i ddatrys problemau'n hawdd o'u cymharu â'r dull iterus.
C #4) Pa un sy'n well – Ailddigwyddiad neu iteriad?2
Ateb: Mae Recursion yn gwneud galwadau mynych nes cyrraedd y ffwythiant sylfaenol. Felly mae cof uwchben wrth i gof ar gyfer pob galwad ffwythiant gael ei wthio ymlaen i'r pentwr.
Nid oes llawer o gof uwchben i'r iteriad ar y llaw arall. Mae cyflawni dychweliad yn arafach na'r dull ailadroddus. Mae recursion yn lleihau maint y cod tra bod y dull iterus yn gwneud y cod yn fawr.
C #5) Beth yw Manteision Ail-ddichweliad dros iteriad?
Ateb:
- Mae Recursion yn gwneud y cod yn gliriach ac yn fyrrach.
- Mae dychwelyd yn well na'r dull ailadroddus ar gyfer problemau fel Tŵr Hanoi, coeden llwybrau, ac ati.
- Gan fod cof wedi'i wthio ymlaen i'r pentwr ar gyfer pob galwad ffwythiant, mae Recursion yn defnyddio mwy o gof.
- Mae perfformiad dychweliad yn arafach na'r dull iterus.
Casgliad
Mae dychwelyd yn gysyniad pwysig iawn mewn meddalwedd waeth beth fo'r iaith raglennu. Defnyddir dychweliad yn bennaf i ddatrys problemau strwythur data fel tyrau Hanoi, llwybrau coed, rhestrau cysylltiedig, ac ati. Er ei fod yn cymryd mwy o gof,mae recursion yn gwneud cod yn symlach ac yn gliriach.
Rydym wedi archwilio popeth am Recursion yn y tiwtorial hwn. Rydym hefyd wedi gweithredu nifer o enghreifftiau rhaglennu ar gyfer gwell dealltwriaeth o'r cysyniad.