जाभामा पुनरावृत्तिमा यो गहिरो ट्युटोरियलले उदाहरण, प्रकार, र सम्बन्धित अवधारणाहरूसँग पुनरावृत्ति के हो भनेर व्याख्या गर्दछ। यसले पुनरावृत्ति बनाम पुनरावृत्तिलाई पनि समेट्छ:
जाभामा हाम्रो अघिल्लो ट्यूटोरियलहरूबाट, हामीले पुनरावृत्ति दृष्टिकोण देख्यौं जसमा हामीले लूप घोषणा गर्छौं र त्यसपछि एक तत्व लिएर पुनरावृत्ति तरिकामा डेटा संरचना मार्फत पार गर्छौं। एक समय।
हामीले सशर्त प्रवाह पनि देख्यौं जहाँ फेरि हामी एउटा लूप चर राख्छौं र लूप भेरिएबलले सर्त पूरा नगरेसम्म कोडको टुक्रा दोहोर्याउँछौं। जब फंक्शन कलहरूको कुरा आउँछ, हामीले फंक्शन कलहरूको लागि पुनरावृत्ति दृष्टिकोण पनि खोज्यौं।
जाभामा पुनरावृत्ति के हो?
पुनरावर्ती एउटा प्रक्रिया हो जसद्वारा कुनै प्रकार्य वा विधि आफैलाई बारम्बार कल गर्छ। प्रत्यक्ष वा अप्रत्यक्ष रूपमा बारम्बार बोलाइने यो प्रकार्यलाई "पुनरावर्ती प्रकार्य" भनिन्छ।
हामी पुनरावृत्ति बुझ्न विभिन्न उदाहरणहरू देख्नेछौं। अब रिकर्सनको सिन्ट्याक्स हेरौं।
रिकर्सन सिन्ट्याक्स
रिकर्सन लागू गर्ने कुनै पनि विधिमा दुईवटा आधारभूत भागहरू हुन्छन्:
- पद्धति कल जसले आफैलाई पुनरावर्ती कल गर्न सक्छ
- एक पूर्व शर्त जसले पुनरावृत्ति रोक्न सक्छ।
ध्यान दिनुहोस् कि कुनै पनि पुनरावृत्ति विधिको लागि पूर्व शर्त आवश्यक छ, यदि हामीले गर्दैनौं भने। तोड्नुहोस्पुनरावृत्ति त्यसपछि यो असीम रूपमा चलिरहन्छ र स्ट्याक ओभरफ्लोमा परिणत हुन्छ।
पुनरावर्तीको सामान्य वाक्य रचना निम्नानुसार छ:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } ध्यान दिनुहोस् कि पूर्व शर्त पनि भनिन्छ आधार अवस्था। हामी अर्को खण्डमा आधार अवस्थाको बारेमा थप छलफल गर्नेछौं।
जाभामा पुनरावृत्ति बुझ्ने
यस खण्डमा, हामी पुनरावृत्ति प्रक्रिया बुझ्ने प्रयास गर्नेछौं र यो कसरी हुन्छ भनेर हेर्नेछौं। हामी आधार अवस्था, स्ट्याक ओभरफ्लो बारे जान्नेछौं, र रिकर्सन र अन्य त्यस्ता विवरणहरूसँग कसरी विशेष समस्या समाधान गर्न सकिन्छ भनेर हेर्नेछौं।
रिकर्सन आधार अवस्था
पुनरावर्ती कार्यक्रम लेख्दा, हामीले पहिले आधार केसको लागि समाधान प्रदान गर्नुहोस्। त्यसपछि हामी साना समस्याहरूको सन्दर्भमा ठूलो समस्या व्यक्त गर्छौं।
एक उदाहरणको रूपमा, हामीले संख्याको फ्याक्टोरियल गणना गर्ने क्लासिक समस्या लिन सक्छौं। 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) आधारभूत अवस्था हो र यो अवस्था पुगेपछि, प्रकार्यले १ फर्काउँछ भनेर देख्न सक्छौं। प्रकार्यको अर्को भाग पुनरावर्ती कल हो। तर हरेक पटक पुनरावृत्ति विधि भनिन्छ, n 1 द्वारा घटाइन्छ।
यसले हामी निष्कर्षमा पुग्न सक्छौं कि अन्ततः n को मान 1 वा 1 भन्दा कम हुनेछ र योबिन्दु, विधिले मान १ फर्काउनेछ। यो आधार अवस्था पुग्नेछ र प्रकार्य रोकिनेछ। ध्यान दिनुहोस् कि n को मान कुनै पनि हुन सक्छ जबसम्म यसले आधार अवस्थालाई सन्तुष्ट गर्दछ।
पुनरावृत्ति प्रयोग गरेर समस्या समाधान गर्ने
पुनरावर्ती प्रयोग गर्नुको पछाडिको आधारभूत विचार भनेको ठूलो समस्याको सन्दर्भमा व्यक्त गर्नु हो। साना समस्याहरू। साथै, हामीले एक वा बढी आधार सर्तहरू थप्न आवश्यक छ ताकि हामी पुनरावृत्तिबाट बाहिर आउन सक्छौं।
यो पहिले नै माथिको तथ्यात्मक उदाहरणमा देखाइएको थियो। यस कार्यक्रममा, हामीले n फ्याक्टोरियल (n!) साना मानहरूको सन्दर्भमा व्यक्त गर्यौं र आधार अवस्था (n =1) थियो ताकि जब n 1 पुग्छ, हामीले पुनरावर्ती विधि छोड्न सक्छौं।
पुनरावृत्तिमा स्ट्याक ओभरफ्लो त्रुटि
हामीलाई थाहा छ कि जब कुनै विधि वा प्रकार्यलाई कल गरिन्छ, प्रकार्यको अवस्था स्ट्याकमा भण्डारण गरिन्छ र कार्य फिर्ता हुँदा पुन: प्राप्त हुन्छ। स्ट्याक पुनरावृत्ति विधिको लागि पनि प्रयोग गरिन्छ।
तर पुनरावृत्तिको अवस्थामा, हामीले आधार अवस्था परिभाषित नगरेमा वा आधार अवस्था कुनै न कुनै रूपमा नपुगेको वा कार्यान्वयन नगर्दा समस्या आउन सक्छ। यदि यो अवस्था आयो भने स्ट्याक ओभरफ्लो उत्पन्न हुन सक्छ।
फ्याक्टोरियल नोटेशनको तलको उदाहरणलाई विचार गरौं।
यहाँ हामीले गलत आधार शर्त दिएका छौं, 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. यस अवस्थामा, साथै विधिले आधार अवस्थालाई कहिल्यै कार्यान्वयन गर्दैन र स्ट्याक ओभरफ्लोको परिणाम दिन्छ।
जाभामा पुनरावृत्ति उदाहरणहरू
यस खण्डमा, हामी निम्न उदाहरणहरू प्रयोग गरेर कार्यान्वयन गर्नेछौं पुनरावृत्ति।
#1) रिकर्सन प्रयोग गर्दै फिबोनाची शृंखला
फिबोनैकी शृङ्खला,
१,१,२,३,५,८,१३,२१,द्वारा दिइएको हो। 34,55,…
माथिको अनुक्रमले हालको तत्व अघिल्लो दुई तत्वहरूको योगफल हो भनेर देखाउँछ। साथै, फिबोनाची शृङ्खलाको पहिलो तत्व १ हो।
त्यसैले सामान्यमा यदि 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 एक प्यालिन्ड्रोम हो।
अर्को नम्बर लिनुहोस्, 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."); } } }0 आउटपुट 
#3) रिभर्स स्ट्रिङ रिकर्सन जाभा
स्ट्रिङ "हेलो" दिएर हामीले यसलाई उल्टाउनु पर्छ ताकि परिणामी स्ट्रिङ "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) बाइनरी खोज जाभा पुनरावृत्ति
बाइनरी खोज एल्गोरिदम खोजको लागि एक प्रसिद्ध एल्गोरिथ्म हो। यस एल्गोरिथ्ममा, n तत्वहरूको क्रमबद्ध एरे दिइएको छ, हामी दिइएको कुञ्जी तत्वको लागि यो एरे खोज्छौं। सुरुमा, हामी array को मध्य तत्व फेला पारेर एरेलाई दुई भागमा विभाजन गर्छौं।
त्यसपछि हामीले हाम्रो खोजलाई एरेको पहिलो वा दोस्रो आधामा सीमित गर्छौं कि होइन भन्ने कुरामा निर्भर गर्दछ। यसरी मुख्य तत्वहरूको स्थान फेला नपरेसम्म उही प्रक्रिया दोहोर्याइन्छ।
हामी यहाँ पुनरावृत्ति प्रयोग गरेर यो एल्गोरिदम लागू गर्नेछौं।
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) रिकर्सन प्रयोग गरेर एरेमा न्यूनतम मान पत्ता लगाउनुहोस्
रिकर्सन प्रयोग गरेर हामी एरेमा न्यूनतम मान पनि फेला पार्न सक्छौँ।
दएरेमा न्यूनतम मान पत्ता लगाउन जाभा प्रोग्राम तल दिइएको छ।
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"); } }आउटपुट
22>
यी केही हुन्। पुनरावृत्ति को उदाहरणहरू। यी उदाहरणहरू बाहेक, सफ्टवेयरमा अन्य धेरै समस्याहरू पुनरावृत्ति प्रविधिहरू प्रयोग गरेर कार्यान्वयन गर्न सकिन्छ।
पुनरावृत्ति प्रकारहरू
पुनरावर्ती दुई प्रकारको हुन्छ जब कल गरिन्छ। पुनरावर्ती विधि।
तिनीहरू हुन्:
#1) टेल रिकर्सन
जब पुनरावर्ती विधिमा कल अन्तिम कथन हो रिकर्सिभ मेथड भित्र कार्यान्वयन गर्दा यसलाई "टेल रिकर्सन" भनिन्छ।
टेल रिकर्सनमा, रिकर्सिभ कल स्टेटमेन्ट सामान्यतया विधिको रिटर्न स्टेटमेन्टसँगै कार्यान्वयन गरिन्छ।
द टेल रिकर्सनको लागि सामान्य सिन्ट्याक्स तल दिइएको छ:
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; } जाभामा पुनरावृत्ति बनाम पुनरावृत्ति
| पुनरावर्ती | पुनरावृत्ति |
|---|---|
| पुनरावर्ती एउटा प्रक्रिया हो जहाँ एक आधार अवस्था पूरा नभएसम्म एक विधिले आफैलाई बारम्बार कल गर्छ। | पुनरावृत्ति हो एउटा प्रक्रिया जसद्वारा कोडको टुक्रा बारम्बार सीमित संख्याको लागि वा सर्त पूरा नभएसम्म कार्यान्वयन गरिन्छ। |
| कार्यहरूको लागि अनुप्रयोग हो। | लागू हुन्छ। लुप्सका लागि। |
| का लागि राम्रोसँग काम गर्दछसानो कोड साइज। | ठूलो कोड साइजको लागि राम्रोसँग काम गर्दछ। |
| प्रत्येक पुनरावर्ती कल स्ट्याकमा पुश भएकोले थप मेमोरी प्रयोग गर्दछ | तुलनात्मक रूपमा कम मेमोरी प्रयोग गरिन्छ। |
| डिबग गर्न र मर्मत गर्न गाह्रो | डिबग गर्न र कायम राख्न सजिलो |
| स्ट्याक ओभरफ्लोमा परिणाम यदि आधार अवस्था निर्दिष्ट गरिएको छैन वा पुगिएको छैन। | असीमित रूपमा कार्यान्वयन हुन सक्छ तर अन्ततः कुनै पनि मेमोरी त्रुटिहरूको साथ कार्यान्वयन रोकिनेछ |
| समय जटिलता धेरै उच्च छ। | समय जटिलता अपेक्षाकृत तल्लो पक्षमा छ। |
बारम्बार सोधिने प्रश्नहरू
प्रश्न # 1) जाभामा पुनरावृत्तिले कसरी काम गर्छ?
उत्तर: पुनरावृत्तिमा, आधार अवस्था सन्तुष्ट नभएसम्म पुनरावृत्ति प्रकार्यले बारम्बार कल गर्छ। कल गर्ने प्रकार्यको लागि मेमोरीलाई कलिङ प्रकार्यको लागि मेमोरीको शीर्षमा स्ट्याकमा धकेलिएको छ। प्रत्येक प्रकार्य कलको लागि, स्थानीय चरहरूको छुट्टै प्रतिलिपि बनाइन्छ।
प्रश्न #2) रिकर्सन किन प्रयोग गरिन्छ?
उत्तर: पुनरावृत्तिलाई ती समस्याहरू समाधान गर्न प्रयोग गरिन्छ जसलाई सानामा विभाजन गर्न सकिन्छ र सम्पूर्ण समस्यालाई सानो समस्याको रूपमा व्यक्त गर्न सकिन्छ।
ती समस्याहरूको लागि पनि पुनरावृत्ति प्रयोग गरिन्छ। पुनरावृत्ति दृष्टिकोण प्रयोग गरेर समाधान गर्न जटिल। समस्याहरू बाहेक जसको लागि समय जटिलता कुनै मुद्दा होइन, पुनरावृत्ति प्रयोग गर्नुहोस्।
प्रश्न #3) के फाइदाहरू छन्Recursion?
उत्तर:
Recursion का फाइदाहरू समावेश छन्:
- Recursion ले अनावश्यक कल कम गर्छ कार्यको।
- पुनरावर्ती दृष्टिकोणको तुलनामा पुनरावृत्तिले हामीलाई समस्याहरू सजिलै समाधान गर्न अनुमति दिन्छ।
प्रश्न # 4) कुन राम्रो छ - पुनरावृत्ति वा पुनरावृत्ति?
उत्तर: आधार प्रकार्य नपुगेसम्म पुनरावृत्तिले दोहोर्याइएको कलहरू बनाउँछ। यसरी त्यहाँ मेमोरी ओभरहेड हुन्छ किनकि प्रत्येक प्रकार्य कलको लागि मेमोरी स्ट्याकमा पुश हुन्छ।
अर्को तर्फ पुनरावृत्तिमा धेरै मेमोरी ओभरहेड हुँदैन। पुनरावृत्ति कार्यान्वयन पुनरावृत्ति दृष्टिकोण भन्दा ढिलो छ। पुनरावृत्तिले कोडको साइज घटाउँछ जबकि पुनरावृत्ति दृष्टिकोणले कोडलाई ठूलो बनाउँछ।
प्रश्न #5) पुनरावृत्तिमा पुनरावृत्तिका फाइदाहरू के हुन्?
उत्तर:
- पुनरावर्तीले कोडलाई स्पष्ट र छोटो बनाउँछ।
- हनोईको टावर, रूख जस्ता समस्याहरूको लागि पुनरावृत्ति दृष्टिकोण भन्दा पुनरावृत्ति राम्रो छ। ट्राभर्सलहरू, आदि।
- प्रत्येक प्रकार्य कलले मेमोरीलाई स्ट्याकमा पुश गरेको हुनाले, रिकर्सनले धेरै मेमोरी प्रयोग गर्दछ।
- पुनरावर्ती कार्यसम्पादन पुनरावृत्ति दृष्टिकोण भन्दा ढिलो हुन्छ।
निष्कर्ष
प्रोग्रामिङ भाषा जुनसुकै भए पनि सफ्टवेयरमा पुनरावृत्ति एउटा महत्त्वपूर्ण अवधारणा हो। रिकर्सन प्रायः डाटा संरचना समस्याहरू समाधान गर्न प्रयोग गरिन्छ जस्तै हनोईको टावरहरू, ट्री ट्र्याभर्सलहरू, लिङ्क गरिएको सूचीहरू, आदि। यद्यपि यसले धेरै मेमोरी लिन्छ,पुनरावृत्तिले कोडलाई सरल र स्पष्ट बनाउँछ।
हामीले यस ट्यूटोरियलमा पुनरावृत्तिको बारेमा सबै कुरा खोजेका छौं। हामीले अवधारणालाई राम्रोसँग बुझ्नको लागि धेरै प्रोग्रामिङ उदाहरणहरू पनि लागू गरेका छौं।