recursion c
क्लासिक उदाहरणों के साथ C ++ में सभी पुनरावृत्ति के बारे में जानें।
हमारे पिछले ट्यूटोरियल में, हमने C ++ में फंक्शन्स के बारे में अधिक जानकारी प्राप्त की।
कार्यों को सबयूनिट में कोड को तोड़ने और कोड को सरल और पठनीय बनाने के लिए फ़ंक्शंस का उपयोग करने के अलावा, फ़ंक्शंस वास्तविक समय की समस्याओं को हल करने, गणितीय और सांख्यिकीय गणना सहित विभिन्न अन्य अनुप्रयोगों में उपयोगी हैं।
जैसा कि हम C ++ में अधिक जटिल एप्लिकेशन विकसित करते हैं, हम कई आवश्यकताओं को पूरा करते हैं ताकि हमें C ++ की कई विशेष अवधारणाओं का उपयोग करने की आवश्यकता हो। रिकर्सियन एक ऐसी अवधारणा है।
=> संपूर्ण C ++ ट्यूटोरियल सूची के लिए यहां जाएं।
इस ट्यूटोरियल में, हम पुनरावर्तन के बारे में अधिक जानेंगे, जहाँ और क्यों इसका उपयोग कुछ क्लासिक C ++ उदाहरणों के साथ किया जाता है जो पुनरावृत्ति को लागू करते हैं।
आप क्या सीखेंगे:
- पुनरावृत्ति क्या है?
- रिकर्सियन बेस कंडीशन
- रिकर्सिव कॉल के लिए मेमोरी आवंटन
- रिकर्सियन में ढेर अतिप्रवाह
- प्रत्यक्ष बनाम अप्रत्यक्ष पुनरावर्तन
- पूंछ और गैर पूंछ पुनर्मिलन
- Iterative प्रोग्रामिंग पर पुनरावृत्ति के पेशेवरों / विपक्ष
- रिकर्सन के उदाहरण हैं
- निष्कर्ष
- अनुशंसित पाठ
पुनरावृत्ति क्या है?
पुनरावृत्ति एक प्रक्रिया है जिसमें एक फ़ंक्शन खुद को कॉल करता है। जिस फ़ंक्शन को पुनरावृत्ति या स्वयं कॉल करता है, उसे पुनरावर्ती फ़ंक्शन कहा जाता है। पुनरावृत्ति में, पुनरावर्ती कार्य खुद को बार-बार कॉल करता है और अंतिम स्थिति पूरी होने तक जारी रहता है।
नीचे दी गई छवि दर्शाती है कि रिकर्सियन कैसे काम करता है:
जैसा कि हम उपरोक्त आरेख में देखते हैं, मुख्य फ़ंक्शन एक फ़ंक्शन, फ़ंक्शनल () कहता है। फ़ंक्शन फ़ंक्शनल () बदले में खुद को इसकी परिभाषा के अंदर कहता है। इस तरह से रिकर्सन काम करता है। फ़ंक्शन को कॉल करने की यह प्रक्रिया तब तक जारी रहेगी जब तक हम एक समाप्ति स्थिति प्रदान नहीं करते हैं जो इसे समाप्त कर देगा।
आमतौर पर, हम पुनरावर्तन को लागू करते समय कोड शाखा प्रदान करते हैं जैसे कि हम एक शर्त प्रदान करते हैं जो पुनरावृत्ति को ट्रिगर करेगा और दूसरा सामान्य निष्पादन को पूरा करने के लिए।
रिकर्सियन बेस कंडीशन
जब पुनरावृत्ति होती है, तो आधार मामले या समाप्त होने वाले मामले का समाधान प्रदान किया जाता है और बड़ी समस्याओं का समाधान छोटी समस्याओं के समाधान के आधार पर बनाया जाता है।
आइए रिकर्सन के एक क्लासिक उदाहरण पर विचार करें, तथ्यपूर्ण संकेतन।
हम जानते हैं कि गणितीय रूप से संख्या n का भाज्य है:
n! = nxn-1x… .x0!
कि 0 दिया! = 1;
तो n = 3 के लिए भाज्य 3 होगा! = 3 × 2!
३! = 3x2x1!
३! = 3x2x2x0!
३! = 3x2x1x1 = 6
तो प्रोग्रामेटिक रूप से हम इस गणना को इस प्रकार व्यक्त कर सकते हैं:
int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }इस प्रकार, जैसा कि ऊपर दिखाया गया है, हमने एक फैक्टरियल की उपरोक्त गणना को पुनरावर्ती फ़ंक्शन कॉल में व्यक्त किया है। हम देखते हैं कि यदि संख्या n 1 से कम या उसके बराबर है, तो हम पुनरावर्ती कॉल के बजाय 1 वापस करते हैं। इस तथ्य के लिए आधार स्थिति / मामला कहा जाता है जो पुनरावृत्ति को रोकने की अनुमति देता है।
इसलिए, आधार स्थिति मूल रूप से यह तय करती है कि एक पुनरावर्ती फ़ंक्शन को कितनी बार कॉल करना चाहिए। इसका मतलब यह है कि हम आधार संख्या तक पहुंचने तक छोटी संख्या के संदर्भ में बड़ी संख्या के तथ्य को अच्छी तरह से गणना कर सकते हैं।
नीचे दिए गए एक नंबर के भाज्य की गणना करने के लिए एक आदर्श उदाहरण है:
#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout< आउटपुट:
वह संख्या दर्ज करें, जिसकी तथ्यात्मक गणना की जानी है: 10
10! = 3628800
उपरोक्त उदाहरण में, हम पुनरावृत्ति को लागू करते हैं। हम उस नंबर को लेते हैं जिसका फैक्टरियल स्टैण्डर्ड इनपुट से पाया जाता है और फिर इसे फैक्टोरियल फंक्शन में पास किया जाता है।
तथ्यात्मक कार्य में, हमने आधार स्थिति को (n) के रूप में दिया है<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.
रिकर्सिव कॉल के लिए मेमोरी आवंटन
हम जानते हैं कि जब कोई फ़ंक्शन कॉल किया जाता है, तो कॉलिंग फ़ंक्शन की स्थिति स्टैक पर संग्रहीत होती है और जब फ़ंक्शन कॉल पूरा हो जाता है, तो उस स्थिति को वापस बहाल कर दिया जाता है ताकि प्रोग्राम निष्पादन जारी रख सके।
जब एक पुनरावर्ती फ़ंक्शन कॉल किया जाता है, तो कॉलिंग फ़ंक्शन की स्थिति के शीर्ष पर कॉल की स्थिति या मेमोरी आवंटित की जाती है और प्रत्येक पुनरावर्ती फ़ंक्शन कॉल के लिए स्थानीय चर की एक अलग प्रतिलिपि बनाई जाती है।
जब आधार स्थिति तक पहुँच जाता है, तो फ़ंक्शन कॉलिंग फ़ंक्शन पर लौट आता है और मेमोरी डी-आबंटित होती है और प्रक्रिया जारी रहती है।
रिकर्सियन में ढेर अतिप्रवाह
जब समय की असीमित मात्रा के लिए पुनरावृत्ति जारी रहती है, तो इसका परिणाम स्टैक ओवरफ्लो हो सकता है।
जब पुनरावृत्ति इस तरह जारी रह सकती है? एक स्थिति यह है जब हम आधार की स्थिति निर्दिष्ट नहीं करते हैं। एक और स्थिति है जब एक कार्यक्रम को निष्पादित करते समय आधार की स्थिति नहीं पहुंचती है।
उदाहरण के लिए,हम उपरोक्त तथ्यात्मक कार्यक्रम को संशोधित करते हैं और इसकी आधार स्थिति को बदलते हैं।
int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }उपरोक्त कोड में, हमने आधार स्थिति को (n == 1000) में बदल दिया है। अब, यदि हम संख्या n = 10 देते हैं, तो हम यह निष्कर्ष निकाल सकते हैं कि आधार की स्थिति कभी नहीं पहुंचेगी। कुछ बिंदु पर इस तरह, स्टैक पर मेमोरी समाप्त हो जाएगी जिससे स्टैक ओवरफ्लो हो जाएगा।
इसलिए, पुनरावर्ती कार्यक्रमों को डिजाइन करते समय, हमें हमारे द्वारा प्रदान की जाने वाली आधार स्थिति के बारे में सावधान रहने की आवश्यकता है।
प्रत्यक्ष बनाम अप्रत्यक्ष पुनरावर्तन
अब तक पुनरावृत्ति में, हमने फ़ंक्शन को स्वयं कॉल करते हुए देखा है। यह प्रत्यक्ष पुनरावृत्ति है।
एक और प्रकार की पुनरावृत्ति है यानी अप्रत्यक्ष पुनरावृत्ति। इसमें एक फ़ंक्शन दूसरे फ़ंक्शन को कॉल करता है और फिर यह फ़ंक्शन कॉलिंग फ़ंक्शन को कॉल करता है। यदि f1 और f2 दो कार्य हैं। फिर f1 कॉल f2 और f2, बदले में, f1 कॉल करता है। यह एक अप्रत्यक्ष पुनरावृत्ति है।
डेटाबेस डेवलपर साक्षात्कार प्रश्न और उत्तर पीडीएफ
एल एट हमें प्रत्यक्ष पुनरावृत्ति को प्रदर्शित करने के लिए हमारे फैक्टरियल कार्यक्रम को संशोधित करता है।
#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout< आउटपुट:
वह संख्या दर्ज करें, जिसकी वास्तविकता की गणना की जानी है: 5
५! = 120
उपरोक्त उदाहरण में, हमने अप्रत्यक्ष पुनरावर्तन दिखाया है। मुख्य समारोह factorial_a कहता है। Factorial_a को factorial_b कहते हैं। बदले में factorial_b factorial_a कहते हैं। हम देखते हैं कि प्रोग्राम का आउटपुट प्रभावित नहीं होता है।
पूंछ और गैर पूंछ पुनर्मिलन
टेल्ड रिकर्सिव फ़ंक्शन एक पुनरावर्ती फ़ंक्शन है जहां फ़ंक्शन में अंतिम कॉल निष्पादित होती है।
उदाहरण के लिए, निम्न फ़ंक्शन पर विचार करें।
void display(int n){ if(n<=1) return; cout<<” ”<उपरोक्त उदाहरण में, डिस्प्ले एक पूंछी गई पुनरावर्ती फ़ंक्शन है जैसे कि यह अंतिम फ़ंक्शन कॉल है।
पूंछ वाले कार्यों को गैर-पूंछ वाले पुनरावर्ती कार्यों से बेहतर माना जाता है क्योंकि वे संकलक द्वारा अनुकूलित किए जा सकते हैं। कारण यह है कि चूंकि पूंछ वाले पुनरावर्ती कॉल फ़ंक्शन में अंतिम कथन है, इसलिए इस कॉल के बाद निष्पादित होने वाला कोई कोड नहीं है।
नतीजतन, फ़ंक्शन के लिए वर्तमान स्टैक फ़्रेम को सहेजना आवश्यक नहीं है।
Iterative प्रोग्रामिंग पर पुनरावृत्ति के पेशेवरों / विपक्ष
पुनरावर्ती कार्यक्रम कॉम्पैक्ट और स्वच्छ कोड प्रदान करते हैं। एक पुनरावर्ती कार्यक्रम कार्यक्रमों को लिखने का एक सरल तरीका है। कुछ अंतर्निहित समस्याएं हैं, जैसे कि फैक्टोरियल, फाइबोनैचि सीक्वेंस, हनोई के टावर्स, ट्री ट्रैवर्सल्स आदि, जिन्हें हल करने के लिए पुनरावृत्ति की आवश्यकता होती है।
दूसरे शब्दों में, वे पुनरावृत्ति के साथ कुशलता से हल हो जाते हैं। उन्हें स्टैक या अन्य डेटा संरचनाओं का उपयोग करके पुनरावृति प्रोग्रामिंग के साथ हल किया जा सकता है लेकिन कार्यान्वयन के लिए अधिक जटिल बनने की संभावना है।
पुनरावर्ती के साथ-साथ पुनरावृत्त प्रोग्रामिंग की समस्या-सुलझाने की शक्तियां समान हैं। हालांकि, पुनरावर्ती कार्यक्रम अधिक मेमोरी स्पेस लेते हैं क्योंकि बेस केस के मिलान होने तक सभी फ़ंक्शन कॉल को स्टैक पर संग्रहीत करने की आवश्यकता होती है।
कई फ़ंक्शन कॉल और रिटर्न मान के कारण पुनरावर्ती कार्य भी एक समय ओवरहेड होते हैं।
रिकर्सन के उदाहरण हैं
अगला, हम पुनरावर्ती प्रोग्रामिंग के कुछ उदाहरणों को लागू करेंगे।
फाइबोनैचि श्रृंखला
फाइबोनैचि श्रृंखला वह क्रम है जिसे दिया जाता है
0 1 1 2 3 5 8 13 ……
जैसा कि ऊपर दिखाया गया है, फाइबोनैचि श्रृंखला की पहली दो संख्याएँ 0 और 1. अनुक्रम में अगली संख्या पिछली दो संख्याओं का योग है।
आइए हम इस श्रृंखला को रिकर्सन का उपयोग करके कार्यान्वित करें।
#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '< आउटपुट:
फाइबोनैचि श्रृंखला के लिए तत्वों की संख्या दर्ज करें: 10
10 संख्याओं के लिए फाइबोनैचि श्रृंखला: 0 1 1 2 3 5 8 13 21 34
इस उदाहरण में, हमने फाइबोनैचि अनुक्रम उत्पन्न करने के लिए एक पुनरावर्ती कॉल का उपयोग किया है। हम देखते हैं कि पहले दो नंबरों को स्थिर किया जा रहा है और सीधे अनुक्रम में अगले नंबरों के लिए हम एक पुनरावर्ती फ़ंक्शन का उपयोग करते हैं।
विलोमपद
एक पालिंद्रा संख्या एक संख्या है जिसे जब रिवर्स दिशा में पढ़ा जाता है, तो इसे बाएं से दाएं दिशा में पढ़ा जाता है।
उदाहरण के लिए, संख्या 121, जबकि बाईं ओर से दाईं ओर और दाईं ओर से बाईं ओर रीडिंग समान है यानी 121। इसलिए 121 एक पैलिंड्रोम है।
संख्या 291, जब दाएं से बाएं यानि रिवर्स ऑर्डर में पढ़ती है, तो 192 की तरह पढ़ती है। इसलिए 291 तालबद्ध नहीं है।
#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '< आउटपुट:
Palindrome की जांच करने के लिए संख्या दर्ज करें: 6556
संख्या 6556 एक ताल है
उसी के लिए स्क्रीनशॉट नीचे दिया गया है।
उपरोक्त कार्यक्रम में, हम मानक इनपुट से इनपुट नंबर पढ़ते हैं। फिर हम इस संख्या को एक संख्या के अंकों को उलटने के लिए एक पुनरावर्ती फ़ंक्शन में पास करते हैं। यदि उलटे अंक और इनपुट संख्या समान हैं तो संख्या एक तालमेल है।
निष्कर्ष
इसके साथ, हमने पुनरावृत्ति के साथ समाप्त कर दिया है। इस ट्यूटोरियल में हमने विभिन्न उदाहरणों के साथ-साथ पुनरावर्ती प्रोग्रामिंग, पुनरावर्ती कार्य, इसके फायदे / नुकसान का अध्ययन किया है।
इन उदाहरणों के अलावा, पुनरावृत्ति का उपयोग कुछ मानक समस्याओं को हल करने में भी किया जाता है जैसे ट्रैवर्सल्स (इनवर्टर / प्रीऑर्डर / पोस्टऑर्डर), हनोई के टॉवर, बीएफएस ट्रैवर्सल, आदि।
=> स्क्रैच से C ++ जानने के लिए यहाँ जाएँ।
अनुशंसित पाठ
- मित्र कार्य C ++ में
- C ++ में बहुरूपता
- C ++ का पूर्ण अवलोकन
- हाथों पर उदाहरण के साथ पायथन मेन फंक्शन ट्यूटोरियल
- यूनिक्स पाइप्स ट्यूटोरियल: यूनिक्स प्रोग्रामिंग में पाइप्स
- पुस्तकालय कार्य C ++ में
- मुफ़्त के लिए C ++ प्रोग्रामिंग सीखने के लिए 70+ BEST C ++ ट्यूटोरियल
- QTP ट्यूटोरियल # 21 - कैसे QTP टेस्ट को मॉड्यूलर और पुन: प्रयोज्य क्रियाओं और फ़ंक्शन पुस्तकालयों का उपयोग करें
