Gruntle Software & Testing

Le Stewart TristianAir a chur suas Air a chur suas ann an Stiùiridhean

Tha an oideachadh domhainn seo air ath-chuairteachadh ann an Java a’ mìneachadh dè a th’ ann an ath-chuairteachadh le eisimpleirean, seòrsaichean, agus bun-bheachdan co-cheangailte. Tha e cuideachd a’ còmhdach Recursion Vs Iteration:

Bho na clasaichean oideachaidh na bu thràithe againn ann an Java, tha sinn air an dòigh ath-aithriseach fhaicinn anns am bi sinn a’ foillseachadh lùb agus an uairsin a’ dol tro structar dàta ann an dòigh ath-aithriseach le bhith a’ gabhail aon eileamaid aig turas.

Chunnaic sinn cuideachd an t-sruth chumha far a bheil sinn a-rithist a’ cumail aon chaochladair lùb agus ag ath-aithris pìos còd gus an coinnich caochladair na lùb ris a’ chumha. Nuair a thig e gu gairmean gnìomh, rannsaich sinn an dòigh ath-aithriseach airson fiosan gnìomh cuideachd. San oideachadh seo, bruidhnidh sinn air dòigh-obrach eadar-dhealaichte a thaobh prògramadh ie an dòigh-obrach ath-chuairteach.

Dè a th’ ann an ath-chuairteachadh ann an Java?

’S e pròiseas a th’ ann an ath-chuairteachadh leis am bi gnìomh no modh ga ghairm fhèin a-rithist is a-rithist. Canar “recursive function” ris a’ ghnìomh seo ris an canar a-rithist is a-rithist an dara cuid gu dìreach no gu neo-dhìreach.

Chì sinn grunn eisimpleirean gus ath-chuairteachadh a thuigsinn. A-nis chì sinn co-chòrdadh ath-chuairteachaidh.

Co-chàradh ath-chuairteachaidh

Tha dà phàirt bhunaiteach aig dòigh sam bith a chuireas an gnìomh Recursion:

  1. Gairm modh a dh'fhaodas a bhith ga ainmeachadh fhèin ie ath-chuairteach
  2. Riaghailt a chuireas stad air an ath-chuairt.

Thoir an aire gu bheil feum air ro-chùmhnant airson modh ath-chuairteachaidh sam bith oir, mura dèan sinn sin briseadh anath-chuairteachadh an uairsin cumaidh e air a' ruith gu neo-chrìochnach agus mar thoradh air sin bidh stac a' cur thairis.

Tha co-chòrdadh coitcheann an ath-chuairteachaidh mar a leanas: 

methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call }

Thoir an aire gur e an t-ainm a th' air an ro-chùmhnant cuideachd. suidheachadh bunaiteach. Bruidhnidh sinn barrachd mun t-suidheachadh bunaiteach anns an ath earrann.

A' Tuigsinn Ath-chuairteachadh ann an Java

San earrann seo, feuchaidh sinn ri pròiseas ath-chuairteachaidh a thuigsinn agus faicinn mar a bhios e a' tachairt. Ionnsaichidh sinn mun t-suidheachadh bunaiteach, stac thar-shruth, agus chì sinn mar a ghabhas fuasgladh fhaighinn air duilgheadas sònraichte le ath-chuairteachadh agus mion-fhiosrachadh eile mar sin.

Suidheachadh Bunait Ath-chuairteachaidh

Nuair a bhios sinn a’ sgrìobhadh a’ phrògram ath-chùramach, bu chòir dhuinn an toiseach thoir seachad am fuasgladh airson a’ chùis bhunaiteach. An uair sin bidh sinn a' cur an cèill an duilgheadas as motha a thaobh trioblaidean nas lugha.

Mar eisimpleir, 's urrainn dhuinn duilgheadas clasaigeach a ghabhail a thaobh a bhith ag obrachadh a-mach factaraidh àireamh. Le àireamh n, feumaidh sinn factaraidh n a lorg air a chomharrachadh le n!

A-nis leig dhuinn am prògram obrachadh a-mach an fhactaraidh n (n!) a’ cleachdadh ath-chuairteachadh.

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); } }

Toradh

Sa phrògram seo, chì sinn gur e an suidheachadh (n=1) am bun-staid agus nuair a ruigear an suidheachadh seo, tillidh an gnìomh 1 Is e am pàirt eile den ghnìomh an gairm ath-chuairteach. Ach a h-uile uair a chanar ris a’ mhodh ath-chuairteach, tha n air a lùghdachadh le 1.

Mar sin faodaidh sinn a cho-dhùnadh gum fàs luach n aig a’ cheann thall gu bhith 1 no nas lugha na 1 agus aig an seopuing, tillidh am modh luach 1. Thèid an suidheachadh bunaiteach seo a ruighinn agus stadaidh an gnìomh. Thoir an aire gum faod luach n a bhith rud sam bith fhad 's a tha e a' sàsachadh a' bhunait bhunaiteach.

Fuasgladh Cheistean a' Cleachdadh Ath-chuairteachadh

'S e am beachd bunaiteach air cùl cleachdadh ath-chuairteachaidh an duilgheadas as motha a chur an cèill a thaobh duilgheadasan nas lugha. Cuideachd, feumaidh sinn aon suidheachadh bunaiteach no barrachd a chur ris gus an tig sinn a-mach à ath-thilleadh.

Chaidh seo a dhearbhadh mar-thà san eisimpleir fhactaraidh gu h-àrd. Anns a' phrògram seo, chuir sinn an cèill an n factorial (n!) a thaobh luachan nas lugha agus bha suidheachadh bunaiteach (n =1) gus nuair a ruigeas n 1, 's urrainn dhuinn stad a chur air a' mhodh ath-chùramach.

Mearachd Stack Overflow In Recursion

Tha sinn mothachail nuair a chanar dòigh no gnìomh sam bith, gu bheil staid a’ ghnìomh air a stòradh air a’ chruaich agus air fhaighinn air ais nuair a thilleas an gnìomh. Tha an stac air a chleachdadh airson an dòigh ath-chùramach cuideachd.

Ach a thaobh ath-chuairteachaidh, dh'fhaodadh duilgheadas èirigh mura mìnich sinn a' bhun-suidheachadh no nuair nach ruigear dòigh air choireigin air a' bhun-suidheachadh no nach tèid a chur an gnìomh. Ma thachras seo is dòcha gun èirich an t-sruth-thar-shruth stac.

Beachdaichidh sinn air an eisimpleir gu h-ìosal de chomharradh fhactaraidh.

Seo tha sinn air suidheachadh bunaiteach ceàrr a thoirt seachad, 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); } }

Mar sin nuair a tha n > 100 tillidh am modh 1 ach cha stad ath-chuairteachadh. Cumaidh luach n air a dhol sìos gu bràth mar a thachan eil suidheachadh sam bith eile ann airson stad a chuir air. Leanaidh seo air adhart gus an tèid stac thairis air.

Bidh cùis eile ann nuair a bhios luach n 100. Anns a' chùis seo cuideachd, cha chuir am modh a' bhun-suidheachadh an gnìomh gu bràth agus mar thoradh air sin bidh stac thar-shruth. ath-chuairteachadh.

#1) Sreath Fibonacci A' Cleachdadh Ath-chuairteachadh

Tha an t-sreath Fibonacci air a thoirt seachad le,

1,1,2,3,5,8,13,21, 34,55,…

Tha an t-sreath gu h-àrd a’ sealltainn gur e an eileamaid làithreach suim an dà eileamaid roimhe. Cuideachd, 's e 1 a' chiad eileamaid san t-sreath Fibonacci.

Mar sin san fharsaingeachd mas e n an àireamh làithreach, tha e air a thoirt seachad leis an t-suim (n-1) agus (n-2). Leis gu bheil an eileamaid làithreach air a chur an cèill a thaobh eileamaidean roimhe, 's urrainn dhuinn an duilgheadas seo a chur an cèill le bhith a' cleachdadh ath-chuairteachadh.

Tha am prògram airson an t-sreath Fibonacci a chur an gnìomh air a thoirt gu h-ìosal: 

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) + " "); } } }

Toradh

#2) Dèan cinnteach a bheil àireamh na phalindrome a’ cleachdadh ath-chuairteachadh

’S e sreath a tha co-ionann a th’ ann am palindrome nuair a bhios sinn leugh e o chlì gu deas no deas gu clì.

Le àireamh 121, chì sinn nuair a leughas sinn e bho chlì gu deas agus deas gu clì, gu bheil e co-ionnan. Mar sin 's e palindrome a th' ann an àireamh 121.

Gabhaidh sinn àireamh eile, 1242. Nuair a leughas sinn e bho chlì gu deas 's e 1242 a th' ann agus nuair a leughas e bho dheas gu clì tha e mar 2421. Mar sin chan e palindrome a tha seo.

Tha sinncuir am prògram palindrome an gnìomh le bhith a’ tionndadh àireamhan àireamhan air ais agus a’ dèanamh coimeas a-rithist is a-rithist eadar an àireamh a chaidh a thoirt seachad agus an riochdachadh air ais.

Tha am prògram gu h-ìosal a’ cur an gnìomh am prògram gus sùil a thoirt air a’ phalindrome. 

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."); } } }

Toradh

#3) Java Reverse String Recursion Java

Le sreang “Hello” feumaidh sinn a thionndadh air ais gus am bi an 's e "olleH" an t-sreang a thig às.

Tha seo air a dhèanamh a' cleachdadh ath-chùram. A' tòiseachadh leis a' charactair mu dheireadh san t-sreang bidh sinn a' clò-bhualadh gach caractar a-rithist gus am bi a h-uile caractar san t-sreang sgìth.

Tha am prògram gu h-ìosal a' cleachdadh ath-chuairteachadh gus sreang shònraichte a thionndadh air ais. 

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); } }

Cur a-mach

#4) Rannsachadh Dàna Ath-chuairteachadh Java

’S e algairim rannsachaidh dà-chànanach a tha ainmeil airson a rannsachadh. San algairim seo, le taghadh de eileamaidean n air an òrdachadh, bidh sinn a’ sgrùdadh an t-sreath seo airson a’ phrìomh eileamaid a chaidh a thoirt seachad. Aig an toiseach, bidh sinn a 'roinn an t-sreath ann an dà leth le bhith a' lorg an eileamaid mheadhanach den rèite.

An uairsin a rèir an e am meadhan iuchair a tha sinn a 'cuingealachadh ar rannsachadh sa chiad no san dàrna leth den raon. San dòigh seo thèid an aon phròiseas a-rithist gus an lorgar suidheachadh nam prìomh eileamaidean.

Cuiridh sinn an algairim seo an gnìomh a’ cleachdadh ath-chùram an-seo. 

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); } }

Cur a-mach

#5) Lorg an luach as ìsle ann an òrdugh a’ cleachdadh ath-chuairteachadh

A’ cleachdadh ath-chuairteachaidh gheibh sinn cuideachd an luach as ìsle san raon.

ThaTha prògram Java airson an luach as lugha a lorg san raon air a thoirt seachad gu h-ìosal. 

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"); } }

Toradh

Seo cuid de eisimpleirean de ath-chuairteachadh. A bharrachd air na h-eisimpleirean seo, faodar tòrr dhuilgheadasan eile sa bhathar-bhog a chur an gnìomh a’ cleachdadh dòighean ath-chuairteachaidh.

Seòrsan Ath-chuairteachaidh

Tha dà sheòrsa ath-chuairteachaidh stèidhichte air cuin a thèid an gairm a dhèanamh. an dòigh ath-chuairteach.

Is iad sin:

#1) Tail Recursion

Nuair a bhios an gairm chun an dòigh ath-chùrsach mar an aithris mu dheireadh air a chur gu bàs taobh a-staigh an dòigh ath-chuairteach, is e “Tail Recursion” a chanar ris.

Ann an ath-chuairteachadh earbaill, mar as trice bidh an aithris gairm ath-chuairteach air a chuir gu bàs còmhla ri aithris tilleadh a’ mhodh.

An tha co-chòrdadh coitcheann airson ath-chuairteachadh earbaill air a thoirt seachad gu h-ìosal: 

methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion }

#2) Ath-chuairteachadh cinn

Is e ath-chuairteachadh cinn dòigh ath-chuairteach sam bith nach e ath-chuairteachadh earbaill. Mar sin tha eadhon ath-chuairteachadh coitcheann air thoiseach air ais.

Tha co-chòrdadh ath-chuairteachaidh cinn mar a leanas: 

methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; }

Ath-chuairteachadh Vs Iteration Ann an Java

Tilleadh Iris
Is e pròiseas a th’ ann an ath-chuairteachadh far a bheil modh a’ gairm fhèin a-rithist is a-rithist gus an tèid suidheachadh bunaiteach a choileanadh. Tha tionndadh pròiseas far an tèid pìos còd a chur an gnìomh a-rithist grunn thursan no gus an tèid cumha a choileanadh.
A bheil an t-iarrtas airson gnìomhan. airson lùban.
Ag obair gu math airsonmeud còd nas lugha. Ag obair gu math airson meud còd nas motha.
A’ cleachdadh barrachd cuimhne leis gu bheil gach gairm ath-chuairteach ga phutadh chun stac An ìre mhath nas lugha de chuimhne air a chleachdadh.
Doirbh a dhì-bhugachadh is a chumail suas Nas fhasa dì-bhugachadh is cumail suas
Toraidhean ann an stac thar-shruth ma tha am bonn chan eil an suidheachadh air a shònrachadh no cha ruigear e. Faodaidh seo a chur an gnìomh gu neo-chrìochnach ach cuiridh e stad air a chur gu bàs mu dheireadh le mearachdan cuimhne sam bith
Tha iom-fhillteachd ùine glè àrd. Tha iom-fhillteachd ùine an ìre mhath air an taobh ìosal.

