Mafunzo haya ya Kina juu ya Kujirudia katika Java Yanafafanua Urudiaji ni nini kwa Mifano, Aina, na Dhana Husika. Pia inashughulikia Recursion Vs Iteration:
Kutoka kwa mafunzo yetu ya awali katika Java, tumeona mbinu ya kurudia ambapo tunatangaza kitanzi na kisha kupitia muundo wa data kwa njia ya kurudia kwa kuchukua kipengele kimoja kwa muda.
Tumeona pia mtiririko wa masharti ambapo tena tunaweka tofauti ya kitanzi kimoja na kurudia kipande cha msimbo hadi utofauti wa kitanzi utimize masharti. Linapokuja suala la simu za kukokotoa, tulichunguza mbinu ya kurudia kwa simu za chaguo za kukokotoa pia.
Katika somo hili, tutajadili mbinu tofauti ya kupanga programu yaani mbinu ya Kujirudia.
Kujirudia Ni Nini Katika Java?
Urejeshaji ni mchakato ambao kitendakazi au mbinu hujiita tena na tena. Kitendaji hiki kinachoitwa tena na tena ama moja kwa moja au kwa njia isiyo ya moja kwa moja inaitwa "tendakazi ya kujirudia".
Tutaona mifano mbalimbali ili kuelewa urejeshaji. Sasa hebu tuone sintaksia ya urejeshaji.
Sintaksia ya urejeshaji
Njia yoyote inayotekeleza Urudiaji ina sehemu mbili za msingi:
- Mbinu ya kupiga simu ambayo inaweza kujiita yenyewe, yaani, kujirudia
- Sharti ambalo litasimamisha ujirudiaji.
Kumbuka kwamba sharti la awali linahitajika kwa mbinu yoyote ya kujirudia kama, ikiwa hatutafanya hivyo. kuvunjarecursion basi itaendelea kufanya kazi bila kikomo na kusababisha kufurika kwa rafu.
Sintaksia ya jumla ya urejeshaji ni kama ifuatavyo:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Kumbuka kwamba sharti pia linaitwa hali ya msingi. Tutajadili zaidi kuhusu hali ya msingi katika sehemu inayofuata.
Kuelewa Kujirudia Katika Java
Katika sehemu hii, tutajaribu kuelewa mchakato wa kujirudia na kuona jinsi unavyofanyika. Tutajifunza kuhusu hali ya msingi, kufurika kwa rafu, na kuona jinsi tatizo fulani linavyoweza kutatuliwa kwa kujirudia na maelezo mengine kama hayo.
Hali ya Msingi wa Kujirudia
Wakati wa kuandika programu inayojirudia, tunapaswa kwanza toa suluhisho kwa kesi ya msingi. Kisha tunaeleza tatizo kubwa zaidi kulingana na matatizo madogo zaidi.
Kama mfano, tunaweza kuchukua tatizo la kawaida la kukokotoa hali halisi ya nambari. Kwa kuzingatia nambari n, inabidi tutafute kipengele cha n kinachoashiria n!
Sasa hebu tutekeleze mpango wa kukokotoa n factorial (n!) kwa kutumia urejeshaji.
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); } }Pato
Katika mpango huu, tunaweza kuona kwamba hali (n=1) ndiyo hali ya msingi na hali hii inapofikiwa, chaguo la kukokotoa linarudi 1. Sehemu nyingine ya chaguo za kukokotoa ni simu inayorudiwa. Lakini kila wakati njia ya kujirudia inapoitwa, n inapunguzwa kwa 1.
Hivyo tunaweza kuhitimisha kwamba hatimaye thamani ya n itakuwa 1 au chini ya 1 na kwa wakati huu.uhakika, njia itarudi thamani 1. Hali hii ya msingi itafikiwa na kazi itaacha. Kumbuka kuwa thamani ya n inaweza kuwa chochote mradi inakidhi hali ya msingi.
Utatuzi wa Matatizo kwa Kutumia Urejeshaji
Wazo la msingi la kutumia urejeshaji ni kueleza tatizo kubwa zaidi katika suala la matatizo madogo. Pia, tunahitaji kuongeza masharti ya msingi moja au zaidi ili tuweze kujirudia.
Hii tayari imeonyeshwa katika mfano wa hali halisi hapo juu. Katika mpango huu, tulionyesha n factorial (n!) kulingana na thamani ndogo zaidi na tulikuwa na hali ya msingi (n =1) ili n inapofika 1, tunaweza kuacha mbinu ya kujirudia.
Hitilafu ya Kuzidisha Rafu Katika Urejeshaji
Tunafahamu kuwa mbinu au chaguo la kukokotoa linapoitwa, hali ya utendakazi huhifadhiwa kwenye rafu na hurejeshwa wakati chaguo la kukokotoa linaporudi. Rafu inatumika kwa mbinu ya kujirudia.
Lakini katika hali ya kujirudia, tatizo linaweza kutokea ikiwa hatutafafanua hali ya msingi au hali ya msingi ikiwa haijafikiwa au kutekelezwa. Hali hii ikitokea basi kufurika kwa rafu kunaweza kutokea.
Hebu tuzingatie mfano ulio hapa chini wa nukuu halisi.
Hapa tumetoa hali mbaya ya msingi, 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); } }Kwa hivyo wakati n > 100 njia itarudi 1 lakini kujirudia hakutaacha. Thamani ya n itaendelea kupungua kwa muda usiojulikana kama hapohakuna sharti lingine la kuizuia. Hii itaendelea hadi rafu itafurika.
Kesi nyingine itakuwa wakati thamani ya n 100. Katika hali hii, vile vile mbinu haitawahi kutekeleza hali ya msingi na kusababisha kufurika kwa rafu.
Mifano ya Kujirudia Katika Java
Katika sehemu hii, tutatekeleza mifano ifuatayo kwa kutumia recursion.
#1) Fibonacci Series Kwa Kutumia Recursion
Msururu wa Fibonacci umetolewa na,
1,1,2,3,5,8,13,21, 34,55,…
Mfuatano ulio hapo juu unaonyesha kuwa kipengele cha sasa ni jumla ya vipengele viwili vilivyotangulia. Pia, kipengele cha kwanza katika mfululizo wa Fibonacci ni 1.
Kwa hiyo kwa ujumla ikiwa n ni nambari ya sasa, basi inatolewa na jumla ya (n-1) na (n-2). Kwa vile kipengele cha sasa kinaonyeshwa kulingana na vipengele vilivyotangulia, tunaweza kueleza tatizo hili kwa kutumia urejeshaji.
Mpango wa kutekeleza mfululizo wa Fibonacci umetolewa hapa chini:
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) + " "); } } } Pato
#2) Angalia Kama Nambari Ni Palindrome Kwa Kutumia Recursion
Palindrome ni mfuatano ambao ni sawa wakati sisi isome kutoka kushoto kwenda kulia au kulia kwenda kushoto.
Tukipewa nambari 121, tunaona kwamba tunapoisoma kutoka kushoto kwenda kulia na kulia kwenda kushoto ni sawa. Kwa hivyo nambari 121 ni palindrome.
Hebu tuchukue nambari nyingine, 1242. Tunapoisoma kutoka kushoto kwenda kulia ni 1242 na inaposomwa kutoka kulia kwenda kushoto inasomeka kama 2421. Kwa hivyo hii sio palindrome.
Sisitekeleza programu ya palindrome kwa kugeuza tarakimu za nambari na kulinganisha nambari iliyotolewa kwa kujirudiarudia na uwakilishi wake kinyume.
Programu iliyo hapa chini inatekeleza mpango wa kuangalia 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."); } } }Toleo
#3) Java Reverse Recursion
Kwa kuzingatia mfuatano wa “Hujambo” inatubidi kuugeuza ili mfuatano wa matokeo ni “olleH”.
Hii inafanywa kwa kutumia marudio. Kuanzia herufi ya mwisho katika mfuatano huo tunachapisha kila herufi kwa kujirudia hadi vibambo vyote kwenye mfuatano viishe.
Programu iliyo hapa chini hutumia urejeshaji ili kubadilisha mfuatano fulani.
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); } } Pato
#4) Utafutaji Binary Urudiaji wa Java
Algoriti ya utafutaji wa binary ni algoriti maarufu ya kutafuta. Katika algoriti hii, kwa kuzingatia safu iliyopangwa ya vipengee n, tunatafuta safu hii kwa kipengele muhimu kilichotolewa. Hapo mwanzo, tunagawanya safu katika nusu mbili kwa kutafuta kipengele cha katikati cha safu.
Kisha kulingana na ikiwa katikati ya ufunguo tunapunguza utafutaji wetu katika nusu ya kwanza au ya pili ya safu. Kwa njia hii mchakato sawa unarudiwa hadi eneo la vipengee muhimu lipatikane.
Tutatekeleza algoriti hii kwa kutumia urejeshaji hapa.
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) Tafuta Thamani Ya Chini Katika Mkusanyiko Kwa Kutumia Urejeshaji
Kwa kutumia urejeshaji pia tunaweza kupata thamani ya chini zaidi katika safu.
TheProgramu ya Java ili kupata thamani ya chini zaidi katika safu imetolewa hapa chini.
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"); } }Pato
Hizi ni baadhi ya mifano ya kujirudia. Kando na mifano hii, matatizo mengine mengi katika programu yanaweza kutekelezwa kwa kutumia mbinu za kujirudia.
Aina za Urudiaji
Urejeshaji ni wa aina mbili kulingana na wakati simu inapigwa njia ya kujirudia.
Nazo ni:
#1) Urejeshaji Mkia
Wakati mwito kwa njia ya kujirudi ndio kauli ya mwisho. inatekelezwa ndani ya mbinu ya kujirudia, inaitwa "Mkia wa Kujirudia".
Katika kurudia kwa mkia, kauli ya simu inayorudiwa kawaida hutekelezwa pamoja na taarifa ya kurejesha ya mbinu.
syntax ya jumla ya urejeshaji wa mkia imetolewa hapa chini:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Urejeshaji wa Kichwa
Urejeshaji wa kichwa ni mbinu yoyote ya kujirudia ambayo si kurudi nyuma kwa mkia. Kwa hivyo hata kujirudia kwa ujumla ni kujirudia kwa mbele.
Sintaksia ya kujirudia kwa kichwa ni kama ifuatavyo:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Kurudia Vs Kurudia Katika Java
| Recursion | Iteration |
|---|---|
| Recursion ni mchakato ambapo mbinu hujiita mara kwa mara hadi sharti la msingi litimizwe. | Marudio ni mchakato ambao kipande cha msimbo hutekelezwa mara kwa mara kwa idadi maalum ya nyakati au hadi sharti litimizwe. |
| Je, ni maombi ya vitendakazi. | Inatumika. kwa vitanzi. |
| Inafanya kazi vizuri kwasaizi ndogo ya msimbo. | Hufanya kazi vyema kwa saizi kubwa ya msimbo. |
| Hutumia kumbukumbu zaidi kila simu inayojirudia inaposukumwa kwenye rafu | kumbukumbu pungufu kwa kulinganisha inatumika. |
| Ni vigumu kutatua na kudumisha | Rahisi kutatua na kudumisha |
| Matokeo ya kufurika kwa rafu ikiwa msingi hali haijabainishwa au haijafikiwa. | Inaweza kutekeleza kwa muda usio na kikomo lakini hatimaye itasimamisha utekelezaji kwa hitilafu zozote za kumbukumbu |
| Utata wa muda ni mkubwa sana. | Utata wa muda uko katika upande wa chini. |
Maswali Yanayoulizwa Mara kwa Mara
Q #1) Je, Recursion hufanyaje kazi katika Java?
Jibu: Katika kurudia, kitendakazi cha kujirudi hujiita mara kwa mara hadi hali ya msingi itimizwe. Kumbukumbu ya kitendakazi kinachoitwa husukumwa kwenye mrundikano ulio juu ya kumbukumbu kwa ajili ya kitendakazi cha kupiga simu. Kwa kila simu ya kukokotoa, nakala tofauti ya viambajengo vya ndani hufanywa.
Q #2) Kwa nini Recursion inatumika?
Jibu: Recursion hutumika kutatua matatizo ambayo yanaweza kugawanywa katika madogo na tatizo zima linaweza kuonyeshwa kwa suala la tatizo dogo.
Recursion pia hutumika kwa matatizo ambayo ni makubwa sana. changamano kutatuliwa kwa kutumia mbinu ya kurudiarudia. Kando na matatizo ambayo ugumu wa wakati sio suala, tumia kujirudia.
Q #3) Je, ni faida gani zaKujirudia?
Jibu:
Faida za Kujirudia ni pamoja na:
- Kujirudia hupunguza simu zisizohitajika ya utendakazi.
- Recursion huturuhusu kutatua matatizo kwa urahisi ikilinganishwa na mbinu ya kurudia.
Q #4) Ipi ni bora - Kujirudia au Kurudia?
Jibu: Recursion hupiga simu zinazorudiwa hadi kitendakazi cha msingi kifikiwe. Kwa hivyo kuna sehemu ya juu ya kumbukumbu kwani kumbukumbu kwa kila simu ya kukokotoa inasukumwa kwenye rafu.
Marudio kwa upande mwingine hayana kumbukumbu nyingi. Utekelezaji wa kujirudia ni wa polepole kuliko mbinu ya kurudia. Urejeshaji hupunguza saizi ya msimbo huku mbinu ya kurudia ikifanya msimbo kuwa mkubwa.
Q #5) Je, Faida za Kujirudia Zaidi ya Kurudiarudia ni zipi?
Jibu:
- Urejeshaji hufanya msimbo kuwa wazi na mfupi zaidi.
- Urejeshaji ni bora kuliko mbinu ya mara kwa mara ya matatizo kama vile Mnara wa Hanoi, mti traversals, n.k.
- Kwa vile kila simu ya kukokotoa ina kumbukumbu inayosukumwa kwenye rafu, Recursion hutumia kumbukumbu zaidi.
- Utendaji wa kujirudia ni wa polepole kuliko mbinu ya kurudia.
Hitimisho
Recursion ni dhana muhimu sana katika programu bila kujali lugha ya programu. Urejeshaji mara nyingi hutumika katika kutatua matatizo ya muundo wa data kama vile minara ya Hanoi, mapito ya miti, orodha zilizounganishwa, n.k. Ingawa inachukua kumbukumbu zaidi,recursion hurahisisha msimbo na kueleweka zaidi.
Tumechunguza yote kuhusu Kujirudia katika somo hili. Pia tumetekeleza mifano mingi ya upangaji kwa uelewa mzuri wa dhana.