रिकर्सन (कंप्यूटर विज्ञान): Difference between revisions

Latest revision as of 14:22, 11 August 2023

लोगो (प्रोग्रामिंग लैंग्वेज) का उपयोग करके बनाया गया ट्री और रिकर्सन पर भारी निर्भर करता है। प्रत्येक शाखा को ट्री के छोटे संस्करण के रूप में देखा जा सकता है।

कंप्यूटर विज्ञान में, रिकर्सन कम्प्यूटेशनल समस्या को हल करने की विधि है जहां कम्प्यूटेशनल समस्या के छोटे उदाहरणों के समाधान पर निर्भर करता है।^[1]^[2] रिकर्सन फ़ंक्शन (कंप्यूटर विज्ञान) का उपयोग करके ऐसे रिकर्सन को हल करता है जो स्वयं को अपने कोड के अंतर्गत कॉल करते हैं। दृष्टिकोण को अनेक प्रकार की समस्याओं पर प्रयुक्त किया जा सकता है, और रिकर्सन कंप्यूटर विज्ञान के केंद्रीय विचारों में से है।^[3]

रिकर्सन की शक्ति स्पष्ट रूप से एक सीमित कथन द्वारा वस्तुओं के अनंत सेट को परिभाषित करने की संभावना में निहित है। उसी तरह, एक सीमित रिकर्सन प्रोग्राम द्वारा अनंत संख्या में संगणनाओं का वर्णन किया जा सकता है, तथापि इस प्रोग्राम में कोई स्पष्ट रिकर्सन न हो।
— निक्लॉस विर्थ, एल्गोरिदम + डेटा संरचनाएं = प्रोग्राम, 1976^[4]

अधिकांश कंप्यूटर प्रोग्रामिंग लैंग्वेज किसी फ़ंक्शन को अपने स्वयं के कोड के अन्दर से कॉल करने की अनुमति देकर रिकर्सन का समर्थन करती हैं। कुछ फ़ंक्शन प्रोग्रामिंग लैंग्वेज (उदाहरण के लिए, क्लोजर) ^[5] किसी भी लूपिंग संरचना को परिभाषित न करें किन्तु कोड को अधिकांशतः कॉल करने के लिए पूरी तरह रिकर्सन पर विश्वास करें। कम्प्यूटेबिलिटी सिद्धांत में यह सिद्ध हो गया है कि यह रिकर्सिव-ओनली लैंग्वेज ट्यूरिंग पूर्णता हैं; इसका कारण यह है कि वह जैसे कि नियंत्रण संरचनाओं पर आधारित इम्प्रेटिव लैंग्वेज while तथा for. उतने ही पॉवरशाली हैं (उनका उपयोग समान समस्याओं को हल करने के लिए किया जा सकता है)

अधिकांशतः किसी फ़ंक्शन को अपने अन्दर से कॉल करने से कॉल स्टैक का आकार सभी सम्मिलित कॉलों के इनपुट आकारों के योग के सामान हो सकता है। यह इस प्रकार है कि, रिकर्सन द्वारा सरलता से हल की जा सकने वाली समस्याओं के लिए, रिकर्सन सामान्यतः कम एल्गोरिथम दक्षता है, और, बड़ी समस्याओं के लिए, टेल कॉल ऑप्टिमाइज़ेशन जैसे अनुकूलन तकनीकों का उपयोग करना मौलिक है।

रिकर्सन फ़ंक्शन और एल्गोरिदम

सामान्य एल्गोरिथम डिजाइन रणनीति समस्या को उसी प्रकार की उप-समस्याओं में विभाजित करना है, जो मूल के समान हैं, उन उप-समस्याओं को हल करें, और परिणामों को संयोजित करें। इसे अधिकांशतः डिवाइड एंड कॉन्कर के रूप में जाना जाता है; जब लुकअप टेबल के साथ जोड़ा जाता है जो पहले हल की गई उप-समस्याओं के परिणामों को संग्रहीत करता है (उन्हें अधिकांशतः हल करने और अतिरिक्त गणना समय व्यय करने से बचने के लिए), इसे डायनामिक प्रोग्रामिंग या संस्मरण के रूप में संदर्भित किया जा सकता है.

बेस केस

रिकर्सन फ़ंक्शन परिभाषा में या अधिक आधार स्थिति होते हैं, जिसका अर्थ है इनपुट जिसके लिए फ़ंक्शन परिणाम उत्पन्न करता है इस प्रकार सामान्य (गणित) ly (रिकर्सन के बिना), और या अधिक रिकर्सन स्थिति, जिसका अर्थ है इनपुट जिसके लिए प्रोग्राम की रिकर्सन होती है (स्वयं कॉल करता है)। उदाहरण के लिए, फ़ैक्टोरियल फ़ंक्शन को समीकरणों $0! = 1$ द्वारा रिकर्सन रूप से परिभाषित किया जा सकता है और, सभी के लिए $n > 0$ , $n! = n (n - 1)!$ . कोई भी समीकरण अपने आप में पूर्ण परिभाषा नहीं बनाता है; पहला बेस केस है, और दूसरा रिकर्सिव केस है। क्योंकि बेस केस रिकर्सन की श्रृंखला को तोड़ता है, इसे कभी-कभी टर्मिनेटिंग केस भी कहा जाता है।

रिकर्सन स्थितियों की नौकरी को काम्प्लेक्स इनपुट को सरल में विभाजित करने के रूप में देखा जा सकता है। ठीक से डिज़ाइन किए गए रिकर्सन फ़ंक्शन में, प्रत्येक रिकर्सिव कॉल के साथ, इनपुट समस्या को इस तरह से सरल किया जाना चाहिए कि अंततः बेस केस तक पहुंचना चाहिए। (ऐसे कार्य जो सामान्य परिस्थितियों में समाप्त करने के लिए अभिप्रेत नहीं हैं—उदाहरण के लिए, कुछ डेमॉन (कंप्यूटर सॉफ़्टवेयर)—इसका अपवाद हैं।) बेस केस लिखने की उपेक्षा करना, या इसके लिए गलत विधि से परीक्षण करना, इन्फिनाईट लूप का कारण बन सकता है।

कुछ फ़ंक्शन के लिए (जैसे कि $e = 1/0! + 1/1! + 1/2! + 1/3! + ...$ वह जो श्रृंखला (गणित) की गणना करता है ) इनपुट डेटा द्वारा निहित कोई स्पष्ट आधार स्थिति नहीं है; इनके लिए कोई मापदंड जोड़ सकता है (जैसे कि हमारे श्रृंखला उदाहरण में जोड़े जाने वाले शब्दों की संख्या) 'स्टॉपिंग मानदंड' प्रदान करने के लिए जो आधार स्थिति स्थापित करता है। इस तरह के उदाहरण को अधिक स्वाभाविक रूप से कोरकर्शन द्वारा माना जाता है,^[how?] जहां आउटपुट में उत्तरोत्तर पद आंशिक योग हैं; इसे nth पद (nth आंशिक योग) की गणना करने के लिए इंडेक्सिंग मापदंड का उपयोग करके रिकर्सन में परिवर्तित किया जा सकता है।

रिकर्सन डेटा प्रकार

अनेक कंप्यूटर प्रोग्राम को अनैतिक रूप से बड़ी मात्रा में डेटा को संसाधित या उत्पन्न करना चाहिए। रिकर्सन डेटा का प्रतिनिधित्व करने के लिए तकनीक है जिसका स्पष्ट आकार प्रोग्रामर के लिए अज्ञात है: प्रोग्रामर इस डेटा को स्व-संदर्भ या स्व-संदर्भ परिभाषा के साथ निर्दिष्ट कर सकता है। स्व-संदर्भित परिभाषाएँ दो प्रकार की होती हैं: जो निम्न इंडुक्टिवेली और सह-संदर्भ परिभाषाएँ है।

इंडुक्टिवेली परिभाषित डेटा

इंडुक्टिवेली परिभाषित रिकर्सन डेटा परिभाषा वह है जो निर्दिष्ट करती है कि डेटा के उदाहरणों का निर्माण कैसे किया जाए। उदाहरण के लिए, लिंक की गई सूचियों को इंडुक्टिवेली परिभाषित किया जा सकता है (यहां, हास्केल (प्रोग्रामिंग लैंग्वेज) सिंटैक्स का उपयोग करके):

data ListOfStrings = EmptyList | Cons String ListOfStrings

उपरोक्त कोड या तो रिक्त होने वाली स्ट्रिंग्स की लिस्ट्स निर्दिष्ट करता है, या संरचना जिसमें स्ट्रिंग और स्ट्रिंग्स की लिस्ट्स होती है। परिभाषा में स्व-संदर्भ किसी भी (सीमित) संख्या में स्ट्रिंग की लिस्ट्स के निर्माण की अनुमति देता है। इंडुक्टिवेली परिभाषा का अन्य उदाहरण प्राकृतिक संख्याएँ (या धनात्मक पूर्णांक) हैं:

A natural number is either 1 or n+1, where n is a natural number.

इसी प्रकार प्रोग्रामिंग लैंग्वेज में अभिव्यक्तियों और कथनों की संरचना को मॉडल करने के लिए अधिकांशतः रिकर्सन परिभाषाओं का उपयोग किया जाता है। लैंग्वेज डिज़ाइनर अधिकांशतः व्याकरण को बैकस-नौर रूप जैसे वाक्य-विन्यास में व्यक्त करते हैं; गुणा और जोड़ के साथ अंकगणितीय अभिव्यक्तियों की सरल लैंग्वेज के लिए यहां ऐसा व्याकरण है:

 <expr> ::= <number>
          | (<expr> * <expr>)
          | (<expr> + <expr>)

यह कहता है कि अभिव्यक्ति या तो संख्या है, दो अभिव्यक्तियों का उत्पाद है, या दो अभिव्यक्तियों का योग है। दूसरी और तीसरी पंक्तियों में अभिव्यक्तियों को रिकर्सन रूप से संदर्भित करके, व्याकरण ही अभिव्यक्ति में से अधिक उत्पाद या योग संचालन के साथ (5 * ((3 * 6) + 8)) जैसे अनैतिक रूप से काम्प्लेक्स अंकगणितीय अभिव्यक्तियों की अनुमति देता है।

संयोगात्मक रूप से परिभाषित डेटा और कोरकर्शन

संयोगात्मक डेटा परिभाषा वह है जो उन परिचालनों को निर्दिष्ट करती है जो डेटा के टुकड़े पर किए जा सकते हैं; सामान्यतः, परिमित आकार की डेटा संरचनाओं के लिए स्व-संदर्भात्मक संयोगात्मक परिभाषाओं का उपयोग किया जाता है।

अनौपचारिक रूप से दी गई स्ट्रिंग की इन्फिनाईट धाराओं की सहवर्ती परिभाषा इस तरह दिख सकती है:

A stream of strings is an object s such that:
 head(s) is a string, and
 tail(s) is a stream of strings.

यह स्ट्रिंग्स की सूचियों की आगमनात्मक परिभाषा के समान है, अंतर यह है कि यह परिभाषा निर्दिष्ट करती है कि डेटा संरचना की कंटेंट तक कैसे पहुंचें - अर्थात्, एक्सेसर फ़ंक्शन हेड और टेल के माध्यम से - और वह कंटेंट क्या हो सकती हैं, जबकि आगमनात्मक परिभाषा निर्दिष्ट करता है कि संरचना कैसे बनाई जाए और इसे किस चीज़ से बनाया जा सकता है।

कोरकर्सियन सहसंयोजन से संबंधित है, और इसका उपयोग (संभवतः) अनंत वस्तुओं के विशेष उदाहरणों की गणना करने के लिए किया जा सकता है। प्रोग्रामिंग तकनीक के रूप में, इसका उपयोग अधिकांशतः लेजी प्रोग्रामिंग लैंग्वेज के संदर्भ में किया जाता है, और जब किसी प्रोग्राम के आउटपुट का वांछित आकार या परिशुद्धता अज्ञात हो तो रिकर्सन के लिए इसे प्राथमिकता दी जा सकती है। ऐसे स्थितियों में प्रोग्राम को असीम रूप से बड़े (या असीम रूप से स्पष्ट) परिणाम के लिए परिभाषा और उस परिणाम का सीमित भाग लेने के लिए तंत्र दोनों की आवश्यकता होती है। पहले n अभाज्य संख्याओं की गणना करने की समस्या ऐसी समस्या है जिसे कोरकर्सिव प्रोग्राम (उदाहरण के लिए यहां) के साथ हल किया जा सकता है।

रिकर्सन के प्रकार

एकल रिकर्सन और एकाधिक रिकर्सन

जिस रिकर्सन में केवल ही स्व-संदर्भ होता है उसे एकल रिकर्सन के रूप में जाना जाता है जबकि जिस रिकर्सन में एकाधिक स्व-संदर्भ होते हैं उसे एकाधिक रिकर्सन के रूप में जाना जाता है। एकल रिकर्सन के मानक उदाहरणों में लिस्ट्स ट्रैवर्सल सम्मिलित है जैसे कि रैखिक खोज या फैक्टोरियल फ़ंक्शन की गणना करना, जबकि मल्टीपल रिकर्सन के मानक उदाहरणों में ट्री ट्रैवर्सल सम्मिलित है जैसे कि डेप्थ-पहली खोज है।

एकल रिकर्सन अधिकांशतः एकाधिक रिकर्सन की तुलना में अधिक कुशल होता है, और सामान्यतः इसे रिकर्सन गणना द्वारा प्रतिस्थापित किया जा सकता है, जो रैखिक समय में चलता है और निरंतर स्थान की आवश्यकता होती है। इसके विपरीत, एकाधिक रिकर्सन के लिए घातीय समय और स्थान की आवश्यकता हो सकती है, और यह अधिक मौलिक रूप से रिकर्सन है, जिसे स्पष्ट स्टैक के बिना रिकर्सन द्वारा प्रतिस्थापित नहीं किया जा सकता है।

एकाधिक रिकर्सन को कभी-कभी एकल रिकर्सन में परिवर्तित किया जा सकता है (और, यदि वांछित हो, तो रिकर्सन में)। उदाहरण के लिए, फाइबोनैचि अनुक्रम की गणना करते समय सहजता से अनेक रिकर्सन की आवश्यकता होती है, क्योंकि प्रत्येक मान के लिए दो पिछले मानों की आवश्यकता होती है, इसे मापदंडों के रूप में दो क्रमिक मानों को पारित करके एकल रिकर्सन द्वारा गणना की जा सकती है। इसे अधिक स्वाभाविक रूप से कोरकर्सियन के रूप में तैयार किया गया है, प्रारंभिक मानों से निर्माण करते हुए, प्रत्येक फेज में दो क्रमिक मानों को ट्रैक करते हुए - कोरकर्सियन देखें: उदाहरण अधिक परिष्कृत उदाहरण में थ्रेडेड बाइनरी ट्री का उपयोग सम्मिलित है, जो एकाधिक रिकर्सन के अतिरिक्त पुनरावृत्त ट्री ट्रैवर्सल की अनुमति देता है।

अप्रत्यक्ष रिकर्सन

रिकर्सन के अधिकांश मूलभूत उदाहरण, और यहां प्रस्तुत अधिकांश उदाहरण, प्रत्यक्ष रिकर्सन प्रदर्शित करते हैं, जिसमें फ़ंक्शन स्वयं को कॉल करता है। अप्रत्यक्ष रिकर्सन तब होता है जब किसी फ़ंक्शन को स्वयं नहीं किन्तु किसी अन्य फ़ंक्शन द्वारा कॉल किया जाता है जिसे वह कॉल करता है (या तो प्रत्यक्ष या अप्रत्यक्ष रूप से)। उदाहरण के लिए, यदि f, f को कॉल करता है, तो यह प्रत्यक्ष रिकर्सन है, किन्तु यदि f, g को कॉल करता है, जो f को कॉल करता है, तो यह f का अप्रत्यक्ष रिकर्सन है। तीन या अधिक कार्यों की शृंखलाएँ संभव हैं; उदाहरण के लिए, फ़ंक्शन 1 फ़ंक्शन 2 को कॉल करता है, फ़ंक्शन 2 फ़ंक्शन 3 को कॉल करता है, और फ़ंक्शन 3 फ़ंक्शन 1 को फिर से कॉल करता है।

अप्रत्यक्ष रिकर्सन को पारस्परिक रिकर्सन भी कहा जाता है, जो अधिक सममित शब्द है, चूँकि यह केवल बल का अंतर है, कोई भिन्न धारणा नहीं है। अर्थात्, यदि f, g को कॉल करता है और फिर g, f को कॉल करता है, जो परिवर्तन में g को फिर से कॉल करता है, एकल f के दृष्टिकोण से, f अप्रत्यक्ष रूप से रिकर्सन है, जबकि एकल g के दृष्टिकोण से, यह अप्रत्यक्ष रूप से रिकर्सन है, जबकि दोनों के दृष्टिकोण से, f और g परस्पर दूसरे पर आवर्ती हैं। इसी प्रकार तीन या अधिक फ़ंक्शंस का सेट जो दूसरे को कॉल करता है उसे पारस्परिक रूप से रिकर्सन फ़ंक्शंस का सेट कहा जा सकता है।

एनोनिमस रिकर्सन

रिकर्सन सामान्यतः किसी फ़ंक्शन को नाम से स्पष्ट रूप से कॉल करके किया जाता है। चूँकि, वर्तमान संदर्भ के आधार पर किसी फ़ंक्शन को अंतर्निहित रूप से कॉल करके भी रिकर्सन किया जा सकता है, जो विशेष रूप से अज्ञात फ़ंक्शंस के लिए उपयोगी है, और इसे एनोनिमस रिकर्सन के रूप में जाना जाता है।

संरचनात्मक बनाम जनरेटिव रिकर्सन

कुछ लेखक रिकर्सन को "संरचनात्मक" या "उत्पादक" के रूप में वर्गीकृत करते हैं। यह अंतर इस बात से संबंधित है कि रिकर्सन प्रक्रिया को वह डेटा कहां से मिलता है जिस पर वह कार्य करती है, और यह उस डेटा को कैसे संसाधित करती है:

फ़ंक्शन जो संरचित डेटा का उपभोग करते हैं सामान्यतः अपने तर्कों को उनके तत्काल संरचनात्मक कॉम्पोनेन्ट में विघटित करते हैं और फिर उन कॉम्पोनेन्ट को संसाधित करते हैं। यदि तत्काल कॉम्पोनेन्ट में से इनपुट के समान डेटा के वर्ग से संबंधित है, तो फ़ंक्शन रिकर्सन है। इसी कारण से, हम इन कार्यों को (संरचनात्मक रूप से) रिकर्सन कार्यों के रूप में संदर्भित करते हैं।

— फेलिसेन, फाइंडलर, फ़्लैट, और कृष्णाउर्थी, हाउ टू डिज़ाइन प्रोग्राम्स, 2001 [6]

इस प्रकार, संरचनात्मक रूप से रिकर्सन फ़ंक्शन की परिभाषित विशेषता यह है कि प्रत्येक रिकर्सिव कॉल का तर्क मूल इनपुट के क्षेत्र की कंटेंट है। संरचनात्मक रिकर्सन में लगभग सभी ट्री ट्रैवर्सल सम्मिलित हैं, जिसमें एक्सएमएल प्रसंस्करण, बाइनरी ट्री निर्माण और खोज आदि सम्मिलित हैं। प्राकृतिक संख्याओं की बीजगणितीय संरचना पर विचार करके (अर्थात, प्राकृतिक संख्या या तो शून्य है या प्राकृतिक संख्या का उत्तराधिकारी है), ऐसे कार्य तथ्यात्मक के रूप में संरचनात्मक रिकर्सन के रूप में भी माना जा सकता है।

जनरेटिव रिकर्सन विकल्प है:

अनेक प्रसिद्ध रिकर्सन एल्गोरिदम दिए गए डेटा से डेटा का बिल्कुल नया टुकड़ा उत्पन्न करते हैं और उस पर रिकर्सन करते हैं। HtDP (प्रोग्राम कैसे डिज़ाइन करें) इस प्रकार को जेनरेटिव रिकर्सन के रूप में संदर्भित करता है। जेनरेटिव रिकर्सन के उदाहरणों में जीसीडी, क्विक्सॉर्ट, बाइनरी सर्च, मर्जसॉर्ट न्यूटन की विधि फ्रैक्टल और अनुकूली एकीकरण सम्मिलित हैं।

— मैथियास फेलिसेन, एडवांस्ड फंक्शनल प्रोग्रामिंग, 2002 ^[6]

किसी फ़ंक्शन की समाप्ति को सिद्ध करने में यह अंतर महत्वपूर्ण है।

इन्फिनाईट (आगमनात्मक रूप से परिभाषित) डेटा संरचनाओं पर सभी संरचनात्मक रूप से रिकर्सन कार्यों को संरचनात्मक प्रेरण के माध्यम से सरलता से समाप्त होते हुए दिखाया जा सकता है: सहज रूप से, प्रत्येक रिकर्सिव कॉल को बेस केस तक पहुंचने तक इनपुट डेटा का छोटा टुकड़ा प्राप्त होता है।

इसके विपरीत, जेनरेटिव रिकर्सिव फ़ंक्शंस आवश्यक रूप से अपने रिकर्सिव कॉल में छोटे इनपुट को फीड नहीं करते हैं, इसलिए उनकी समाप्ति का प्रमाण उतना सरल नहीं है, और अनंत लूप से बचने के लिए अधिक देखभाल की आवश्यकता होती है। इन जेनरेटिव रिकर्सिव फ़ंक्शंस को अधिकांशतः कोरकर्सिव फ़ंक्शंस के रूप में व्याख्या किया जा सकता है - प्रत्येक फेज नया डेटा उत्पन्न करता है, जैसे कि न्यूटन की विधि में क्रमिक सन्निकटन - और इस कोरकर्सिव को समाप्त करने के लिए आवश्यक है कि डेटा अंततः कुछ नियमो को पूरा करे, जिसकी गारंटी आवश्यक नहीं है।
लूप वेरिएंट के संदर्भ में, संरचनात्मक रिकर्सन तब होता है जब स्पष्ट लूप वेरिएंट होता है, अर्थात् आकार या काम्प्लेक्स, जो इन्फिनाईट से प्रारंभ होती है और प्रत्येक रिकर्सिव फेज पर घट जाती है।
इसके विपरीत, जेनरेटिव रिकर्सन तब होता है जब ऐसा कोई स्पष्ट लूप वैरिएंट नहीं होता है, और समाप्ति फ़ंक्शन पर निर्भर करती है, जैसे कि "अनुमान की त्रुटि" जो आवश्यक रूप से शून्य तक कम नहीं होती है, और इस प्रकार आगे के विश्लेषण के बिना समाप्ति की गारंटी नहीं होती है।

कार्यान्वयन संबंधी उद्देश्य

वास्तविक कार्यान्वयन में, शुद्ध रिकर्सन फ़ंक्शन (बेस केस के लिए एकल जांच, अन्यथा रिकर्सन फेज ) के अतिरिक्त, स्पष्टता या दक्षता के प्रयोजनों के लिए अनेक संशोधन किए जा सकते हैं। इसमे सम्मिलित है:

रैपर फ़ंक्शन (शीर्ष पर)
बेस केस को शॉर्ट-सर्किट करना, उर्फ "आर्म्स-लेंथ रिकर्सन" (नीचे)
हाइब्रिड एल्गोरिदम (नीचे) - डेटा अधिक छोटा होने पर भिन्न एल्गोरिदम पर स्विच करना

सुंदरता के आधार पर, रैपर कार्यों को सामान्यतः अनुमोदित किया जाता है, जबकि बेस केस में शॉर्ट-सर्किटिंग को विशेष रूप से शिक्षा विश्व में नापसंद किया जाता है। हाइब्रिड एल्गोरिदम का उपयोग अधिकांशतः दक्षता के लिए किया जाता है, छोटे स्थितियों में रिकर्सन के ओवरहेड को कम करने के लिए, और आर्म-लेंथ रिकर्सन इसका विशेष स्थिति है।

रैपर फ़ंक्शन

रैपर फ़ंक्शन ऐसा फ़ंक्शन है जिसे सीधे कॉल किया जाता है किन्तु वह स्वयं को पुनरावृत्त नहीं करता है, इसके अतिरिक्त भिन्न सहायक फ़ंक्शन को कॉल करता है जो वास्तव में रिकर्सन करता है।

रैपर फ़ंक्शंस का उपयोग मापदंडों को मान्य करने के लिए किया जा सकता है (जिससे रिकर्सन फ़ंक्शन इन्हें छोड़ सके), आरंभीकरण करें (मेमोरी आवंटित करें, वैरीएबल प्रारंभ करें), विशेष रूप से सहायक वैरीएबल जैसे "रिकर्सन का स्तर" या मेमोइज़ेशन के लिए आंशिक गणना, और अपवादों और त्रुटियों को संभालें . नेस्टेड फ़ंक्शंस का समर्थन करने वाली लैंग्वेज में, सहायक फ़ंक्शन को रैपर फ़ंक्शन के अंदर नेस्ट किया जा सकता है और साझा सीमा का उपयोग किया जा सकता है। नेस्टेड फ़ंक्शंस की अनुपस्थिति में, सहायक फ़ंक्शंस भिन्न फ़ंक्शन होते हैं, यदि संभव हो तो निजी (क्योंकि उन्हें सीधे नहीं कहा जाता है), और जानकारी पास-बाय-रेफरेंस का उपयोग करके रैपर फ़ंक्शन के साथ साझा की जाती है।

बेस केस में शॉर्ट-सर्किट करना

                                                                                                                                               
{{anchor|Arm's-length recursion}}                                                                                     
{| class="wikitable floatright collapsible"                                                                                
|+ {{nowrap|Factorial: ordinary}} vs. short-circuit                                                                         
|-
! Ordinary recursion                                                                                                   
! Short-circuit recursion                                                                                                         
|-
| VALIGN=TOP | <syntaxhighlight lang=C>                                                                                                                                                             
int fac1(int n) {   
   if (n <= 0)
      return 1;
   else
      return fac1(n-1)*n;
}

static int fac2(int n) {
   // assert(n >= 2);
   if (n == 2)
      return 2;
   else
      return fac2(n-1)*n;
}
int fac2wrapper(int n) {
   if (n <= 1)
      return 1;
   else
      return fac2(n);
}

बेस केस को शॉर्ट-सर्किट करना, जिसे आर्म्स-लेंथ रिकर्सन के रूप में भी जाना जाता है, जिसमें रिकर्सिव कॉल करने से पहले बेस केस की जाँच करना सम्मिलित है - अर्थात, कॉल करने के अतिरिक्त यह जाँचना कि क्या अगला कॉल बेस केस होगा और फिर जाँच करना आधार स्थिति के लिए। शॉर्ट-सर्किटिंग विशेष रूप से दक्षता कारणों से किया जाता है, फ़ंक्शन कॉल के ओवरहेड से बचने के लिए जो तुरंत लौटता है। ध्यान दें कि चूंकि बेस केस पहले ही चेक किया जा चुका है (रिकर्सन फेज से तुरंत पहले), इसे भिन्न से चेक करने की आवश्यकता नहीं है, किन्तु किसी को स्थिति के लिए रैपर फ़ंक्शन का उपयोग करने की आवश्यकता होती है जब समग्र रिकर्सन बेस केस से प्रारंभ होता है अपने आप उदाहरण के लिए, फैक्टोरियल फ़ंक्शन में, बेस केस ठीक से 0 है! जबकि तुरंत 1 के लिए 1 लौटा रहा है! शॉर्ट सर्किट है, और 0 मिस हो सकता है; इसे रैपर फ़ंक्शन द्वारा कम किया जा सकता है। बॉक्स सी (प्रोग्रामिंग लैंग्वेज) कोड को शार्टकट फैक्टोरियल केस 0 और 1 के लिए दिखाता है।

शॉर्ट-सर्किटिंग मुख्य रूप से चिंता का विषय है जब अनेक आधार स्थिति सामने आते हैं, जैसे कि ट्री में नल पॉइंटर्स, जो फ़ंक्शन कॉल की संख्या में रैखिक हो सकते हैं, इसलिए महत्वपूर्ण बचत $O (n)$ एल्गोरिदम है; इसे डेप्थ से पहली खोज के लिए नीचे चित्रित किया गया है। ट्री पर शॉर्ट सर्किट आधार स्थिति के रूप में रिक्त नोड पर विचार करने के अतिरिक्त आधार स्थिति के रूप में पत्ते (कोई चिल्ड्रेन के साथ गैर-रिक्त नोड) पर विचार करने से मेल खाता है। यदि केवल आधार स्थिति है, जैसे कि फैक्टोरियल की गणना में, शॉर्ट सर्किटिंग केवल $O (1)$ प्रदान करता है

संकल्पनात्मक रूप से, शॉर्ट-सर्किटिंग को या तो समान आधार केस और रिकर्सन फेज माना जा सकता है, केवल रिकर्सन से पहले बेस केस की जांच करना, या इसे भिन्न बेस केस (मानक बेस केस से कदम हटा दिया गया) और a माना जा सकता है। अधिक काम्प्लेक्स रिकर्सन फेज , अर्थात् ट्री में आधार स्थितियों के रूप में नल नोड्स के अतिरिक्त पत्ती नोड्स पर विचार करने के रूप में मान्य फिर रिकर्सन की जाँच करें। क्योंकि शॉर्ट-सर्किटिंग में अधिक काम्प्लेक्स प्रवाह होता है, बेस केस के स्पष्ट पृथक्करण और मानक रिकर्सन में रिकर्सन फेज की तुलना में, इसे अधिकांशतः व्यर्थ शैली माना जाता है, विशेष रूप से शिक्षाविदों में उपयोग किया जाता है।^[7]

डेप्थ-पहली खोज

बाइनरी ट्री की डेप्थ-फर्स्ट सर्च (डीएफएस ) में शॉर्ट-सर्किटिंग का मूलभूत उदाहरण दिया गया है; मानक रिकर्सन विचार के लिए बाइनरी ट्री अनुभाग देखें।

डीएफएस के लिए मानक रिकर्सन एल्गोरिथ्म है:

बेस केस: यदि वर्तमान नोड शून्य है, तो लाई वापसी करें
रिकर्सन कदम: अन्यथा, वर्तमान नोड के मूल्य की जांच करें, यदि मेल खाता है तो सही लौटें, अन्यथा चिल्ड्रेन पर रिकर्सन करें

शॉर्ट सर्किटिंग में, इसके अतिरिक्त यह है:

वर्तमान नोड का मूल्य जांचें, यदि मेल खाता है तो सही लौटें,
अन्यथा, चिल्ड्रेन पर, यदि शून्य नहीं है, तो रिकर्सन करें।

मानक फेज के संदर्भ में, यह रिकर्सन फेज से पहले बेस केस चेक को स्थानांतरित करता है। वैकल्पिक रूप से, इन्हें क्रमशः बेस केस और रिकर्सिव स्टेप का भिन्न रूप माना जा सकता है। ध्यान दें कि ट्री के रिक्त होने पर स्थिति को संभालने के लिए इसे रैपर फ़ंक्शन की आवश्यकता होती है (रूट नोड शून्य है)।

ऊँचाई h के परफेक्ट बाइनरी ट्री के स्थिति में, 2^h+1−1 नोड हैं और 2^h+1 चिल्ड्रेन के रूप में अशक्त संकेत (2 में से प्रत्येक के लिए 2^h छोड़ देता है), इसलिए शॉर्ट-सर्किटिंग सबसे व्यर्थ स्थिति में फ़ंक्शन कॉल की संख्या को आधा कर देता है।

C में, मानक रिकर्सन एल्गोरिथ्म को इस प्रकार प्रयुक्त किया जा सकता है:

bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // base case
    else if (tree_node->data == i)
        return true;
    else
        return tree_contains(tree_node->left, i) ||
               tree_contains(tree_node->right, i);
}

शॉर्ट-सर्किट एल्गोरिदम को इस प्रकार कार्यान्वित किया जा सकता है:

// Wrapper function to handle empty tree
bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // empty tree
    else
        return tree_contains_do(tree_node, i);  // call auxiliary function
}

// Assumes tree_node != NULL
bool tree_contains_do(struct node *tree_node, int i) {
    if (tree_node->data == i)
        return true;  // found
    else  // recurse
        return (tree_node->left  && tree_contains_do(tree_node->left,  i)) ||
               (tree_node->right && tree_contains_do(tree_node->right, i));
}

बूलियन && (AND) ऑपरेटरों के शॉर्ट सर्किट मूल्यांकन के उपयोग पर ध्यान दें, जिससे रिकर्सिव कॉल केवल तभी किया जा सके जब नोड वैध (गैर-शून्य) होता है। ध्यान दें कि जबकि AND में पहला शब्द नोड के लिए सूचक है, दूसरा शब्द बूलियन है, इसलिए समग्र अभिव्यक्ति बूलियन का मूल्यांकन करती है। रिकर्सिव शॉर्ट सर्किटिंग में यह सामान्य मुहावरा है। यह बूलियन || के शॉर्ट-सर्किट मूल्यांकन के अतिरिक्त है (या) ऑपरेटर, बाएं चाइल्ड के विफल होने पर केवल सही चाइल्ड की जांच करने के लिए। वास्तव में, इन कार्यों के संपूर्ण नियंत्रण प्रवाह को रिटर्न स्टेटमेंट में एकल बूलियन अभिव्यक्ति के साथ बदला जा सकता है, किन्तु सुगमता दक्षता के लिए कोई लाभ नहीं उठाती है।

हाइब्रिड एल्गोरिथम

अधिकांशतः फ़ंक्शन कॉल और रिटर्न के ओवरहेड के कारण रिकर्सन एल्गोरिदम अधिकांशतः छोटे डेटा के लिए अक्षम होते हैं। इस कारण से रिकर्सन एल्गोरिदम के कुशल कार्यान्वयन अधिकांशतः रिकर्सन एल्गोरिदम से प्रारंभ होते हैं, किन्तु जब इनपुट छोटा हो जाता है तो भिन्न एल्गोरिदम पर स्विच करें। महत्वपूर्ण उदाहरण मर्ज़ सॉर्ट है, जिसे अधिकांशतः गैर-रिकर्सन सम्मिलन सॉर्ट पर स्विच करके प्रयुक्त किया जाता है, जब डेटा पर्याप्त रूप से छोटा होता है, जैसा कि टाइल टाइल मर्ज सॉर्ट में होता है। हाइब्रिड रिकर्सन एल्गोरिदम को अधिकांशतः और अधिक परिष्कृत किया जा सकता है, जैसे कि टिमसोर्ट में, हाइब्रिड मर्ज सॉर्ट/इंसर्शन सॉर्ट से प्राप्त किया गया था।

रिकर्सन बनाम पुनरावृति

रिकर्सन और रिकर्सन समान रूप से एक्स्प्रेसिव हैं: रिकर्सन को स्पष्ट कॉल स्टैक के साथ रिकर्सन द्वारा प्रतिस्थापित किया जा सकता है, जबकि रिकर्सन को टेल कॉल से बदला जा सकता है। कौन सा दृष्टिकोण उत्तम है विचाराधीन समस्या और प्रयुक्त लैंग्वेज पर निर्भर करता है। इम्प्रेटिव प्रोग्रामिंग में, रिकर्सन को प्राथमिकता दी जाती है, विशेष रूप से सरल रिकर्सन के लिए, क्योंकि यह फ़ंक्शन कॉल और कॉल स्टैक मैनेजमेंट के ओवरहेड से बचा जाता है, किन्तु रिकर्सन सामान्यतः एकाधिक रिकर्सन के लिए उपयोग किया जाता है। इसके विपरीत, फ़ंक्शन प्रोग्रामिंग में रिकर्सन को प्राथमिकता दी जाती है, टेल रिकर्सन अनुकूलन के साथ थोड़ा ओवरहेड होता है। हो सकता है कि पुनरावृति का उपयोग करके एल्गोरिथम को प्रयुक्त करना सरलता से प्राप्त न किया जा सकता है।

x_n से x_n = f(n, x_n-1) द्वारा परिभाषित x_base की गणना करने के लिए टेम्प्लेट की तुलना करें:

function recursive(n)
 if n == base
 return x_base
 else
 return f(n, recursive(n-1))

function iterative(n)
 x = x_base
 for i = base+1 to n
 x = f(i, x)
 return x

इम्प्रेटिव लैंग्वेज के लिए ओवरहेड फ़ंक्शन को परिभाषित करना है, और फ़ंक्शन लैंग्वेज के लिए ओवरहेड संचायक वैरीएबल x को परिभाषित करना है।

उदाहरण के लिए, तर्कों को पारित करने और रिकर्सन द्वारा मानों को वापस करने के अतिरिक्त, लूप इंडेक्स वेरिएबल और संचायक वैरीएबल को असाइन करके सी (प्रोग्रामिंग लैंग्वेज) में फैक्टोरियल फ़ंक्शन को पुनरावृत्त रूप से कार्यान्वित किया जा सकता है:

unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}

एक्स्प्रेसिव पॉवर

आज उपयोग की जाने वाली अधिकांश प्रोग्रामिंग भाषाएँ रिकर्सन कार्यों और प्रक्रियाओं के प्रत्यक्ष विनिर्देशन की अनुमति देती हैं। जब इस तरह के फ़ंक्शन को कॉल किया जाता है, जिससे प्रोग्राम का रनटाइम वातावरण फ़ंक्शन के विभिन्न इंस्टेंस (कंप्यूटर विज्ञान) का ट्रैक रखता है (अधिकांशतः कॉल स्टैक का उपयोग करते हुए, चूँकि अन्य विधियों का उपयोग किया जा सकता है)। नियंत्रण प्रवाह के साथ रिकर्सिव कॉल को परिवर्तित करके और प्रोग्राम द्वारा स्पष्ट रूप से प्रबंधित स्टैक (डेटा संरचना) के साथ कॉल स्टैक को अनुकरण करके प्रत्येक रिकर्सन फ़ंक्शन को पुनरावृत्त फ़ंक्शन में परिवर्तित किया जा सकता है।^[8]^[9]

इसके विपरीत, कंप्यूटर द्वारा मूल्यांकन किए जा सकने वाले सभी पुनरावृत्त कार्यों और प्रक्रियाओं (ट्यूरिंग पूर्णता देखें) को रिकर्सन कार्यों के संदर्भ में व्यक्त किया जा सकता है; पुनरावृत्त नियंत्रण निर्माण जैसे कि लूप और लूप के लिए फ़ंक्शन लैंग्वेज में रिकर्सन रूप में नियमित रूप से फिर से लिखे जाते हैं।^[10]^[11] चूँकि, अभ्यास में यह पुनर्लेखन टेल कॉल उन्मूलन पर निर्भर करता है, जो सभी लैंग्वेज की विशेषता नहीं है। सी (प्रोग्रामिंग लैंग्वेज), जावा (प्रोग्रामिंग लैंग्वेज), और पायथन (प्रोग्रामिंग लैंग्वेज) उल्लेखनीय मुख्यधारा की लैंग्वेज हैं जिनमें टेल कॉल सहित सभी फ़ंक्शन कॉल स्टैक आवंटन का कारण बन सकते हैं जो लूपिंग निर्माणों के उपयोग से नहीं होती है; इन लैंग्वेज में, रिकर्सन रूप में फिर से लिखा गया कार्यशील पुनरावृत्त प्रोग्राम स्टैक ओवरफ़्लो हो सकता है, चूँकि टेल कॉल एलिमिनेशन ऐसी विशेषता हो सकती है जो किसी लैंग्वेज के विनिर्देशन द्वारा कवर नहीं की जाती है, और ही लैंग्वेज के विभिन्न कार्यान्वयन टेल कॉल एलिमिनेशन क्षमताओं में भिन्न हो सकते हैं।

प्रदर्शन उद्देश्य

लैंग्वेज में (जैसे कि सी (प्रोग्रामिंग लैंग्वेज) और जावा (प्रोग्रामिंग लैंग्वेज)) जो पुनरावृत्त लूपिंग निर्माणों का पक्ष लेते हैं, सामान्यतः रिकर्सन प्रोग्रामों से जुड़े महत्वपूर्ण समय और स्थान की निवेश होती है, स्टैक के मैनेजमेंट के लिए आवश्यक ओवरहेड और सापेक्ष धीमेपन के कारण फ़ंक्शन कॉल; फ़ंक्शन लैंग्वेज में, फ़ंक्शन कॉल (विशेष रूप से टेल कॉल) सामान्यतः बहुत तेज़ ऑपरेशन होता है, और अंतर सामान्यतः कम ध्यान देने योग्य होता है।

ठोस उदाहरण के रूप में, उपरोक्त तथ्यात्मक उदाहरण के रिकर्सन और पुनरावृत्त कार्यान्वयन के बीच प्रदर्शन में अंतर उपयोग किए गए कंपाइलर पर अत्यधिक निर्भर करता है। उन लैंग्वेज में जहां लूपिंग संरचनाओं को प्राथमिकता दी जाती है, पुनरावृत्त संस्करण रिकर्सन की तुलना में तीव्रता के अनेक क्रमों के सामान हो सकता है। फ़ंक्शन लैंग्वेज में, दो कार्यान्वयनों का समग्र समय अंतर नगण्य हो सकता है; वास्तव में, छोटी संख्याओं के अतिरिक्त पहले बड़ी संख्याओं को गुणा करने की निवेश (जो कि यहाँ दिया गया पुनरावृत्त संस्करण ऐसा करने के लिए होता है) रिकर्सन को चुनकर बचाए गए किसी भी समय को अभिभूत कर सकता है।

