जावा में रिकर्सन पर यह गहन ट्यूटोरियल उदाहरणों, प्रकारों और संबंधित अवधारणाओं के साथ रिकर्सन क्या है इसकी व्याख्या करता है। इसमें पुनरावर्तन बनाम पुनरावृत्ति को भी शामिल किया गया है:
जावा में हमारे पहले के ट्यूटोरियल से, हमने पुनरावृत्त दृष्टिकोण देखा है जिसमें हम एक लूप की घोषणा करते हैं और फिर डेटा संरचना के माध्यम से पुनरावृत्त तरीके से एक तत्व लेते हुए पार करते हैं। एक समय।
हमने सशर्त प्रवाह भी देखा है जहां फिर से हम एक लूप चर रखते हैं और कोड का एक टुकड़ा तब तक दोहराते हैं जब तक लूप चर शर्त को पूरा नहीं करता। जब फ़ंक्शन कॉल की बात आती है, तो हमने फ़ंक्शन कॉल के लिए पुनरावृत्त दृष्टिकोण का भी पता लगाया।
जावा में रिकर्सन क्या है?
रिकर्सन एक ऐसी प्रक्रिया है जिसके द्वारा कोई फ़ंक्शन या कोई विधि स्वयं को बार-बार कॉल करती है। यह फ़ंक्शन जिसे प्रत्यक्ष या अप्रत्यक्ष रूप से बार-बार कॉल किया जाता है, "रिकर्सिव फ़ंक्शन" कहलाता है।
रिकर्सन को समझने के लिए हम विभिन्न उदाहरण देखेंगे। अब हम रिकर्सन का सिंटैक्स देखते हैं।
रिकर्सन सिंटैक्स
रिकर्सन को लागू करने वाली कोई भी विधि के दो मूल भाग होते हैं:
- मेथड कॉल जो खुद को कॉल कर सकता है यानी रिकर्सिव
- एक पूर्व शर्त जो रिकर्सन को रोक देगा। तोड़ दोरिकर्सन तो यह असीमित रूप से चलता रहेगा और इसका परिणाम स्टैक ओवरफ्लो होगा। आधार स्थिति। हम अगले खंड में आधार स्थिति के बारे में अधिक चर्चा करेंगे।
जावा में पुनरावर्तन को समझना
इस खंड में, हम पुनरावर्तन प्रक्रिया को समझने की कोशिश करेंगे और देखेंगे कि यह कैसे होता है। हम आधार स्थिति, स्टैक ओवरफ्लो के बारे में जानेंगे और देखेंगे कि किसी विशेष समस्या को रिकर्सन और ऐसे अन्य विवरणों से कैसे हल किया जा सकता है।
रिकर्सन बेस कंडीशन
रिकर्सिव प्रोग्राम लिखते समय, हमें यह करना चाहिए पहले बेस केस के लिए समाधान प्रदान करें। फिर हम बड़ी समस्या को छोटी समस्याओं के रूप में व्यक्त करते हैं।
एक उदाहरण के रूप में, हम किसी संख्या के भाज्य की गणना करने की क्लासिक समस्या ले सकते हैं। एक संख्या 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); } }Output
इस प्रोग्राम में, हम देख सकते हैं कि कंडीशन (n=1) बेस कंडीशन है और जब यह कंडीशन पूरी हो जाती है, तो फंक्शन 1 देता है फ़ंक्शन का दूसरा भाग रिकर्सिव कॉल है। लेकिन हर बार पुनरावर्ती विधि को कहा जाता है, n को 1 से घटाया जाता है।
इस प्रकार हम यह निष्कर्ष निकाल सकते हैं कि अंततः n का मान 1 या 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) पुनरावर्तन का उपयोग करते हुए फाइबोनैचि श्रृंखला
फाइबोनैचि श्रृंखला इसके द्वारा दी गई है,
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 पढ़ता है। इस प्रकार यह एक विलोमपद नहीं है।
हमसंख्याओं के अंकों को उल्टा करके पैलिंड्रोम प्रोग्राम को लागू करें और दी गई संख्या को उसके उल्टे प्रतिनिधित्व से पुन: तुलना करें।
नीचे दिया गया प्रोग्राम पैलिंड्रोम की जांच करने के लिए प्रोग्राम को लागू करता है। आउटपुट
#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 तत्वों की एक क्रमबद्ध सरणी दी गई है, हम इस सरणी को दिए गए प्रमुख तत्व के लिए खोजते हैं। शुरुआत में, हम सरणी के मध्य तत्व को ढूंढकर सरणी को दो हिस्सों में विभाजित करते हैं।
फिर इस पर निर्भर करते हुए कि कुंजी मध्य हम अपनी खोज को सरणी के पहले या दूसरे भाग में सीमित करते हैं। इस तरह मुख्य तत्वों का स्थान मिलने तक यही प्रक्रिया दोहराई जाती है।
हम यहां पुनरावर्तन का उपयोग करके इस एल्गोरिद्म को लागू करेंगे।
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"); } }आउटपुट
ये कुछ हैं पुनरावर्तन के उदाहरण। इन उदाहरणों के अलावा, सॉफ्टवेयर में कई अन्य समस्याओं को पुनरावर्ती तकनीकों का उपयोग करके लागू किया जा सकता है। पुनरावर्ती विधि।
वे हैं:
#1) पूंछ पुनरावर्तन
जब पुनरावर्ती विधि के लिए कॉल अंतिम कथन है पुनरावर्ती विधि के अंदर निष्पादित, इसे "टेल रिकर्सन" कहा जाता है।
टेल रिकर्सन में, रिकर्सिव कॉल स्टेटमेंट को आमतौर पर विधि के रिटर्न स्टेटमेंट के साथ निष्पादित किया जाता है।
द टेल रिकर्सन के लिए सामान्य सिंटैक्स नीचे दिया गया है:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion }#2) हेड रिकर्सन
हेड रिकर्सन कोई भी रिकर्सिव अप्रोच है जो टेल रिकर्सन नहीं है। तो सामान्य रिकर्सन भी फॉरवर्ड रिकर्सन है। 25>पुनरावृत्ति
पुनरावृत्ति पुनरावर्तन एक प्रक्रिया है जहां एक विधि स्वयं को तब तक बार-बार बुलाती है जब तक कि आधार शर्त पूरी नहीं हो जाती। पुनरावर्तन है एक प्रक्रिया जिसके द्वारा कोड का एक टुकड़ा बार-बार परिमित संख्या के लिए या किसी शर्त के पूरा होने तक निष्पादित किया जाता है। क्या कार्यों के लिए आवेदन है। लागू है for लूप्स। के लिए अच्छा काम करता हैछोटे कोड आकार। बड़े कोड आकार के लिए अच्छी तरह से काम करता है। उपयोग किया जाता है। डीबग करना और बनाए रखना मुश्किल है डिबग करना और बनाए रखना आसान है बेस होने पर स्टैक ओवरफ्लो में परिणाम स्थिति निर्दिष्ट नहीं है या पूरी नहीं हुई है। अनंत रूप से निष्पादित हो सकता है लेकिन अंततः किसी भी मेमोरी त्रुटियों के साथ निष्पादन को रोक देगा समय की जटिलता बहुत अधिक है। समय जटिलता अपेक्षाकृत कम है। अक्सर पूछे जाने वाले प्रश्न
प्रश्न #1) जावा में रिकर्सन कैसे काम करता है?
जवाब: रिकर्सन में, रिकर्सिव फंक्शन खुद को तब तक बार-बार कॉल करता है जब तक कि बेस कंडीशन पूरी नहीं हो जाती। कॉल किए गए फ़ंक्शन के लिए मेमोरी को कॉलिंग फ़ंक्शन के लिए मेमोरी के शीर्ष पर स्टैक पर धकेल दिया जाता है। प्रत्येक फ़ंक्शन कॉल के लिए, स्थानीय चरों की एक अलग कॉपी बनाई जाती है।
Q #2) रिकर्सन का उपयोग क्यों किया जाता है?
उत्तर: रिकर्सन का उपयोग उन समस्याओं को हल करने के लिए किया जाता है जिन्हें छोटे-छोटे भागों में तोड़ा जा सकता है और पूरी समस्या को एक छोटी समस्या के रूप में व्यक्त किया जा सकता है।
रिकर्सन का उपयोग उन समस्याओं के लिए भी किया जाता है जो बहुत अधिक होती हैं पुनरावृत्त दृष्टिकोण का उपयोग करके हल किया जाने वाला जटिल। उन समस्याओं के अलावा जिनके लिए समय जटिलता कोई समस्या नहीं है, पुनरावर्तन का उपयोग करें।
Q #3) के क्या लाभ हैंरिकर्सन?
उत्तर:
रिकर्सन के लाभों में शामिल हैं:
- रिकर्सन अनावश्यक कॉलिंग को कम करता है
- पुनरावर्तन हमें पुनरावृत्त दृष्टिकोण की तुलना में समस्याओं को आसानी से हल करने की अनुमति देता है।
प्रश्न # 4) कौन सा बेहतर है - पुनरावृत्ति या पुनरावृत्ति?
जवाब: रिकर्सन बार-बार कॉल करता है जब तक कि बेस फंक्शन तक नहीं पहुंच जाता। इस प्रकार एक मेमोरी ओवरहेड है क्योंकि प्रत्येक फ़ंक्शन कॉल के लिए मेमोरी को स्टैक पर धकेल दिया जाता है।
दूसरी ओर इटरेशन में बहुत अधिक मेमोरी ओवरहेड नहीं होती है। पुनरावर्तन निष्पादन पुनरावृत्त दृष्टिकोण की तुलना में धीमा है। पुनरावर्तन कोड के आकार को कम करता है जबकि पुनरावृत्ति दृष्टिकोण कोड को बड़ा बनाता है।
Q #5) पुनरावृत्ति पर पुनरावर्तन के क्या लाभ हैं?
जवाब:
- रिकर्सन कोड को स्पष्ट और छोटा बनाता है।
- टॉवर ऑफ हनोई, ट्री जैसी समस्याओं के लिए पुनरावर्तन दृष्टिकोण की तुलना में रिकर्सन बेहतर है ट्रैवर्सल, आदि।
- चूंकि प्रत्येक फ़ंक्शन कॉल में स्टैक पर मेमोरी पुश की जाती है, रिकर्सन अधिक मेमोरी का उपयोग करता है।
- पुनरावृत्ति प्रदर्शन पुनरावृत्त दृष्टिकोण की तुलना में धीमा है।
निष्कर्ष
प्रोग्रामिंग भाषा के बावजूद सॉफ्टवेयर में रिकर्सन एक बहुत ही महत्वपूर्ण अवधारणा है। रिकर्सन का उपयोग ज्यादातर हनोई के टावर, ट्री ट्रैवर्सल, लिंक्ड लिस्ट आदि जैसी डेटा संरचना समस्याओं को हल करने में किया जाता है। हालांकि इसमें अधिक मेमोरी लगती है,पुनरावर्तन कोड को सरल और स्पष्ट बनाता है।
हमने इस ट्यूटोरियल में पुनरावर्तन के बारे में सब कुछ पता लगाया है। हमने अवधारणा की बेहतर समझ के लिए कई प्रोग्रामिंग उदाहरण भी लागू किए हैं।