recursion java tutorial with examples
जावा में पुनरावृत्ति पर यह गहराई से ट्यूटोरियल उदाहरण, प्रकार, और संबंधित अवधारणाओं के साथ पुनरावृत्ति क्या है बताते हैं। इसमें पुनरावर्तन बनाम पुनरावृत्ति भी शामिल है:
जावा में हमारे पहले के ट्यूटोरियल से, हमने पुनरावृति के दृष्टिकोण को देखा है जिसमें हम एक बार में एक तत्व लेकर पुनरावृत्त तरीके से एक डेटा संरचना के माध्यम से एक लूप की घोषणा करते हैं।
हमने सशर्त प्रवाह को भी देखा है जहां फिर से हम एक लूप वेरिएबल रखते हैं और कोड के एक टुकड़े को तब तक दोहराते हैं जब तक लूप वेरिएबल कंडीशन को पूरा नहीं करता है। जब फ़ंक्शन कॉल की बात आती है, तो हमने फ़ंक्शन कॉल के लिए पुनरावृत्त दृष्टिकोण का भी पता लगाया।
=> यहाँ सभी जावा ट्यूटोरियल की जाँच करें।
इस ट्यूटोरियल में, हम प्रोग्रामिंग के लिए एक अलग दृष्टिकोण यानी रिकर्सिव दृष्टिकोण पर चर्चा करेंगे।
आप क्या सीखेंगे:
- जावा में पुनरावृत्ति क्या है?
- जावा में पुनरावृत्ति बनाम Iteration
- निष्कर्ष
जावा में पुनरावृत्ति क्या है?
पुनरावृत्ति एक ऐसी प्रक्रिया है जिसके द्वारा एक फ़ंक्शन या विधि बार-बार खुद को कॉल करती है। यह फ़ंक्शन जिसे बार-बार या प्रत्यक्ष या अप्रत्यक्ष रूप से 'पुनरावर्ती फ़ंक्शन' कहा जाता है।
क़ा या बा जो बेहतर है
हम पुनरावृत्ति को समझने के लिए विभिन्न उदाहरण देखेंगे। अब रिकर्सन के सिंटैक्स को देखते हैं।
रिकर्सियन सिंटेक्स
किसी भी विधि जो पुनरावृत्ति को लागू करती है उसके दो मूल भाग होते हैं:
- मेथड कॉल जो खुद कह सकता है यानी पुनरावर्ती
- एक पूर्व शर्त जो पुनरावृत्ति को रोक देगा।
ध्यान दें कि किसी भी पुनरावर्ती विधि के लिए एक पूर्व शर्त आवश्यक है, अगर हम पुनरावृत्ति को नहीं तोड़ते हैं, तो यह असीम रूप से चलता रहेगा और परिणामस्वरूप एक अतिप्रवाह होगा।
पुनरावृत्ति का सामान्य सिंटैक्स निम्नानुसार है:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } ध्यान दें कि पूर्व शर्त को आधार स्थिति भी कहा जाता है। बेस सेक्शन के बारे में हम अगले भाग में चर्चा करेंगे।
जावा में पुनरावृत्ति को समझना
इस खंड में, हम पुनरावृत्ति प्रक्रिया को समझने की कोशिश करेंगे और देखेंगे कि यह कैसे होता है। हम आधार स्थिति, स्टैक ओवरफ्लो के बारे में जानेंगे और देखेंगे कि किसी विशेष समस्या को पुनरावृत्ति और इस तरह के अन्य विवरणों के साथ कैसे हल किया जा सकता है।
रिकर्सियन बेस कंडीशन
पुनरावर्ती कार्यक्रम लिखते समय, हमें पहले आधार मामले के लिए समाधान प्रदान करना चाहिए। फिर हम छोटी समस्याओं के संदर्भ में बड़ी समस्या को व्यक्त करते हैं।
एक के रूप में उदाहरण, हम एक संख्या के भाज्य की गणना की एक क्लासिक समस्या ले सकते हैं। एक संख्या n को देखते हुए, हमें n द्वारा चिह्नित n का एक भाज्य ज्ञात करना होगा!
अब पुनरावर्तन का उपयोग करते हुए n factorial (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); } }उत्पादन
इस कार्यक्रम में, हम देख सकते हैं कि स्थिति (एन<=1) is the base condition and when this condition is reached, the function returns 1. The else part of the function is the recursive call. But every time the recursive method is called, n is decremented by 1.
इस प्रकार हम यह निष्कर्ष निकाल सकते हैं कि अंततः n का मान 1 या 1 से कम हो जाएगा और इस बिंदु पर, विधि 1 मान लौटाएगा। यह आधार स्थिति तक पहुंच जाएगा और फ़ंक्शन बंद हो जाएगा। ध्यान दें कि जब तक यह आधार स्थिति को संतुष्ट करता है n का मूल्य कुछ भी हो सकता है।
समस्या-समाधान पुनरावृत्ति का उपयोग करना
पुनरावृत्ति का उपयोग करने के पीछे मूल विचार छोटी समस्याओं के संदर्भ में बड़ी समस्या को व्यक्त करना है। इसके अलावा, हमें एक या अधिक आधार शर्तों को जोड़ने की आवश्यकता है ताकि हम पुनरावृत्ति से बाहर आ सकें।
उपरोक्त तथ्यात्मक उदाहरण में यह पहले से ही प्रदर्शित किया गया था। इस कार्यक्रम में, हमने छोटे मूल्यों के संदर्भ में n factorial (n!) को व्यक्त किया था और इसकी आधार स्थिति थी (n)<=1) so that when n reaches 1, we can quit the recursive method.
रिकर्सियन में ढेर अतिप्रवाह त्रुटि
हम जानते हैं कि जब किसी भी विधि या फ़ंक्शन को कॉल किया जाता है, तो फ़ंक्शन की स्थिति स्टैक पर संग्रहीत होती है और फ़ंक्शन के वापस आने पर पुनर्प्राप्त की जाती है। स्टैक का उपयोग पुनरावर्ती विधि के लिए भी किया जाता है।
लेकिन पुनरावृत्ति के मामले में, एक समस्या तब हो सकती है जब हम आधार की स्थिति को परिभाषित नहीं करते हैं या जब आधार स्थिति किसी तरह पहुंच या निष्पादित नहीं होती है। यदि यह स्थिति होती है तो स्टैक ओवरफ्लो उत्पन्न हो सकता है।
आइए तथ्यात्मक अंकन के नीचे के उदाहरण पर विचार करें।
यहां हमने गलत आधार स्थिति दी है, 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 का मान अनिश्चित काल तक घटता रहेगा क्योंकि इसे रोकने के लिए कोई अन्य शर्त नहीं है। यह ओवरफ्लो होने तक चलेगा।
एक और मामला तब होगा जब एन के मूल्य<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
जावा में रिकर्सन उदाहरण
इस अनुभाग में, हम पुनरावर्तन का उपयोग करके निम्नलिखित उदाहरणों को लागू करेंगे।
# 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.'); } } }उत्पादन
# 3) उलटा स्ट्रिंग रिक्रिएशन जावा
एक स्ट्रिंग 'हैलो' को देखते हुए हमें इसे उल्टा करना होगा ताकि परिणामी स्ट्रिंग 'ओलेह' हो।
यह पुनरावृत्ति का उपयोग करके किया जाता है। स्ट्रिंग में अंतिम वर्ण से शुरू करके हम प्रत्येक वर्ण को पुन: मुद्रित करते हैं जब तक कि स्ट्रिंग के सभी वर्ण समाप्त नहीं हो जाते।
नीचे दिए गए प्रोग्राम में किसी दिए गए स्ट्रिंग को उलटने के लिए पुनरावर्तन का उपयोग किया गया है।
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) + '
'); } }उत्पादन
ये कुछ उदाहरण हैं पुनरावृत्ति के। इन उदाहरणों के अलावा, पुनरावर्ती तकनीकों का उपयोग करके सॉफ्टवेयर में कई अन्य समस्याओं को लागू किया जा सकता है।
पुनरावृत्ति प्रकार
पुनरावर्तन दो प्रकार का होता है, जब कॉल पुनरावर्ती विधि से किया जाता है।
वे:
(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; } जावा में पुनरावृत्ति बनाम Iteration
| प्रत्यावर्तन | यात्रा |
|---|---|
| समय जटिलता बहुत अधिक है। | समय की जटिलता अपेक्षाकृत कम तरफ है। |
| पुनर्संयोजन एक ऐसी प्रक्रिया है, जिसमें एक आधार शर्त पूरी होने तक एक विधि बार-बार खुद को कॉल करती है। | Iteration एक ऐसी प्रक्रिया है जिसके द्वारा बार-बार परिमित संख्या के लिए या किसी शर्त के पूरा होने तक कोड का एक टुकड़ा निष्पादित किया जाता है। |
| कार्यों के लिए आवेदन है। | छोरों के लिए लागू है। |
| छोटे कोड आकार के लिए अच्छी तरह से काम करता है। | बड़े कोड आकार के लिए अच्छी तरह से काम करता है। |
| अधिक मेमोरी का उपयोग करता है क्योंकि प्रत्येक पुनरावर्ती कॉल को स्टैक पर धकेल दिया जाता है | तुलनात्मक रूप से कम मेमोरी का उपयोग किया जाता है। |
| डिबग और बनाए रखने के लिए मुश्किल | डिबग और बनाए रखने में आसान |
| यदि आधार स्थिति निर्दिष्ट नहीं है या नहीं पहुंची है, तो स्टैक ओवरफ्लो में परिणाम। | असीम रूप से निष्पादित हो सकता है लेकिन अंततः किसी भी मेमोरी त्रुटियों के साथ निष्पादन को रोक देगा |
बार बार पूछे जाने वाले प्रश्न
Q # 1) जावा में रिकर्सियन कैसे काम करता है?
उत्तर: पुनरावर्तन में, पुनरावर्ती फ़ंक्शन बार-बार कॉल करता है जब तक कि एक आधार स्थिति संतुष्ट न हो। बुलाए गए फ़ंक्शन के लिए मेमोरी को कॉलिंग फ़ंक्शन के लिए मेमोरी के शीर्ष पर स्टैक पर धकेल दिया जाता है। प्रत्येक फ़ंक्शन कॉल के लिए, स्थानीय चर की एक अलग प्रतिलिपि बनाई जाती है।
क्यू # 2) Recursion का उपयोग क्यों किया जाता है?
उत्तर: पुनर्संयोजन का उपयोग उन समस्याओं को हल करने के लिए किया जाता है जिन्हें छोटे लोगों में तोड़ा जा सकता है और पूरी समस्या को एक छोटी समस्या के रूप में व्यक्त किया जा सकता है।
पुनर्संयोजन का उपयोग उन समस्याओं के लिए भी किया जाता है जो पुनरावृत्त दृष्टिकोण का उपयोग करके बहुत जटिल हैं। उन समस्याओं के अलावा जिनके लिए समय जटिलता एक मुद्दा नहीं है, पुनरावृत्ति का उपयोग करें।
क्यू # 3) पुनरावर्तन के क्या लाभ हैं?
उत्तर:
पुनरावर्तन के लाभों में शामिल हैं:
- रिकर्सन फ़ंक्शन के अनावश्यक कॉलिंग को कम करता है।
- पुनरावृत्ति, पुनरावृत्ति दृष्टिकोण की तुलना में समस्याओं को आसानी से हल करने की अनुमति देता है।
Q # 4) कौन सा बेहतर है - पुनरावृत्ति या पुनरावृत्ति?
उत्तर: आधार फ़ंक्शन तक पहुंचने तक पुनरावृत्ति बार-बार कॉल करती है। इस प्रकार प्रत्येक फ़ंक्शन कॉल के लिए एक मेमोरी ओवरहेड एक मेमोरी के रूप में स्टैक पर धकेल दिया जाता है।
दूसरी ओर गर्भाधान में बहुत अधिक मेमोरी नहीं होती है। पुनरावृत्ति निष्पादन पुनरावृत्ति दृष्टिकोण से धीमा है। पुनरावर्तन कोड के आकार को कम करता है जबकि पुनरावृत्ति दृष्टिकोण कोड को बड़ा बनाता है।
क्यू # 5) Iteration पर पुनरावर्तन के क्या लाभ हैं?
उत्तर:
- रिकर्सियन कोड को स्पष्ट और छोटा बनाता है।
- टॉवर ऑफ़ हनोई, ट्री ट्रैवर्सल्स आदि जैसी समस्याओं के लिए पुनरावृत्ति पुनरावृत्ति दृष्टिकोण से बेहतर है।
- जैसा कि प्रत्येक फ़ंक्शन कॉल में मेमोरी को स्टैक पर धकेल दिया जाता है, रिकर्सन अधिक मेमोरी का उपयोग करता है।
- पुनरावृत्ति का प्रदर्शन पुनरावृत्ति दृष्टिकोण की तुलना में धीमा है।
निष्कर्ष
प्रोग्रामिंग भाषा के बावजूद सॉफ़्टवेयर में पुनरावृत्ति एक बहुत महत्वपूर्ण अवधारणा है। रिकर्सियन का इस्तेमाल ज्यादातर डेटा संरचना की समस्याओं जैसे हनोई, ट्री ट्रैवर्सल्स, लिंक्ड लिस्ट आदि को हल करने में किया जाता है। हालांकि, यह अधिक मेमोरी लेता है, रिकर्सन कोड को सरल और स्पष्ट बनाता है।
हमने इस ट्यूटोरियल में रिकर्सन के बारे में खोजबीन की है। हमने अवधारणा की बेहतर समझ के लिए कई प्रोग्रामिंग उदाहरणों को भी लागू किया है।
=> आसान जावा प्रशिक्षण श्रृंखला के माध्यम से पढ़ें।
अनुशंसित पाठ
- सी ++ में पुनरावृत्ति
- जावा Iterator: उदाहरण के साथ जावा में Iterators का उपयोग करना सीखें
- ListIterator Interface जावा में उदाहरणों के साथ
- जावा ट्यूटोरियल फॉर बिगिनर्स: 100+ हैंड्स-ऑन जावा वीडियो ट्यूटोरियल
- कार्यक्रम के उदाहरणों के साथ लूप ट्यूटोरियल के लिए जावा
- जावा लूप - ट्यूटोरियल प्रोग्रामिंग के साथ ट्यूटोरियल
- जावा डू जबकि लूप - उदाहरणों के साथ ट्यूटोरियल
- जावा में दांतेदार सरणी - उदाहरणों के साथ ट्यूटोरियल