Ev Dersa Kûrahî ya Li ser Vegerandinê ya li Java-yê Bi Mînak, Cure û Têgînên Têkildar Vegerandin rave dike ku çi ye. Di heman demê de Recursion Vs Iteration jî vedigire:
Ji dersên meyên berê yên li Java-yê, me nêzîkatiya dubarekirî dît ku tê de em xelekek radigihînin û dûv re di nav avahiyek daneyê de bi rengek dubarekirî bi girtina yek elementek li demek.
Me her weha herikîna şertî jî dît ku dîsa em guhêrbarek xelekek diparêzin û perçeyek kodê dubare dikin heya ku guhêrbar çerxê şertê pêk bîne. Dema ku dor tê bangên fonksiyonê, me ji bo bangên fonksiyonê nêzîkatiya dubarekirî jî lêkolîn kir.
Di vê dersê de, em ê nêzîkatiyek cûda ya bernamekirinê ango nêzîkatiya Recursive nîqaş bikin.
Recursion Di Java de Çi ye?
Vegerandin pêvajoyek e ku fonksiyonek an rêbazek dîsa û dîsa gazî xwe dike. Ji vê fonksîyona ku carcaran rasterast an nerasterast tê gotin "fonksîyona vegerî" tê gotin.
Ji bo têgihîştina vegerê em ê mînakên cihê bibînin. Naha em hevoksaziya vegerandinê bibînin.
Sîntaksa Vegerandinê
Her rêbaza ku Vegerandinê pêk tîne du beşên bingehîn hene:
- Banga rêbaza ku dikare xwe bi nav bike ango vegere
- Şerteke pêşwext ku dê vegerandinê rawestîne.
Bala xwe bidin ku şertek pêşwext ji bo her şêwazek vegerî pêdivî ye, heke em nebin bişkîninpaşvegerandin wê demê ew ê bêsînor bimeşe û bibe sedema pirbûna stê.
Sîntaksa giştî ya vegerandinê wiha ye:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Bêbînî ku şerta pêşîn jî tê gotin. rewşa bingehîn. Em ê di beşa pêş de bêtir li ser rewşa bingehîn nîqaş bikin.
Fêmkirina Vegerandina Li Javayê
Di vê beşê de, em ê hewl bidin ku pêvajoya vegerandinê fam bikin û bibînin ka ew çawa pêk tê. Em ê li ser rewşa bingehê hîn bibin, stûyê zêde bikin, û bibînin ka pirsgirêkek taybetî çawa dikare bi vegerandinê û hûrguliyên din ên weha were çareser kirin.
Rewşa Bingeha Vegerandinê
Dema ku bernameya vegerê dinivîsin, divê em pêşî çareseriyek ji bo doza bingehîn peyda bikin. Paşê em pirsgirêka mezintir bi pirsgirêkên piçûktir diyar dikin.
Wek nimûne, em dikarin pirsgirêka klasîk a hesabkirina faktoriya jimarekê bigirin. Jimara n tê dayîn, divê em faktoriyek n-ya ku bi n-yê tê nîşankirin bibînin!
Niha em bernameyê bicîh bikin ku n-ya faktorîal (n!) bi karanîna vegerandinê hesab bike.
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); } }Derketin
Di vê bernameyê de, em dikarin bibînin ku şerta (n=1) şerta bingehîn e û dema ku ev rewş gihîştî, fonksiyon 1 vedigere. Beşê din ê fonksiyonê banga veger e. Lê her cara ku rêbaza vegerê tê gotin, n bi 1 kêm dibe.
Bi vî awayî em dikarin encam bidin ku di dawiyê de nirxa n dê bibe 1 an ji 1 kêmtirxal, rêbaz dê nirxa 1 vegerîne. Ev rewşa bingehîn dê bigihîje û fonksiyon dê raweste. Bala xwe bidinê ku nirxa n dikare her tişt be heya ku ew şerta bingehîn têr dike.
Çareserkirina Pirsgirêkan Bi Bikaranîna Vegerandinê
Ramana bingehîn a li pişt karanîna vegerandinê ev e ku pirsgirêka mezintir bi şertê diyar bike. pirsgirêkên piçûktir. Di heman demê de, divê em yek an çend şertên bingehîn lê zêde bikin da ku em ji paşverûbûnê derkevin.
Ev jixwe di mînaka faktorî ya jorîn de hate xuyang kirin. Di vê bernameyê de, me n-ya faktorîal (n!) li gorî nirxên piçûktir diyar kir û şertek bingehîn hebû (n =1) ji ber vê yekê dema ku n bigihîje 1-ê, em dikarin dev ji rêbaza paşverû berdin.
Di Vegerandinê de Çewtiya Serhildana Stackê
Em dizanin ku dema ku rêbazek an fonksiyonek tê gazî kirin, rewşa fonksiyonê li ser stikê tê hilanîn û dema fonksiyon vedigere tê hilanîn. Stack ji bo rêbaza vegerê jî tê bikaranîn.
Lê di rewşa vegerandinê de, dibe ku pirsgirêk derkeve heke em şerta bingehîn diyar nekin an jî dema ku şerta bingehîn bi rengekî negihîje an neyê bicîh kirin. Ger ev rewş çêbibe wê hingê dibe ku dorhêla stikê çêbibe.
Werin em mînaka jêrîn a nîşankirina faktorî binirxînin.
Li vir me şertek bingehîn a xelet daye, 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); } }Ji ber vê yekê dema ku n > 100 rêbaz dê 1 vegere lê vegerandin namîne. Nirxa n dê her ku diçe kêm bibe li wirne şertekî din e ji bo rawestandina wê. Ev dê bidome heta stack overflow.
Rewşa din dê bibe dema ku nirxa n 100. Di vê rewşê de jî, rêbaz tu carî şerta bingehîn pêk nayîne û di encamê de stêk zêde dibe.
Mînakên Vegerandinê Di Java-yê de
Di vê beşê de, em ê mînakên jêrîn bi kar bînin paşveçûn.
#1) Rêzeya Fibonacci Bi Bikaranîna Vegerandinê
Rêzeya Fibonacci ji hêla,
1,1,2,3,5,8,13,21 ve tê dayîn. 34,55,…
Rêza jorîn nîşan dide ku hêmana heyî berhevoka her du hêmanên berê ye. Her weha, hêmana yekem di rêza Fibonacci de 1 e.
Ji ber vê yekê bi gelemperî heke n jimareya heyî be, hingê ew bi berhevoka (n-1) û (n-2) tê dayîn. Ji ber ku hêmana heyî li gorî hêmanên berê tê diyar kirin, em dikarin vê pirsgirêkê bi karanîna vegerandinê diyar bikin.
Bernameya pêkanîna rêzikên Fibonacci li jêr tê dayîn:
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) + " "); } } } Derketin
#2) Kontrol bikin ka jimarek palindrom e bi karanîna vegerandinê
Palindrom rêzek e ku gava em wekhev e. ji çepê ber bi rastê yan jî rastê ber bi çepê ve bixwîne.
Jimara 121ê tê dayîn, em dibînin ku dema em wê ji çepê ber bi rastê û rastê ber bi çepê ve dixwînin ew wek hev e. Ji ber vê yekê jimareya 121 palindromek e.
Em jimareke din, 1242, bigirin. Dema ku em ji çepê ber bi rastê ve dixwînin ew dibe 1242 û dema ku ji rastê ber bi çepê ve tê xwendin ew wekî 2421 tê xwendin. Loma ev ne palindrom e.
Embernameya palindromê bi berevajîkirina reqemên jimareyan pêk bîne û bi awayekî vegere hejmara diyarkirî bi temsîla wê ya berevajî bide ber hev.
Bernameya jêrîn bernameya kontrolkirina palindromê pêk tîne.
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."); } } }Derketin
#3) Vegerandina rêza berevajî Java
Ji rêzika "Silav" tê dayîn, divê em wê berevajî bikin da ku rêzika encam "olleH" ye.
Ev bi karanîna vegerandinê tê kirin. Ji tîpa paşîn a rêzikê dest pê dike, em her karakterek bi paşverû çap dikin heya ku hemî tîpên di rêzikê de biqedin.
Bernameya jêrîn ji bo berevajîkirina rêzek diyarkirî vegerandinê bikar tîne.
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); } } Derketin
#4) Lêgerîna Binary Java Recursion
Algorîtmaya lêgerînê ya binar algorîtmayek navdar a lêgerînê ye. Di vê algorîtmayê de, ku ji n hêmanan rêzkirîyek rêzkirî tê dayîn, em li vê rêzê li hêmana sereke ya diyarkirî digerin. Di destpêkê de, em bi dîtina hêmana navîn a rêzê, rêzê dikin du nîv.
Piştre li gorî ka mid-ya sereke em lêgerîna xwe di nîvê yekem an duyemîn a rêzê de bisînor dikin. Bi vî awayî heman pêvajo tê dubarekirin heta ku cîhê hêmanên sereke were dîtin.
Em ê vê algorîtmayê bi karanîna vegerê li vir bicîh bikin.
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); } } Derketin
#5) Bi Bikaranîna Vegerê Di Arrayyê de Nirxa Kêmtirîn Bibînin
Bi karanîna vegerandinê em dikarin di rêzê de nirxa herî kêm jî bibînin.
0> TheBernameya Java ya ji bo dîtina nirxa herî kêm a di rêzê de li jêr tê dayîn.
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"); } }Derketin
Ev çend ji mînakên vegerê. Ji xeynî van mînakan, gelek pirsgirêkên din ên di nermalavê de bi karanîna teknîkên vegerandinê dikarin bêne bicîh kirin.
Cureyên vegerandinê
Li gorî dema ku bang tê kirin vegerandin du celeb e. rêbaza vegere.
Ew ev in:
#1) Vegerandina dûvikê
Dema ku banga rêbaza paşverû gotina dawîn e. Di hundurê rêbaza vegerê de, jê re dibêjin "Devgera dûvik".
Di vegerandina dûvikê de, bi gelemperî daxuyaniya banga vegerê ligel daxuyaniya vegerê ya rêbazê tê darve kirin.
hevoksaziya giştî ya ji bo vegerandina dûvikê li jêr hatiye dayîn:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Vegerîna Serî
Vegerandina serî her nêzîkbûnek vegerî ye ku ne vegerandina dûvikê ye. Ji ber vê yekê vegerandina giştî jî li pêş vegerê ye.
Sîntaksa vegerandina serî wiha ye:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Vegerandin Vs Dubarekirin Di Java de
| Vegerandin | Derbarekirin |
|---|---|
| Vegerandin pêvajoyek e ku rêbazek dubare gazî xwe dike heya ku şertek bingehîn pêk were. | Dîbarkirin e. pêvajoyek ku pêvajoyek kodek çend caran ji bo çend caran an jî heya ku şertek pêk were tê xebitandin. |
| Ma serîlêdana fonksiyonan e. | Ma tê pêkanîn. ji bo loops. |
| Ji bo baş dixebiteqebareya kodê piçûktir. | Ji bo qebareya kodê ya mezin baş dixebite. |
| Her ku her bangek paşverû ber bi stikê ve tê kişandin bêtir bîranînê bi kar tîne | Hêza berawirdî kêmtir tê bikaranîn. |
| Debutkirin û domandin zehmet e | Dabeşkirin û domandin hêsan e |
| Eger bingehê di stûyê de zêde dibe. şert nayê diyar kirin an jî nayê gihîştin. | Dibe ku bêsînor were înfazkirin lê di dawiyê de digel her xeletiyên bîranînê dê înfazê rawestîne |
| Tevlîheviya demê pir zêde ye. | Tevliheviya demê bi nisbeten li aliyê jêrîn e. |
Pirsên Pir Pir Pir Pirsîn
Q #1) Recursion çawa di Java de dixebite?
Bersiv: Di vegerandinê de, fonksiyona vegerê çend caran gazî xwe dike heya ku şertek bingehîn têr bibe. Bîra fonksiyona gazîkirî ji bo fonksiyona bangkirinê berbi stûna li jorê bîranînê tê kişandin. Ji bo her bangek fonksiyonê, kopiyek cihêreng ji guhêrbarên herêmî tê çêkirin.
Q #2) Çima Recursion tê bikaranîn?
Bersiv: Recursion ji bo çareserkirina wan pirsgirêkan tê bikaranîn ku dikarin li ser yên piçûk werin dabeş kirin û hemî pirsgirêk bi pirsgirêkek piçûktir were diyar kirin. kompleks bi karanîna nêzîkatiyek dubarekirî were çareser kirin. Ji xeynî pirsgirêkên ku ji bo wan tevliheviya demê ne pirsgirêk e, vegerandinê bikar bînin.
Q #3) Feydeyên çi neVegerandin?
Bersiv:
Feydeyên Rekursionê ev in:
- Dîvegerandin banga zêde kêm dike fonksîyonê.
- Vegerandin rê dide me ku em pirsgirêkan bi hêsanî çareser bikin dema ku li gorî nêzîkatiya dubarekirî tê berhev kirin.
Q #4) Kîjan çêtir e - Vegerandin an dubarekirin?
Bersiv: Recursion bangên dubare dike heta ku fonksiyona bingehîn bigihîje. Ji ber vê yekê ji bo her gazîkirina fonksiyonê bîranînek li ser stikê tê hilanîn.
Li hêla din veguheztinek zêde bi bîra bîranînê tune. Pêkanîna vegerê ji nêzîkatiya dubareker hêdîtir e. Vegerandin qebareya kodê kêm dike dema ku nêzîkbûna dubare kodê mezin dike.
Q #5) Awantajên Vegerandinê li ser dubarekirinê çi ne?
Bersiv:
- Vegerandin kodê zelaltir û kurttir dike.
- Vegerandin ji nêzîkatiya dubarekirinê çêtir e ji bo pirsgirêkên mîna Birca Hanoi, dar. gerguhêz û hwd.
- Çawa ku her bangek fonksiyonê bîranîna li ser stakê tê hilanîn, Recursion bêtir bîranîn bikar tîne.
- Performansa vegerandinê ji nêzîkatiya dubarekirinê hêdîtir e.
Encam
Zimanê bernamesaziyê çi dibe bila bibe di nermalavê de veger têgehek pir girîng e. Vegerandin bi piranî di çareserkirina pirsgirêkên strukturên daneyê yên mîna bircên Hanoi, gerokên daran, navnîşên girêdayî, hwd de tê bikar anîn. Her çend ew bêtir bîranîn digire.vegerandin kodê sadetir û zelaltir dike.
Me di vê tutorialê de hemî der barê Vegerandinê de lêkolîn kir. Her weha me gelek mînakên bernamesaziyê ji bo têgihiştinek çêtir pêk anîne.