स्टैक स्पेस

कुछ प्रोग्रामिंग लैंग्वेज में, कॉल स्टैक का अधिकतम आकार हीप (प्रोग्रामिंग) में उपलब्ध स्थान से बहुत कम है, और रिकर्सन एल्गोरिदम को पुनरावृत्त एल्गोरिदम की तुलना में अधिक स्टैक स्थान की आवश्यकता होती है। परिणाम स्वरुप, यह लैंग्वेज कभी-कभी स्टैक ओवरफ़्लो से बचने के लिए रिकर्सन की डेप्थ पर सीमा लगाती हैं; पाइथन (प्रोग्रामिंग लैंग्वेज) ऐसी लैंग्वेज है।^[12] टेल रिकर्सन के विशेष स्थिति के संबंध में नीचे दी गई चेतावनी पर ध्यान दें।

अंतर्यता

क्योंकि रिकर्सन एल्गोरिदम स्टैक ओवरफ्लो के अधीन हो सकते हैं, वह पैथोलॉजिकल (गणित) या मैलवेयर इनपुट के प्रति संवेदनशील हो सकते हैं।^[13] कुछ मैलवेयर विशेष रूप से प्रोग्राम के कॉल स्टैक को लक्षित करते हैं और स्टैक की अंतर्निहित रिकर्सन प्रकृति का लाभ उठाते हैं।^[14] मैलवेयर की अनुपस्थिति में भी, अनबाउंड रिकर्सन के कारण होने वाला स्टैक ओवरफ्लो प्रोग्राम के लिए घातक हो सकता है, और अपवाद हैंडलिंग लॉजिक संबंधित प्रोसेस (कंप्यूटिंग) को प्रोसेस स्टेट या टर्मिनेटेड होने से नहीं रोक सकता है।^[15]

रिकर्सन समस्याओं को गुणा करें

गुणा रिकर्सन समस्याएं स्वाभाविक रूप से रिकर्सन होती हैं, क्योंकि पूर्व स्थिति के कारण उन्हें ट्रैक करने की आवश्यकता होती है। उदाहरण ट्री ट्रैवर्सल है जैसा कि डेप्थ-फर्स्ट सर्च में है; चूँकि दोनों रिकर्सन और पुनरावृत्त विधियों का उपयोग किया जाता है,^[16] वह लिस्ट्स में लिस्ट्स ट्रैवर्सल और रैखिक खोज के विपरीत हैं, जो अकेला रिकर्सन है और इस प्रकार स्वाभाविक रूप से पुनरावृत्त विधि है। अन्य उदाहरणों में डिवाइड एंड कॉन्कर एल्गोरिथ्म जैसे क्विकसॉर्ट और एकरमैन फ़ंक्शन जैसे फ़ंक्शन सम्मिलित हैं। इन सभी एल्गोरिदम को स्पष्ट स्टैक (डेटा संरचना) की सहायता से पुनरावृत्त रूप से प्रयुक्त किया जा सकता है, किन्तु स्टैक के मैनेजमेंट में सम्मिलित प्रोग्रामर का प्रयास, और परिणामी प्रोग्राम की काम्प्लेक्सता, यकीनन पुनरावृत्त समाधान के किसी भी लाभ से अधिक है।

रिफैक्टरिंग रिकर्सन

रिकर्सन एल्गोरिदम को गैर-रिकर्सन समकक्षों से बदला जा सकता है।^[17] रिकर्सन एल्गोरिदम को परिवर्तित करने के लिए विधि स्टैक-आधारित मेमोरी आवंटन के स्थान पर मेमोरी मैनेजमेंट का उपयोग करके उन्हें अनुकरण करना है।^[18] विकल्प पूरी तरह से गैर-रिकर्सन विधियों पर आधारित प्रतिस्थापन एल्गोरिदम विकसित करना है, जो चुनौतीपूर्ण हो सकता है।^[19] उदाहरण के लिए, वाइल्डकार्ड मिलान के लिए रिकर्सिव एल्गोरिद्म, जैसे रिच साल्ज़' वाइल्डमैट एल्गोरिद्म,^[20] कभी विशिष्ट थे। उसी उद्देश्य के लिए गैर-रिकर्सन एल्गोरिदम, जैसे क्रॉस मैचिंग वाइल्डकार्ड एल्गोरिथम, को रिकर्सन की कमियों से बचने के लिए विकसित किया गया है।^[21] और सॉफ्टवेयर परीक्षण और प्रोफाइलिंग (कंप्यूटर प्रोग्रामिंग) प्रदर्शन जैसी तकनीकों के आधार पर केवल क्रमशः सुधार हुआ है।^[22]

टेल-रिकर्सन कार्य

टेल-रिकर्सिव फ़ंक्शंस ऐसे फ़ंक्शंस हैं जिनमें सभी रिकर्सिव कॉल्स टेल कॉल्स होते हैं और इसलिए किसी भी आस्थगित ऑपरेशन का निर्माण नहीं करते हैं। उदाहरण के लिए, जीसीडी फ़ंक्शन (नीचे फिर से दिखाया गया है) टेल-रिकर्सन है। इसके विपरीत, फैक्टोरियल फ़ंक्शन (नीचे भी) टेल-रिकर्सिव नहीं है; क्योंकि इसकी रिकर्सिव कॉल टेल की स्थिति में नहीं है, यह आस्थगित गुणा संचालन बनाता है जिसे अंतिम रिकर्सिव कॉल पूर्ण होने के पश्चात् किया जाना चाहिए। कंपाइलर या इंटरप्रेटर (कंप्यूटिंग) के साथ जो टेल-रिकर्सिव कॉल को फ़ंक्शन कॉल के अतिरिक्त के रूप में मानता है, जीसीडी जैसे टेल-रिकर्सन फ़ंक्शन निरंतर स्थान का उपयोग करके निष्पादित करता है। इस प्रकार प्रोग्राम इम्प्रेटिव रूप से पुनरावृत्त है, इम्प्रेटिव लैंग्वेज नियंत्रण संरचनाओं का उपयोग करने के लिए और लूप के समय उपयोग किया जाता है।

टेल रेकर्सन

संवर्धित रिकर्सन :

//INPUT: Integers x, y such that x >= y and y >= 0
int gcd(int x, int y)
{
  if (y == 0)
     return x;
  else
     return gcd(y, x % y);
}

//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}

टेल रिकर्सन का महत्व यह है कि टेल-रिकर्सिव कॉल (या कोई टेल कॉल) करते समय, कॉलर की वापसी स्थिति को कॉल स्टैक पर सेव करने की आवश्यकता नहीं होती है; जब रिकर्सिव कॉल वापस आती है, तो यह पहले से सहेजी गई वापसी स्थिति पर सीधे सम्बंधित होती है। इसलिए, उन लैंग्वेज में जो टेल कॉल्स के इस गुण को पहचानती हैं, टेल रिकर्सन स्पेस और टाइम दोनों को बचाता है।

निष्पादन का क्रम

इन दो कार्यों पर विचार करें:

फंक्शन 1

void recursiveFunction(int num) {
    printf("%d\n", num);
    if (num < 4)
        recursiveFunction(num + 1);
}

फंक्शन 2

void recursiveFunction(int num) {
    if (num < 4)
        recursiveFunction(num + 1);
    printf("%d\n", num);
}

फंक्शन 2 फंक्शन 1 है जिसमें लाइनों को परिवर्तन किया जाता है।

किसी फ़ंक्शन के केवल बार कॉल करने के स्थिति में, रिकर्सिव कॉल से पहले रखे गए निर्देशों को रिकर्सिव कॉल के पश्चात् दिए गए किसी भी निर्देश से पहले बार रिकर्सन निष्पादित किया जाता है। अधिकतम रिकर्सन तक पहुंचने के पश्चात् पश्चात् वाले को अधिकांशतः निष्पादित किया जाता है।

यह भी ध्यान दें कि प्रिंट स्टेटमेंट का क्रम उल्टा है, जो कि कॉल स्टैक पर फ़ंक्शन और स्टेटमेंट को संग्रहीत करने के विधि के कारण है।

रिकर्सन प्रक्रियाएं

फैक्टोरियल

रिकर्सन प्रक्रिया का उत्कृष्ट उदाहरण प्राकृतिक संख्या के भाज्य की गणना करने के लिए उपयोग किया जाने वाला कार्य है:

\operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}

स्यूडोकोड (पुनरावर्ती):

function factorial is:

input: integer n such that n >= 0

output: [n × (n-1) × (n-2) × ... × 1]


 1. if n is 0, return 1
 2. otherwise, return [ n × factorial(n-1) ]


end factorial

फ़ंक्शन को रिकर्सन संबंध के रूप में भी लिखा जा सकता है:

b_{n}=nb_{n-1}

b_{0}=1

रिकर्सन संबंध का यह मूल्यांकन उस संगणना को प्रदर्शित करता है जो उपरोक्त स्यूडोकोड के मूल्यांकन में किया जाएगा:

n = 4 के लिए रिकर्सन संबंध की गणना:
b₄ = 4 × b₃ = 4 × (3 × b₂) = 4 × (3 × (2 × b₁)) = 4 × (3 × (2 × (1 × b₀))) = 4 × (3 × (2 × (1 × 1))) = 4 × (3 × (2 × 1)) = 4 × (3 × 2) = 4 × 6 = 24

इम्प्रेटिव प्रोग्रामिंग लैंग्वेज में पाए जाने वाले विशिष्ट लूपिंग निर्माणों का उपयोग करके रिकर्सन का उपयोग किए बिना इस फैक्टोरियल फ़ंक्शन का भी वर्णन किया जा सकता है:

स्यूडोकोड (पुनरावृत्त):

function factorial is:

input: integer n such that n >= 0

output: [n × (n-1) × (n-2) × ... × 1]


 1. create new variable called running_total with a value of 1


 2. begin loop
 1. if n is 0, exit loop
 2. set running_total to (running_total × n)
 3. decrement n
 4. repeat loop


 3. return running_total


end factorial

उपरोक्त इम्प्रेटिव कोड संचायक वैरीएबल का उपयोग करके इस गणितीय परिभाषा $t$ के सामान है :

{\begin{aligned}\operatorname {fact} (n)&=\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&={\begin{cases}t&{\mbox{if }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{if }}n>0\\\end{cases}}\end{aligned}}

ऊपर दी गई परिभाषा सीधे फ़ंक्शन प्रोग्रामिंग लैंग्वेज जैसे कि प्रोग्राम (प्रोग्रामिंग लैंग्वेज) में अनुवाद करती है; यह रिकर्सन रूप से कार्यान्वित रिकर्सन का उदाहरण है।

सबसे बड़ा सामान्य विभाजक

यूक्लिडियन एल्गोरिथ्म, जो दो पूर्णांकों के सबसे बड़े सामान्य विभाजक की गणना करता है, जिसको रिकर्सन रूप से लिखा जा सकता है।

फ़ंक्शन परिभाषा::

\gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}

स्यूडोकोड (पुनरावर्ती):
function gcd is: input: integer x, integer y such that x > 0 and y >= 0 1. if y is 0, return x 2. otherwise, return [ gcd( y, (remainder of x/y) ) ] end gcd

सबसे बड़े सामान्य विभाजक के लिए रिकर्सन संबंध, जहाँ $x\%y$ शेष $x/y$ व्यक्त करता है :

\gcd(x,y)=\gcd(y,x\%y)

यदि

y\neq 0

\gcd(x,0)=x

x = 27 और y = 9 के लिए रिकर्सन संबंध की गणना:
gcd(27, 9) = gcd(9, 27 % 9) = gcd(9, 0) = 9
x = 111 और y = 259 के लिए रिकर्सन संबंध की गणना:
gcd(111, 259) = gcd(259, 111 % 259) = gcd(259, 111) = gcd(111, 2595% 111) = gcd(111, 37) = gcd(37, 111 % 37) = gcd(37, 0) = 37

उपरोक्त रिकर्सन प्रोग्राम टेल-रिकर्सन है; यह पुनरावृत्त एल्गोरिथम के समतुल्य है, और ऊपर दिखाई गई गणना मूल्यांकन के फेज को दर्शाती है जो ऐसी लैंग्वेज द्वारा निष्पादित की जाएगी जो टेल कॉल को समाप्त करती है। नीचे उसी एल्गोरिदम का संस्करण है जो स्पष्ट रिकर्सन का उपयोग करता है, जो उस लैंग्वेज के लिए उपयुक्त है जो टेल कॉल को समाप्त नहीं करता है। अपनी स्थिति को पूरी तरह से वैरीएबल x और y में बनाए रखने और लूपिंग निर्माण का उपयोग करके, प्रोग्राम रिकर्सिव कॉल करने और कॉल स्टैक को बढ़ाने से बचता है।

स्यूडोकोड (पुनरावृत्त):

function gcd is:

input: integer x, integer y such that x >= y and y >= 0


 1. create new variable called remainder


 2. begin loop
 1. if y is zero, exit loop
 2. set remainder to the remainder of x/y
 3. set x to y
 4. set y to remainder
 5. repeat loop


 3. return x


end gcd

पुनरावृत्त एल्गोरिथ्म के लिए अस्थायी वैरीएबल की आवश्यकता होती है, और यहां तक कि यूक्लिडियन एल्गोरिथ्म के ज्ञान को सरल निरीक्षण द्वारा प्रक्रिया को समझना अधिक कठिन होता है, चूँकि दो एल्गोरिदम उनके फेज में बहुत समान हैं।

हनोई के टावर्स

हनोई की मीनारें

हनोई के टावर्स गणितीय पहेली है जिसका समाधान रिकर्सन को दर्शाता है।^[23]^[24] तीन खूंटे हैं जो विभिन्न व्यास के डिस्क के संग्रह को पकड़ सकते हैं। बड़ी डिस्क को कभी भी छोटी डिस्क के ऊपर नहीं रखा जा सकता है। पेग पर एन डिस्क से प्रारंभ करके, उन्हें बार में दूसरे पेग पर ले जाना चाहिए। स्टैक को स्थानांतरित करने के लिए फेज की सबसे छोटी संख्या क्या है?

फ़ंक्शन परिभाषा::

\operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}

हनोई के लिए रिकर्सन संबंध:

h_{n}=2h_{n-1}+1

h_{1}=1

n = 4 के लिए रिकर्सन संबंध की गणना:
hanoi(4) = 2×hanoi(3) + 1 = 2×(2×hanoi(2) + 1) + 1 = 2×(2×(2×hanoi(1) + 1) + 1) + 1 = 2×(2×(2×1 + 1) + 1) + 1 = 2×(2×(3) + 1) + 1 = 2×(7) + 1 = 15

उदाहरण कार्यान्वयन:

स्यूडोकोड (पुनरावर्ती):
function hanoi is: input: integer n, such that n >= 1 1. if n is 1 then return 1 2. return [2 * [call hanoi(n-1)] + 1] end hanoi

चूँकि सभी रिकर्सन कार्यों का स्पष्ट समाधान नहीं है, हनोई अनुक्रम के टॉवर को स्पष्ट सूत्र में घटाया जा सकता है।^[25]

हनोई के टावर्स के लिए स्पष्ट सूत्र:
h₁ = 1 = 2¹ - 1 h₂ = 3 = 2² - 1 h₃ = 7 = 2³ - 1 h₄ = 15 = 2⁴ - 1 h₅ = 31 = 2⁵ - 1 h₆ = 63 = 2⁶ - 1 h₇ = 127 = 2⁷ - 1 In general: h_n = 2ⁿ - 1, for all n >= 1

बाइनरी खोज

बाइनरी खोज एल्गोरिदम प्रत्येक रिकर्सिव पास के साथ सरणी को आधे में काटकर एकल अवयव के लिए सॉर्ट किए गए सरणी को खोजने का विधि है। चाल सरणी के केंद्र के पास मध्य बिंदु लेने के लिए है, उस बिंदु पर डेटा की खोज की जा रही डेटा के साथ तुलना करें और फिर तीन संभावित स्थितियों में से का जवाब दें: डेटा मध्य बिंदु पर पाया जाता है, मध्य बिंदु पर डेटा अधिक होता है खोजे जा रहे डेटा की तुलना में, या मध्यबिंदु पर डेटा खोजे जा रहे डेटा से कम है।

इस एल्गोरिदम में रिकर्सन का उपयोग किया जाता है क्योंकि प्रत्येक पास के साथ पुराने को आधे में काटकर नई सरणी बनाई जाती है। बाइनरी खोज प्रक्रिया को फिर रिकर्सन रूप से कहा जाता है, इसे बार नई (और छोटी) सरणी पर। सामान्यतः सरणी के आकार को प्रारंभ और समाप्ति सूचकांक में परिवर्तन करके समायोजित किया जाता है। एल्गोरिथ्म विकास के लघुगणकीय क्रम को प्रदर्शित करता है क्योंकि यह इम्प्रेटिव रूप से समस्या डोमेन को प्रत्येक पास के साथ आधे में विभाजित करता है।

C में बाइनरी खोज का उदाहरण कार्यान्वयन:

 /*
  Call binary_search with proper initial conditions.

  INPUT:
    data is an array of integers SORTED in ASCENDING order,
    toFind is the integer to search for,
    count is the total number of elements in the array

  OUTPUT:
    result of binary_search

 */
 int search(int *data, int toFind, int count)
 {
    //  Start = 0 (beginning index)
    //  End = count - 1 (top index)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Binary Search Algorithm.

   INPUT:
        data is a array of integers SORTED in ASCENDING order,
        toFind is the integer to search for,
        start is the minimum array index,
        end is the maximum array index
   OUTPUT:
        position of the integer toFind within array data,
        -1 if not found
 */
 int binary_search(int *data, int toFind, int start, int end)
 {
    //Get the midpoint.
    int mid = start + (end - start)/2;   //Integer division


    if (start > end)                     //Stop condition (base case)
       return -1;
    else if (data[mid] == toFind)        //Found, return index
       return mid;
    else if (data[mid] > toFind)         //Data is greater than toFind, search lower half
       return binary_search(data, toFind, start, mid-1);
    else                                 //Data is less than toFind, search upper half
       return binary_search(data, toFind, mid+1, end);
 }

रिकर्सन डेटा संरचनाएं (संरचनात्मक रिकर्सन)

कंप्यूटर विज्ञान में रिकर्सन का महत्वपूर्ण अनुप्रयोग डायनामिक डेटा संरचनाओं जैसे लिस्ट्स (सार डेटा प्रकार) और ट्री (डेटा संरचना) को परिभाषित करने में है। रनटाइम आवश्यकताओं के जवाब में रिकर्सन डेटा संरचनाएं डायनामिक रूप से सैद्धांतिक रूप से परिमित आकार तक बढ़ सकती हैं; इसके विपरीत, स्थिर सरणी का आकार संकलन समय पर सेट होना चाहिए।

रिकर्सन एल्गोरिदम विशेष रूप से उपयुक्त होते हैं जब अंतर्निहित समस्या या इलाज किए जाने वाले डेटा को रिकर्सन शब्दों में परिभाषित किया जाता है।^[26]

इस खंड के उदाहरण बताते हैं कि संरचनात्मक रिकर्सन के रूप में क्या जाना जाता है। यह शब्द इस तथ्य को संदर्भित करता है कि रिकर्सन प्रक्रियाएं उस डेटा पर कार्य कर रही हैं जिसे रिकर्सन रूप से परिभाषित किया गया है।

जब तक प्रोग्रामर डेटा परिभाषा से टेम्पलेट प्राप्त करता है, तब तक फ़ंक्शन संरचनात्मक रिकर्सन को नियोजित करता है। यही है, किसी फ़ंक्शन के शरीर में रिकर्सन किसी दिए गए कंपाउंड वैल्यू के कुछ तत्काल टुकड़े का उपभोग करते हैं।^[27]

लिंक की गई सूचियां

लिंक की गई लिस्ट्स नोड संरचना की सी परिभाषा नीचे दी गई है। विशेष रूप से ध्यान दें कि कैसे नोड को स्वयं के संदर्भ में परिभाषित किया गया है। स्ट्रक्वैरीएबल नोड का अगला अवयव दूसरे स्ट्रक्वैरीएबल नोड के लिए सूचक है, प्रभावी रूप से लिस्ट्स प्रकार बना रहा है।

struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};

क्योंकि संरचना नोड डेटा संरचना को रिकर्सन रूप से परिभाषित किया गया है, इस पर चलने वाली प्रक्रियाओं को स्वाभाविक रूप से रिकर्सन प्रक्रियाओं के रूप में प्रयुक्त किया जा सकता है। नीचे दी गई list_print प्रक्रिया लिस्ट्स के रिक्त होने तक नीचे चलती है (अर्थात, लिस्ट्स सूचक का मान NULL है)। प्रत्येक नोड के लिए यह डेटा अवयव ( पूर्णांक) प्रिंट करता है। सी कार्यान्वयन में, लिस्ट्स list_print प्रक्रिया द्वारा अपरिवर्तित बनी हुई है।

void list_print(struct node *list)
{
    if (list != NULL)               // base case
    {
       printf ("%d ", list->data);  // print integer data followed by a space
       list_print (list->next);     // recursive call on the next node
    }
}

बाइनरी ट्री

नीचे बाइनरी ट्री नोड के लिए सरल परिभाषा दी गई है। लिंक की गई सूचियों के लिए नोड की तरह, इसे रिकर्सन रूप से स्वयं के संदर्भ में परिभाषित किया गया है। दो स्व-संदर्भित संकेत हैं: बाएँ (बाएँ सब-ट्री की ओर संकेत करते हुए) और दाएँ (दाएँ सब-ट्री की ओर संकेत करते हुए)।

struct node
{
  int data;            // some integer data
  struct node *left;   // pointer to the left subtree
  struct node *right;  // point to the right subtree
};

रिकर्सन का उपयोग करके ट्री पर संचालन को प्रयुक्त किया जा सकता है। ध्यान दें कि क्योंकि दो स्व-संदर्भ सूचक (बाएं और दाएं) हैं, ट्री के संचालन के लिए दो रिकर्सिव कॉल की आवश्यकता हो सकती है:

// Test if tree_node contains i; return 1 if so, 0 if not.
int tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return 0;  // base case
    else if (tree_node->data == i)
        return 1;
    else
        return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);
}

जैसा कि ऊपर परिभाषित किया गया है, ट्री में सम्मिलित है को किसी भी कॉल के लिए अधिकतम दो रिकर्सिव कॉल किए जाएंगे।

// Inorder traversal:
void tree_print(struct node *tree_node) {
    if (tree_node != NULL) {              // base case
        tree_print(tree_node->left);      // go left
        printf("%d ", tree_node->data);   // print the integer followed by a space
        tree_print(tree_node->right);     // go right
    }
}

ऊपर दिया गया उदाहरण ट्री ट्रैवर्सल या बाइनरी ट्री के इन-ऑर्डर ट्रैवर्सल को दिखाता है। बाइनरी सर्च ट्री बाइनरी ट्री का विशेष स्थिति है जहां प्रत्येक नोड के डेटा अवयव क्रम में होते हैं।

फाइलसिस्टम ट्रैवर्सल

चूंकि फ़ाइल सिस्टम में फ़ाइलों की संख्या भिन्न हो सकती है, रिकर्सन ट्रैवर्स करने का एकमात्र व्यावहारिक विधि है और इस प्रकार इसकी कंटेंट की गणना करता है। फ़ाइल सिस्टम को ट्रैवर्स करना ट्री ट्रैवर्सल के समान है, इसलिए ट्री ट्रैवर्सल के पीछे की अवधारणा फ़ाइल सिस्टम को ट्रैवर्स करने पर प्रयुक्त होती है। अधिक विशेष रूप से, नीचे दिया गया कोड फ़ाइल सिस्टम के प्रीऑर्डर ट्रैवर्सल का उदाहरण होता है।

import java.io.File;

public class FileSystem {

	public static void main(String [] args) {
		traverse();
	}

	/**
	 * Obtains the filesystem roots
	 * Proceeds with the recursive filesystem traversal
	 */
	private static void traverse() {
		File[] fs = File.listRoots();
		for (int i = 0; i < fs.length; i++) {
			System.out.println(fs[i]);
			if (fs[i].isDirectory() && fs[i].canRead()) {
				rtraverse(fs[i]);
			}
		}
	}

	/**
	 * Recursively traverse a given directory
	 *
	 * @param fd indicates the starting point of traversal
	 */
	private static void rtraverse(File fd) {
		File[] fss = fd.listFiles();

		for (int i = 0; i < fss.length; i++) {
			System.out.println(fss[i]);
			if (fss[i].isDirectory() && fss[i].canRead()) {
				rtraverse(fss[i]);
			}
		}
	}

}

यह कोड रिकर्सन और रिकर्सन दोनों है - फ़ाइलें और निर्देशिकाएं पुनरावृत्त होती हैं, और प्रत्येक निर्देशिका रिकर्सन रूप से खोली जाती है।

"आरट्रैवर्स" विधि प्रत्यक्ष रिकर्सन का उदाहरण है, जबकि "ट्रैवर्स" विधि रैपर फ़ंक्शन है।

"बेस केस" परिदृश्य यह है कि किसी दिए गए फ़ाइल सिस्टम में सदैव फ़ाइलों और/या निर्देशिकाओं की निश्चित संख्या होती है।

रिकर्सन एल्गोरिदम की समय-दक्षता

रिकर्सन एल्गोरिदम की समय दक्षता को बिग ओ नोटेशन के रिकर्सन संबंध में व्यक्त किया जा सकता है। वह (सामान्यतः) तब बिग-ओ टर्म में सरलीकृत हो सकते हैं।

शॉर्टकट नियम (मास्टर प्रमेय)

यदि फ़ंक्शन की समय-काम्प्लेक्सता रूप में है

T(n)=a\cdot T(n/b)+f(n)

फिर समय-काम्प्लेक्सता का बिग ओ इस प्रकार है:

If $f(n)=O(n^{\log _{b}a-\varepsilon })$ for some constant $\varepsilon >0$ , then $T(n)=\Theta (n^{\log _{b}a})$
If $f(n)=\Theta (n^{\log _{b}a})$ , then $T(n)=\Theta (n^{\log _{b}a}\log n)$
If $f(n)=\Omega (n^{\log _{b}a+\varepsilon })$ for some constant $\varepsilon >0$ , and if $a\cdot f(n/b)\leq c\cdot f(n)$ for some constant $c < 1$ and all sufficiently large $n$ , then $T(n)=\Theta (f(n))$

जहाँ पर $a$ रिकर्सन के प्रत्येक स्तर पर रिकर्सिव कॉल की संख्या का प्रतिनिधित्व करता है, $b$ रिकर्सन के अगले स्तर के लिए इनपुट किस कारक से छोटा है, इसका प्रतिनिधित्व करता है (अर्थात आप समस्या को विभाजित करने वाले टुकड़ों की संख्या), और $f (n)$ उस कार्य का प्रतिनिधित्व करता है जो फ़ंक्शन रिकर्सन के प्रत्येक स्तर पर किसी भी रिकर्सन (जैसे विभाजन, पुनर्संयोजन) से स्वतंत्र रूप से करता है।

यह भी देखें

फ़ंक्शन प्रोग्रामिंग
कम्प्यूटेशनल समस्या
एसक्यूएल में श्रेणीबद्ध और रिकर्सन प्रश्न
क्लेन-रॉसर विरोधाभास
ओपन रिकर्सन
रिकर्सन
सीरपिन्स्की वक्र
मैककार्थी 91 फंक्शन
μ-रिकर्सन कार्य
मौलिक रिकर्सन कार्य
तक (फ़ंक्शन)

↑ Graham, Ronald; Knuth, Donald; Patashnik, Oren (1990). "1: Recurrent Problems". ठोस गणित. ISBN 0-201-55802-5.
↑ Kuhail, M. A.; Negreiros, J.; Seffah, A. (2021). "अनप्लग्ड गतिविधियों का उपयोग करके पुनरावर्ती सोच सिखाना" (PDF). WTE&TE. 19: 169–175.
↑ Epp, Susanna (1995). अनुप्रयोगों के साथ असतत गणित (2nd ed.). p. 427. ISBN 978-0-53494446-9.
↑ Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126. ISBN 978-0-13022418-7.
↑ "कार्यात्मक प्रोग्रामिंग | बहादुर और सच्चे के लिए क्लोजर". www.braveclojure.com. Retrieved 2020-10-21.
↑ 7
↑ Mongan, John; Giguère, Eric; Kindler, Noah (2013). प्रोग्रामिंग इंटरव्यू एक्सपोज़्ड: सीक्रेट टू लैंडिंग योर नेक्स्ट जॉब (3rd ed.). Wiley. p. 115. ISBN 978-1-118-26136-1.
↑ Hetland, Magnus Lie (2010), Python Algorithms: Mastering Basic Algorithms in the Python Language, Apress, p. 79, ISBN 9781430232384.
↑ Drozdek, Adam (2012), Data Structures and Algorithms in C++ (4th ed.), Cengage Learning, p. 197, ISBN 9781285415017.
↑ Shivers, Olin. "द एनाटॉमी ऑफ़ ए लूप - स्कोप और कंट्रोल की कहानी" (PDF). Georgia Institute of Technology. Retrieved 2012-09-03.
↑ Lambda the Ultimate. "एक लूप का एनाटॉमी". Lambda the Ultimate. Retrieved 2012-09-03.
↑ "27.1। sys - सिस्टम-विशिष्ट पैरामीटर और फ़ंक्शंस - पायथन v2.7.3 प्रलेखन". Docs.python.org. Retrieved 2012-09-03.
↑ Krauss, Kirk J. (2014). "मैचिंग वाइल्डकार्ड: एल्गोरिथम को वश में करने का एक अनुभवजन्य तरीका". Dr. Dobb's Journal.
↑ Mueller, Oliver (2012). "स्टैक स्मैशिंग अटैक का एनाटॉमी और कैसे जीसीसी इसे रोकता है". Dr. Dobb's Journal.
↑ "स्टैक ओवरफ्लो एक्सेप्शन क्लास". .NET Framework Class Library. Microsoft Developer Network. 2018.
↑ "डेप्थ फर्स्ट सर्च (डीएफएस): पुनरावृत्त और पुनरावर्ती कार्यान्वयन". Techie Delight. 2018.
↑ Mitrovic, Ivan. "रिकर्सन को इटरेशन से बदलें". ThoughtWorks.
↑ La, Woong Gyu (2015). "स्टैक-ओवरफ्लो से बचने के लिए स्टैक और जबकि-लूप का उपयोग करके पुनरावर्ती कार्यों को कैसे बदलें". CodeProject.
↑ Moertel, Tom (2013). "व्यापार की तरकीबें: पुनरावर्तन से पुनरावृत्ति, भाग 2: समय-यात्रा गुप्त सुविधा ट्रिक के साथ पुनरावर्तन को समाप्त करना".
↑ Salz, Rich (1991). "वाइल्डमैट.सी". GitHub.
↑ Krauss, Kirk J. (2008). "मिलान वाइल्डकार्ड: एक एल्गोरिथम". Dr. Dobb's Journal.
↑ Krauss, Kirk J. (2018). "मैचिंग वाइल्डकार्ड: बिग डेटा के लिए एक बेहतर एल्गोरिथम". Develop for Performance.
↑ Graham, Knuth & Patashnik 1990, §1.1: The Tower of Hanoi
↑ Epp 1995, pp. 427–430: The Tower of Hanoi
↑ Epp 1995, pp. 447–448: An Explicit Formula for the Tower of Hanoi Sequence
↑ Wirth 1976, p. 127
↑ Cite error: Invalid <ref> tag; no text was provided for refs named Felleisen 2002 108

संदर्भ

Barron, David William (1968) [1967]. Written at Cambridge, UK. Gill, Stanley (ed.). Recursive techniques in programming. Macdonald Computer Monographs (1 ed.). London, UK: Macdonald & Co. (Publishers) Ltd. SBN 356-02201-3. (viii+64 pages)
Felleisen, Matthias; Findler, Robert B.; Flatt, Matthew; Krishnamurthi, Shriram (2001). How To Design Programs: An Introduction to Computing and Programming. MIT Press. ISBN 0262062186.
Rubio-Sanchez, Manuel (2017). Introduction to Recursive Programming. CRC Press. ISBN 978-1-351-64717-5.
Pevac, Irena (2016). Practicing Recursion in Java. CreateSpace Independent. ISBN 978-1-5327-1227-2.
Roberts, Eric (2005). Thinking Recursively with Java. Wiley. ISBN 978-0-47170146-0.
Rohl, Jeffrey S. (1984). Recursion Via Pascal. Cambridge University Press. ISBN 978-0-521-26934-6.
Helman, Paul; Veroff, Robert. Walls and Mirrors.
Abelson, Harold; Sussman, Gerald Jay; Sussman, Julie (1996). Structure and Interpretation of Computer Programs (2nd ed.). MIT Press. ISBN 0-262-51087-1.
Dijkstra, Edsger W. (1960). "Recursive Programming". Numerische Mathematik. 2 (1): 312–318. doi:10.1007/BF01386232. S2CID 127891023.

[1] Graham, Ronald; Knuth, Donald; Patashnik, Oren (1990). "1: Recurrent Problems". ठोस गणित. ISBN 0-201-55802-5.

[2] Kuhail, M. A.; Negreiros, J.; Seffah, A. (2021). "अनप्लग्ड गतिविधियों का उपयोग करके पुनरावर्ती सोच सिखाना" (PDF). WTE&TE. 19: 169–175.

[3] Epp, Susanna (1995). अनुप्रयोगों के साथ असतत गणित (2nd ed.). p. 427. ISBN 978-0-53494446-9.

[4] Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126. ISBN 978-0-13022418-7.

[5] "कार्यात्मक प्रोग्रामिंग | बहादुर और सच्चे के लिए क्लोजर". www.braveclojure.com. Retrieved 2020-10-21.

[6] 7

[7] Mongan, John; Giguère, Eric; Kindler, Noah (2013). प्रोग्रामिंग इंटरव्यू एक्सपोज़्ड: सीक्रेट टू लैंडिंग योर नेक्स्ट जॉब (3rd ed.). Wiley. p. 115. ISBN 978-1-118-26136-1.

[8] Hetland, Magnus Lie (2010), Python Algorithms: Mastering Basic Algorithms in the Python Language, Apress, p. 79, ISBN 9781430232384.

[9] Drozdek, Adam (2012), Data Structures and Algorithms in C++ (4th ed.), Cengage Learning, p. 197, ISBN 9781285415017.

[10] Shivers, Olin. "द एनाटॉमी ऑफ़ ए लूप - स्कोप और कंट्रोल की कहानी" (PDF). Georgia Institute of Technology. Retrieved 2012-09-03.

[11] Lambda the Ultimate. "एक लूप का एनाटॉमी". Lambda the Ultimate. Retrieved 2012-09-03.

[12] "27.1। sys - सिस्टम-विशिष्ट पैरामीटर और फ़ंक्शंस - पायथन v2.7.3 प्रलेखन". Docs.python.org. Retrieved 2012-09-03.

[13] Krauss, Kirk J. (2014). "मैचिंग वाइल्डकार्ड: एल्गोरिथम को वश में करने का एक अनुभवजन्य तरीका". Dr. Dobb's Journal.

[14] Mueller, Oliver (2012). "स्टैक स्मैशिंग अटैक का एनाटॉमी और कैसे जीसीसी इसे रोकता है". Dr. Dobb's Journal.

[15] "स्टैक ओवरफ्लो एक्सेप्शन क्लास". .NET Framework Class Library. Microsoft Developer Network. 2018.

[16] "डेप्थ फर्स्ट सर्च (डीएफएस): पुनरावृत्त और पुनरावर्ती कार्यान्वयन". Techie Delight. 2018.

[17] Mitrovic, Ivan. "रिकर्सन को इटरेशन से बदलें". ThoughtWorks.

[18] La, Woong Gyu (2015). "स्टैक-ओवरफ्लो से बचने के लिए स्टैक और जबकि-लूप का उपयोग करके पुनरावर्ती कार्यों को कैसे बदलें". CodeProject.

[19] Moertel, Tom (2013). "व्यापार की तरकीबें: पुनरावर्तन से पुनरावृत्ति, भाग 2: समय-यात्रा गुप्त सुविधा ट्रिक के साथ पुनरावर्तन को समाप्त करना".

[20] Salz, Rich (1991). "वाइल्डमैट.सी". GitHub.

[21] Krauss, Kirk J. (2008). "मिलान वाइल्डकार्ड: एक एल्गोरिथम". Dr. Dobb's Journal.

[22] Krauss, Kirk J. (2018). "मैचिंग वाइल्डकार्ड: बिग डेटा के लिए एक बेहतर एल्गोरिथम". Develop for Performance.

[23] Graham, Knuth & Patashnik 1990, §1.1: The Tower of Hanoi

[24] Epp 1995, pp. 427–430: The Tower of Hanoi

[25] Epp 1995, pp. 447–448: An Explicit Formula for the Tower of Hanoi Sequence

[26] Wirth 1976, p. 127

[Felleisen_2002_108-27] Cite error: Invalid <ref> tag; no text was provided for refs named Felleisen 2002 108

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

@@ Line 770: / Line 770: @@
 जहाँ पर {{mvar|a}} रिकर्सन के प्रत्येक स्तर पर रिकर्सिव कॉल की संख्या का प्रतिनिधित्व करता है, {{mvar|b}} रिकर्सन के अगले स्तर के लिए इनपुट किस कारक से छोटा है, इसका प्रतिनिधित्व करता है (अर्थात आप समस्या को विभाजित करने वाले टुकड़ों की संख्या), और {{math|''f''(''n'')}} उस कार्य का प्रतिनिधित्व करता है जो फ़ंक्शन रिकर्सन के प्रत्येक स्तर पर किसी भी रिकर्सन (जैसे विभाजन, पुनर्संयोजन) से स्वतंत्र रूप से करता है।
-[[Category:Articles with hatnote templates targeting a nonexistent page|Recursion (Computer Science)]]
-[[Category:Articles with invalid date parameter in template|Recursion (Computer Science)]]
-[[Category:CS1 location test|Recursion (Computer Science)]]
-[[Category:Created On 14/12/2022|Recursion (Computer Science)]]
-[[Category:Machine Translated Page|Recursion (Computer Science)]]
-[[Category:Pages with math errors|Recursion (Computer Science)]]
-[[Category:Pages with math render errors|Recursion (Computer Science)]]
-[[Category:Pages with reference errors|Recursion (Computer Science)]]
-[[Category:Pages with script errors|Recursion (Computer Science)]]
-[[Category:Pages with syntax highlighting errors|Recursion (Computer Science)]]
 == यह भी देखें                                                                                                                                                                                                                ==
@@ Line 809: / Line 809: @@
 * {{cite journal |author-first=Edsger W. |author-last=Dijkstra |author-link=Edsger W. Dijkstra |title=Recursive Programming |journal=Numerische Mathematik |volume=2 |issue=1 |date=1960 |pages=312–318 |doi=10.1007/BF01386232|s2cid=127891023 }}
 {{refend}}
-{{DEFAULTSORT:Recursion (Computer Science)}}[[Category:सैद्धांतिक कंप्यूटर विज्ञान]]
+{{DEFAULTSORT:Recursion (Computer Science)}}
-[[Category:रिकर्सन]]
-[[Category: संगणनीयता सिद्धांत]]
-[[Category: स्यूडोकोड उदाहरण के साथ लेख]]
-[[Category: प्रोग्रामिंग मुहावरे]]
-[[Category: सबरूटीन्स]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Recursion (Computer Science)]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with invalid date parameter in template|Recursion (Computer Science)]]
-[[Category:Created On 14/12/2022]]
+[[Category:CS1 location test|Recursion (Computer Science)]]
-[[Category:Vigyan Ready]]
+[[Category:Citation Style 1 templates|M]]
+[[Category:Collapse templates]]
+[[Category:Created On 14/12/2022|Recursion (Computer Science)]]
+[[Category:Lua-based templates|Recursion (Computer Science)]]
+[[Category:Machine Translated Page|Recursion (Computer Science)]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages that use a deprecated format of the math tags|Recursion (Computer Science)]]
+[[Category:Pages with math errors|Recursion (Computer Science)]]
+[[Category:Pages with math render errors|Recursion (Computer Science)]]
+[[Category:Pages with reference errors|Recursion (Computer Science)]]
+[[Category:Pages with script errors|Recursion (Computer Science)]]
+[[Category:Pages with syntax highlighting errors|Recursion (Computer Science)]]
+[[Category:Short description with empty Wikidata description|Recursion (Computer Science)]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready|Recursion (Computer Science)]]
+[[Category:Templates based on the Citation/CS1 Lua module]]
+[[Category:Templates generating COinS|Cite magazine]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category|Recursion (Computer Science)]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions|Recursion (Computer Science)]]
+[[Category:Templates using TemplateData|Recursion (Computer Science)]]
+[[Category:Wikipedia articles needing clarification from September 2020|Recursion (Computer Science)]]
+[[Category:Wikipedia fully protected templates|Cite magazine]]
+[[Category:Wikipedia metatemplates]]
+[[Category:प्रोग्रामिंग मुहावरे|Recursion (Computer Science)]]
+[[Category:रिकर्सन|Recursion (Computer Science)]]
+[[Category:संगणनीयता सिद्धांत|Recursion (Computer Science)]]
+[[Category:सबरूटीन्स|Recursion (Computer Science)]]
+[[Category:सैद्धांतिक कंप्यूटर विज्ञान|Recursion (Computer Science)]]
+[[Category:स्यूडोकोड उदाहरण के साथ लेख|Recursion (Computer Science)]]

Anonymous

Search