Ceistean Bitheanta

C #1) Ciamar a tha Recursion ag obair ann an Java?

Freagair: Ann an ath-chuairteachadh, bidh an gnìomh ath-chuairteach ga ghairm fhèin a-rithist is a-rithist gus am bi suidheachadh bunaiteach riaraichte. Tha a’ chuimhne airson a’ ghnìomh ris an canar air a phutadh air a’ chruach aig mullach a’ chuimhne airson a’ ghnìomh gairm. Airson gach gairm gnìomh, thèid leth-bhreac fa leth de na caochladairean ionadail a dhèanamh.

Q #2) Carson a chleachdar Recursion?

Freagairt: Bithear a' cleachdadh ath-chuairteachadh gus fuasgladh fhaighinn air na duilgheadasan sin a dh'fhaodar a bhriseadh sìos gu feadhainn nas lugha agus faodar an duilgheadas gu lèir a chur an cèill a thaobh duilgheadas nas lugha.

Bithear a' cleachdadh ath-chuairteachadh cuideachd airson nan duilgheadasan sin a tha cuideachd iom-fhillte ri fhuasgladh a’ cleachdadh dòigh-obrach ath-aithriseach. A bharrachd air na duilgheadasan nach eil iom-fhillteachd ùine na chùis, cleachd ath-chuairteachadh.

Q #3) Dè na buannachdan a tha annAth-chuairteachadh?

Freagra:

Tha buannachdan ath-chuairteachaidh a’ toirt a-steach:

  1. Tha ath-chuairteachadh a’ lughdachadh gairmean nach eil feum gnìomh.
  2. Leigidh ath-chuairteachadh leinn duilgheadasan fhuasgladh gu furasta an taca ris an dòigh ath-aithriseach.

Q #4) Dè am fear as fheàrr – Ath-chuairteachadh no Iteration?2

Freagra: Bidh ath-chuairteachadh a’ dèanamh gairmean a-rithist gus an ruigear a’ ghnìomh bhunaiteach. Mar sin tha cuimhne os an cionn leis gu bheil cuimhne airson gach gairm gnìomh ga phutadh air a’ chruaich.

Air an làimh eile, chan eil mòran cuimhne aig an ath-aithris air an làimh eile. Tha coileanadh ath-chuairteachaidh nas slaodaiche na an dòigh ath-aithriseach. Bidh ath-chuairteachadh a’ lughdachadh meud a’ chòd fhad ‘s a tha an dòigh ath-aithriseach a’ fàgail a’ chòd mòr.

Q #5) Dè na buannachdan a th’ ann an ath-thilleadh thairis air tionndadh?

Freagair:

  • Tha ath-chuairteachadh a’ dèanamh a’ chòd nas soilleire agus nas giorra.
  • Tha ath-chuairteachadh nas fheàrr na an dòigh ath-aithriseach airson duilgheadasan leithid Tùr Hanoi, craobh slighean-tarsainn, msaa.
  • A chionn 's gu bheil cuimhne air a phutadh air a' chruaich aig a h-uile gairm gnìomh, bidh Recursion a' cleachdadh barrachd cuimhne.
  • Tha coileanadh ath-chuairteachaidh nas slaodaiche na an dòigh ath-aithriseach.

Co-dhùnadh

Tha ath-chuairteachadh na bhun-bheachd fìor chudromach ann am bathar-bog ge bith dè an cànan prògramaidh a th’ ann. Tha ath-chuairteachadh air a chleachdadh sa mhòr-chuid ann a bhith a’ fuasgladh dhuilgheadasan structar dàta leithid tùir Hanoi, slighean chraobhan, liostaichean ceangailte, msaa. Ged a bheir e barrachd cuimhne,nì ath-chuairteachadh còd nas sìmplidh agus nas soilleire.

Rannsaich sinn a h-uile càil mu dheidhinn Ath-chuairteachadh san oideachadh seo. Tha sinn cuideachd air grunn eisimpleirean de phrògraman a chuir an gnìomh airson tuigse nas fheàrr fhaighinn air a’ bhun-bheachd.

Sgrolaich gu barr