Java-ում ռեկուրսիայի վերաբերյալ այս խորը ձեռնարկը բացատրում է, թե ինչ է ռեկուրսիան օրինակներով, տեսակներով և հարակից հասկացություններով: Այն նաև ընդգրկում է Recursion vs Iteration:
Java-ի մեր ավելի վաղ ձեռնարկներից մենք տեսել ենք կրկնվող մոտեցումը, որտեղ մենք հայտարարում ենք հանգույց և այնուհետև անցնում ենք տվյալների կառուցվածքի միջով կրկնվող ձևով՝ վերցնելով մեկ տարր ժամանակ:
Մենք նաև տեսել ենք պայմանական հոսքը, որտեղ կրկին պահում ենք մեկ հանգույց փոփոխական և կրկնում ենք կոդի մի հատված, մինչև որ հանգույց փոփոխականը համապատասխանի պայմանին: Երբ խոսքը վերաբերում է ֆունկցիայի կանչերին, մենք ուսումնասիրել ենք նաև գործառույթի կանչերի կրկնվող մոտեցումը:> Այս ձեռնարկում մենք կքննարկենք ծրագրավորման այլ մոտեցում, այսինքն՝ ռեկուրսիվ մոտեցում:
Ի՞նչ է ռեկուրսը Java-ում:
Ռեկուրսիան գործընթաց է, որի միջոցով ֆունկցիան կամ մեթոդը կրկին ու կրկին կանչում է իրեն: Այս ֆունկցիան, որը կրկին ու կրկին կանչվում է ուղղակիորեն կամ անուղղակի, կոչվում է «ռեկուրսիվ ֆունկցիա»:
Մենք կտեսնենք տարբեր օրինակներ՝ ռեկուրսիան հասկանալու համար: Այժմ տեսնենք ռեկուրսիայի շարահյուսությունը:
Recursion Syntax
Ցանկացած մեթոդ, որն իրականացնում է Recursion, ունի երկու հիմնական մաս.
- Մեթոդի կանչ, որը կարող է իրեն անվանել, այսինքն՝ ռեկուրսիվ
- Նախապայման, որը կդադարեցնի ռեկուրսիան:
Նկատի ունեցեք, որ նախապայմանն անհրաժեշտ է ցանկացած ռեկուրսիվ մեթոդի համար, քանի որ եթե մենք դա չանենք կոտրել էռեկուրսիան, այնուհետև այն կշարունակի աշխատել անվերջ և կհանգեցնի կուտակիչի արտահոսքի:
Ռեկուրսիայի ընդհանուր շարահյուսությունը հետևյալն է.
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Նշեք, որ նախապայմանը նաև կոչվում է. բազային վիճակ. Մենք ավելի շատ կքննարկենք հիմնական պայմանի մասին հաջորդ բաժնում:
Հասկանալով ռեկուրսիան Java-ում
Այս բաժնում մենք կփորձենք հասկանալ ռեկուրսիայի գործընթացը և տեսնել, թե ինչպես է այն տեղի ունենում: Մենք կիմանանք բազային պայմանի, կույտի արտահոսքի մասին և կտեսնենք, թե ինչպես կարելի է որոշակի խնդիր լուծել ռեկուրսիայով և նման այլ մանրամասներով:
Recursion Base Condition
Ռեկուրսիվ ծրագիրը գրելիս մենք պետք է նախ տրամադրեք լուծումը բազային գործի համար: Այնուհետև ավելի մեծ խնդիրն արտահայտում ենք ավելի փոքր խնդիրներով:
Որպես օրինակ, կարող ենք վերցնել թվի գործակիցը հաշվարկելու դասական խնդիր: Հաշվի առնելով n թիվը, մենք պետք է գտնենք n-ի գործակիցը, որը նշանակվում է n-ով:
Այժմ եկեք իրականացնենք ծրագիրը՝ հաշվարկելու n գործոնը (n!) օգտագործելով ռեկուրսիա:
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); } }Արդյունք
Այս ծրագրում մենք կարող ենք տեսնել, որ պայմանը (n=1) բազային պայմանն է, և երբ այս պայմանը հասնում է, ֆունկցիան վերադարձնում է 1: Ֆունկցիայի մյուս մասը ռեկուրսիվ կանչն է: Բայց ամեն անգամ, երբ ռեկուրսիվ մեթոդը կանչվում է, n-ը նվազում է 1-ով:
Այսպիսով մենք կարող ենք եզրակացնել, որ ի վերջո n-ի արժեքը կդառնա 1 կամ 1-ից փոքր, և այս դեպքումկետը, մեթոդը կվերադարձնի 1 արժեքը: Այս բազային պայմանը կհասնի, և գործառույթը կդադարի: Նկատի ունեցեք, որ n-ի արժեքը կարող է լինել ցանկացած բան, քանի դեռ այն բավարարում է բազային պայմանին:
Խնդրի լուծում՝ օգտագործելով ռեկուրսիա
Հիմնական գաղափարը, որն օգտագործվում է ռեկուրսիայի օգտագործման հիմքում, ավելի մեծ խնդիրն արտահայտելն է. ավելի փոքր խնդիրներ. Բացի այդ, մենք պետք է ավելացնենք մեկ կամ մի քանի բազային պայմաններ, որպեսզի կարողանանք դուրս գալ ռեկուրսիայից:
Սա արդեն ցուցադրվել է վերը նշված գործոնային օրինակում: Այս ծրագրում մենք արտահայտեցինք n գործոնը (n!) ավելի փոքր արժեքներով և ունեինք բազային պայման (n =1), որպեսզի երբ n-ը հասնի 1-ի, մենք կարողանանք դուրս գալ ռեկուրսիվ մեթոդից:
Stack Overflow Error In Recursion
Մենք տեղյակ ենք, որ երբ կանչվում է որևէ մեթոդ կամ ֆունկցիա, ֆունկցիայի վիճակը պահվում է կույտի վրա և վերականգնվում է, երբ ֆունկցիան վերադառնում է: Ստեկը նույնպես օգտագործվում է ռեկուրսիվ մեթոդի համար:
Սակայն ռեկուրսիայի դեպքում կարող է խնդիր առաջանալ, եթե մենք չսահմանենք բազային պայմանը կամ երբ բազային պայմանը ինչ-որ կերպ չի հասնում կամ չի կատարվում: Եթե այս իրավիճակը տեղի ունենա, ապա կարող է առաջանալ կույտի արտահոսք:
Եկեք դիտարկենք գործոնային նշման ստորև բերված օրինակը:
Այստեղ մենք սխալ բազային պայման ենք տվել՝ 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); } }Այսպիսով, երբ n > 100 մեթոդը կվերադարձնի 1, բայց ռեկուրսիան չի դադարի: n-ի արժեքը կշարունակի նվազել անորոշ ժամանակովդա դադարեցնելու այլ պայման չկա: Սա կշարունակվի այնքան ժամանակ, մինչև կույտը լցվի:
Մեկ այլ դեպք կլինի, երբ n 100. Այս դեպքում ևս մեթոդը երբեք չի կատարի բազային պայմանը և կհանգեցնի կույտի արտահոսքի:
Recursion Օրինակներ Java-ում
Այս բաժնում մենք կիրագործենք հետևյալ օրինակները՝ օգտագործելով ռեկուրսիա։
#1) Ֆիբոնաչիի շարքը ռեկուրսիայով
Ֆիբոնաչիի շարքը տրված է,
1,1,2,3,5,8,13,21, 34,55,…
Վերոնշյալ հաջորդականությունը ցույց է տալիս, որ ընթացիկ տարրը նախորդ երկու տարրերի գումարն է: Նաև Ֆիբոնաչիի շարքի առաջին տարրը 1-ն է:
Այսպիսով, ընդհանուր առմամբ, եթե n-ն ընթացիկ թիվն է, ապա այն տրվում է (n-1) և (n-2) գումարով: Քանի որ ընթացիկ տարրն արտահայտված է նախորդ տարրերով, մենք կարող ենք այս խնդիրը արտահայտել ռեկուրսիայի միջոցով:
Ֆիբոնաչիի շարքն իրականացնելու ծրագիրը տրված է ստորև.
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) + " "); } } } Ելք
#2) Ստուգեք, թե արդյոք թիվը պալինդրոմ է, օգտագործելով ռեկուրսիան
Պալինդրոմը հաջորդականություն է, որը հավասար է, երբ մենք կարդալ այն ձախից աջ կամ աջից ձախ:
Տրված 121 թիվը, մենք տեսնում ենք, որ երբ այն կարդում ենք ձախից աջ և աջից ձախ, այն հավասար է: Այսպիսով, 121 թիվը պալինդրոմ է:
Վերցնենք մեկ այլ թիվ՝ 1242-ը: Երբ այն կարդում ենք ձախից աջ, այն 1242 է, իսկ երբ աջից ձախ կարդացվում է, այն կարդում է որպես 2421: Այսպիսով, սա պալինդրոմ չէ:
Մենքիրականացրե՛ք պալինդրոմ ծրագիրը՝ հակադարձելով թվերի թվանշանները և ռեկուրսիվորեն համեմատելով տրված թիվը նրա հակադարձ ներկայացման հետ։
Ստորև նշված ծրագիրն իրականացնում է պալինդրոմը ստուգելու ծրագիրը։
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."); } } }Ելք
արդյունք տողը «olleH» է:
Սա արվում է ռեկուրսիայի միջոցով: Սկսած տողի վերջին նիշից՝ մենք ռեկուրսիվորեն տպում ենք յուրաքանչյուր նիշ, մինչև որ տողի բոլոր նիշերը սպառվեն:
Ստորև բերված ծրագիրը օգտագործում է ռեկուրսիա՝ տրված տողը հակադարձելու համար:
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); } } Ելք
#4) Երկուական որոնման Java Recursion
Երկուական որոնման ալգորիթմը որոնման հայտնի ալգորիթմ է: Այս ալգորիթմում, հաշվի առնելով n տարրերի տեսակավորված զանգվածը, մենք որոնում ենք այս զանգվածում տվյալ հիմնական տարրը: Սկզբում զանգվածը բաժանում ենք երկու կեսի` գտնելով զանգվածի միջին տարրը:
Այնուհետև, կախված նրանից, թե բանալու միջինը մենք սահմանափակում ենք մեր որոնումը զանգվածի առաջին կամ երկրորդ կեսում: Այս կերպ նույն գործընթացը կրկնվում է այնքան ժամանակ, մինչև գտնվի հիմնական տարրերի գտնվելու վայրը:
Այս ալգորիթմը կիրականացնենք ռեկուրսի միջոցով այստեղ:
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); } } Ելք
#5) Գտեք նվազագույն արժեքը զանգվածում, օգտագործելով Recursion
Օգտագործելով ռեկուրսիա մենք կարող ենք նաև գտնել զանգվածի նվազագույն արժեքը:
0> TheԶանգվածում նվազագույն արժեքը գտնելու Java ծրագիրը տրված է ստորև:
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"); } }Ելք
Սրանք մի քանիսն են ռեկուրսիայի օրինակներ. Բացի այս օրինակներից, ծրագրաշարի բազմաթիվ այլ խնդիրներ կարող են իրականացվել ռեկուրսիվ տեխնիկայի միջոցով:
Ռեկուրսիայի տեսակները
Ռեկուրսիան երկու տեսակի է` հիմնված այն բանի վրա, թե երբ է զանգը կատարվում դեպի ռեկուրսիվ մեթոդը։
Դրանք են՝
#1) Tail Recursion
Երբ զանգը դեպի ռեկուրսիվ մեթոդը վերջին հայտարարությունն է։ Կատարված ռեկուրսիվ մեթոդի ներսում, այն կոչվում է «Tail Recursion»:
Պոչի ռեկուրսիայում, ռեկուրսիվ կանչի հայտարարությունը սովորաբար կատարվում է մեթոդի վերադարձի հայտարարության հետ մեկտեղ:
The tail recursion: պոչի ռեկուրսիայի ընդհանուր շարահյուսությունը տրված է ստորև.
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Գլխի ռեկուրսիա
Գլխի ռեկուրսիա ցանկացած ռեկուրսիվ մոտեցում է, որը պոչի ռեկուրսիա չէ: Այսպիսով, նույնիսկ ընդհանուր ռեկուրսիան առջևում է:
Գլխի ռեկուրսիայի շարահյուսությունը հետևյալն է.
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Recursion vs Iteration Java-ում
| Recursion | Iteration |
|---|---|
| Recursion-ը գործընթաց է, որտեղ մեթոդն իրեն բազմիցս կանչում է մինչև բազային պայմանը բավարարված լինի: | Iteration-ը. պրոցես, որով կոդի կտորը բազմիցս կատարվում է վերջավոր թվով անգամ կամ մինչև որևէ պայման չկատարվի: |
| Արդյո՞ք հավելվածը գործառույթների համար է: loops-ի համար: | |
| Լավ է աշխատումկոդի ավելի փոքր չափը: | Լավ է աշխատում ավելի մեծ կոդի չափի դեպքում: |
| Օգտագործում է ավելի շատ հիշողություն, քանի որ յուրաքանչյուր ռեկուրսիվ զանգ տեղափոխվում է բուրգ | Համեմատաբար ավելի քիչ հիշողություն օգտագործվում է: |
| Դժվար է վրիպազերծել և պահպանել | Ավելի հեշտ է վրիպազերծել և պահպանել |
| Արդյունքում կույտից դուրս է գալիս, եթե բազան պայմանը նշված չէ կամ չի հասել: | Կարող է գործել անվերջ, բայց ի վերջո կդադարեցնի կատարումը ցանկացած հիշողության սխալներով |
| Ժամանակի բարդությունը շատ մեծ է: | Ժամանակի բարդությունը համեմատաբար ցածր է: |
Հաճախակի տրվող հարցեր
Հ #1) Ինչպե՞ս է աշխատում Recursion-ը Java-ում:
Պատասխան․ Ռեկուրսիայի ժամանակ ռեկուրսիվ ֆունկցիան իրեն բազմիցս կանչում է մինչև բազային պայմանը բավարարված լինի։ Կանչված ֆունկցիայի հիշողությունը դրվում է կանչող ֆունկցիայի հիշողության վերևի մասում: Յուրաքանչյուր ֆունկցիայի կանչի համար կատարվում է տեղական փոփոխականների առանձին պատճեն:
Q #2) Ինչու է օգտագործվում Recursion-ը:
Պատասխան. Ռեկուրսիան օգտագործվում է այն խնդիրների լուծման համար, որոնք կարելի է բաժանել փոքրերի, և ամբողջ խնդիրը կարող է արտահայտվել փոքր խնդրի տեսքով:
Ռեկուրսիան օգտագործվում է նաև այն խնդիրների համար, որոնք նույնպես շատ են համալիր, որը պետք է լուծվի կրկնվող մոտեցման միջոցով: Բացի այն խնդիրներից, որոնց համար ժամանակի բարդությունը խնդիր չէ, օգտագործեք ռեկուրսիա:
Հ #3) Որո՞նք են օգուտներըՌեկուրսիա՞ն:
Պատասխան.
Recursion-ի առավելությունները ներառում են. ֆունկցիայի:
Հ #4) Ո՞րն է ավելի լավ՝ ռեկուրսիա՞ն, թե՞ կրկնությունը:
Պատասխան․ Այսպիսով, կա հիշողության գերբեռնվածություն, քանի որ յուրաքանչյուր ֆունկցիայի կանչի հիշողությունը դրվում է փաթեթ:
Մյուս կողմից, կրկնությունը մեծ հիշողություն չունի: Ռեկուրսիայի կատարումն ավելի դանդաղ է, քան կրկնվող մոտեցումը: Ռեկուրսիան նվազեցնում է կոդի չափը, մինչդեռ կրկնվող մոտեցումը մեծացնում է կոդը:
Q #5) Որո՞նք են ռեկուրսիայի առավելությունները կրկնության նկատմամբ:
Պատասխան․ անցումներ և այլն:
Եզրակացություն
Ռեկուրսիան շատ կարևոր հասկացություն է ծրագրային ապահովման մեջ՝ անկախ ծրագրավորման լեզվից: Ռեկուրսիան հիմնականում օգտագործվում է տվյալների կառուցվածքի խնդիրների լուծման համար, ինչպիսիք են Հանոյի աշտարակները, ծառերի անցումները, կապակցված ցուցակները և այլն: Թեև այն ավելի շատ հիշողություն է պահանջում,recursion-ը կոդն ավելի պարզ և հստակ է դարձնում:
Մենք ուսումնասիրել ենք ամեն ինչ Recursion-ի մասին այս ձեռնարկում: Մենք նաև իրականացրել ենք բազմաթիվ ծրագրավորման օրինակներ՝ հայեցակարգն ավելի լավ հասկանալու համար: