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

This article is about समस्याओं को हल करने के लिए पुनरावर्ती दृष्टिकोण. For पुनरावृत्ति द्वारा प्रमाण, see गणितीय प्रवर्तन. For कंप्यूटर विज्ञान के परिवर्णी शब्दों में पुनरावर्तन, see Recursive acronym § Computer-related examples.

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

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

रिकर्सन की शक्ति स्पष्ट रूप से एक सीमित कथन द्वारा वस्तुओं के अनंत सेट को परिभाषित करने की संभावना में निहित है। उसी तरह, एक सीमित रिकर्सन प्रोग्राम द्वारा अनंत संख्या में संगणनाओं का वर्णन किया जा सकता है, तथापि इस प्रोग्राम में कोई स्पष्ट रिकर्सन न हो।

— निक्लॉस विर्थ, Algorithms + Data Structures = Programs, 1976

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

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

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

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

बेस केस

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

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

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

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

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

Further information: बीजगणितीय डेटा प्रकार

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

Main article: रिकर्सिव डेटा प्रकार

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

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]

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

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

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

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

{{quote|text=Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it.  [[How to Design Programs|''HtDP'' (''How to Design Programs'')]] refers to this kind as generative recursion.  Examples of generative recursion include: [[Euclidean algorithm|gcd]], [[quicksort]], [[binary search]], [[mergesort]], [[Newton's method]], [[fractal]]s, and [[adaptive quadrature|adaptive integration]].|author=Matthias Felleisen|source=''Advanced Functional Programming'', 2002<ref name="Felleisen 2002 108">{{Cite book
  | last = Felleisen
  | first = Matthias
  | chapter = Developing Interactive Web Programs |chapter-url=https://books.google.com/books?id=Y3GqCAAAQBAJ&pg=PA108
  | date = 2002
  | title = Advanced Functional Programming: 4th International School
  | editor-last = Jeuring
  | editor-first = Johan
  | page = 108
  | publisher = Springer
  | isbn = 9783540448334
  | url = ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/Advanced%20Functional%20Programming%204%20conf.,%20AFP%202002%20(LNCS2638,%20Springer,%202003)(ISBN%203540401326)(O)(222s).pdf#page=109 	
}}
</ref>

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

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

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

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

=== [[आवरण समारोह]] ===
एक रैपर फ़ंक्शन एक ऐसा फ़ंक्शन होता है जिसे सीधे कहा जाता है लेकिन खुद को दोबारा नहीं करता है, बल्कि एक अलग सहायक फ़ंक्शन को कॉल करता है जो वास्तव में रिकर्सन करता है।                                                                                   

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

=== बेस केस को शॉर्ट-सर्किट करना ===                                                                                                                                                                      
{{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;
}

| VALIGN=TOP |

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 के लिए 1 लौटा रहा है! शॉर्ट सर्किट है, और 0 मिस हो सकता है; इसे रैपर फ़ंक्शन द्वारा कम किया जा सकता है। बॉक्स सी (प्रोग्रामिंग भाषा) कोड को शार्टकट फैक्टोरियल केस 0 और 1 के लिए दिखाता है।

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

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

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

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

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

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

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

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

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

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

सी में, मानक रिकर्सन एल्गोरिथ्म को इस प्रकार प्रयुक्त किया जा सकता है: <वाक्यविन्यास लैंग = सी> बूल ट्री_कंटेन्स (स्ट्रक्चर नोड * ट्री_नोड, इंट आई) {

 अगर (tree_node == न्यूल)
 विवरण झूठा है; // मुख्य स्थिति
 और अगर (tree_node-> डेटा == i)
 वापसी सच;
 वरना
 रिटर्न ट्री_कंटेन्स (ट्री_नोड-> लेफ्ट, आई) ||
 tree_contains(tree_node->right, i);

} </वाक्यविन्यास हाइलाइट>

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

<वाक्यविन्यास लैंग = सी> // रिक्त पेड़ को संभालने के लिए रैपर फ़ंक्शन बूल ट्री_कंटेन्स (स्ट्रक्चर नोड * ट्री_नोड, इंट आई) {

 अगर (tree_node == न्यूल)
 विवरण झूठा है; // रिक्त पेड़
 वरना
 वापसी tree_contains_do (tree_node, i); // सहायक फ़ंक्शन को कॉल करें

}

// मानता है tree_node != NULL बूल ट्री_कंटेन्स_डो (स्ट्रक्चर नोड * ट्री_नोड, इंट आई) {

 अगर (tree_node-> डेटा == i)
 वापसी सच; // मिल गया
 और // रिकर्स
 रिटर्न (ट्री_नोड-> लेफ्ट एंड& ट्री_कंटेन्स_डो (ट्री_नोड-> लेफ्ट, आई)) ||
 (ट्री_नोड-> राइट एंड& ट्री_कंटेन्स_डो (ट्री_नोड-> राइट, आई));

} </वाक्यविन्यास हाइलाइट>

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

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

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

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

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

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

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

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

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

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

<वाक्यविन्यास लैंग = सी> अहस्ताक्षरित इंट फैक्टोरियल (अहस्ताक्षरित इंट एन) {

 अहस्ताक्षरित इंट उत्पाद = 1; // रिक्त उत्पाद 1 है
 जबकि (एन) {
 उत्पाद * = एन;
 --एन;
 }
 वापसी उत्पाद;

} </वाक्यविन्यास हाइलाइट>

अभिव्यंजक शक्ति

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

प्रदर्शन मुद्दे

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

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

स्टैक स्पेस

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

अंतर्यता

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

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

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

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

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

पूंछ-रिकर्सन कार्य

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

Tail recursion:	Augmenting recursion:
//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

<वाक्यविन्यास प्रकाश लैंग = सी> शून्य रिकर्सन समारोह (पूर्णांक संख्या) {

 प्रिंटफ (% डी \ n, संख्या);
 अगर (संख्या <4)
 रिकर्सिवफंक्शन (संख्या + 1);

} </वाक्यविन्यास हाइलाइट>

समारोह 2

<वाक्यविन्यास प्रकाश लैंग = सी> शून्य रिकर्सन समारोह (पूर्णांक संख्या) {

 अगर (संख्या <4)
 रिकर्सिवफंक्शन (संख्या + 1);
 प्रिंटफ (% डी \ n, संख्या);

} </वाक्यविन्यास हाइलाइट>

फंक्शन 2 फंक्शन 1 है जिसमें लाइनों की अदला-बदली की जाती है।

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

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

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

फैक्टोरियल

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

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

Pseudocode (recursive):
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$

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

Computing the recurrence relation for n = 4:
b4 = 4 × b3 = 4 × (3 × b2) = 4 × (3 × (2 × b1)) = 4 × (3 × (2 × (1 × b0))) = 4 × (3 × (2 × (1 × 1))) = 4 × (3 × (2 × 1)) = 4 × (3 × 2) = 4 × 6 = 24

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

Pseudocode (iterative):
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}}$

Pseudocode (recursive):
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$

Computing the recurrence relation for x = 27 and y = 9:
gcd(27, 9) = gcd(9, 27 % 9) = gcd(9, 0) = 9
Computing the recurrence relation for x = 111 and 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 में बनाए रखने और लूपिंग निर्माण का उपयोग करके, कार्यक्रम रिकर्सन कॉल करने और कॉल स्टैक को बढ़ाने से बचता है।

Pseudocode (iterative):
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

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

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

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

Main article: Towers of Hanoi

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

कार्य परिभाषा:

$\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$

Computing the recurrence relation for 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

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

Pseudocode (recursive):
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

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

An explicit formula for Towers of Hanoi:
h1 = 1 = 21 - 1 h2 = 3 = 22 - 1 h3 = 7 = 23 - 1 h4 = 15 = 24 - 1 h5 = 31 = 25 - 1 h6 = 63 = 26 - 1 h7 = 127 = 27 - 1 In general: hn = 2n - 1, for all n >= 1

बाइनरी खोज

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

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

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

<वाक्यविन्यास लैंग = सी>

/*
 उचित प्रारंभिक स्थितियों के साथ बाइनरी_सर्च को कॉल करें।

 इनपुट:
 डेटा आरोही क्रम में क्रमबद्ध पूर्णांकों की सरणी है,
 toFind खोजने के लिए पूर्णांक है,
 गिनती सरणी में तत्वों की कुल संख्या है

 आउटपुट:
 बाइनरी_सर्च का परिणाम

*/
int search (int *data, int toFind, int count)
{
 // प्रारंभ = 0 (प्रारंभिक सूचकांक)
 // अंत = गिनती - 1 (शीर्ष सूचकांक)
 बाइनरी_सर्च लौटें (डेटा, टूफाइंड, 0, काउंट -1);
}

/*
 बाइनरी सर्च एल्गोरिथम।

 इनपुट:
 डेटा आरोही क्रम में क्रमबद्ध पूर्णांकों की सरणी है,
 toFind खोजने के लिए पूर्णांक है,
 प्रारंभ न्यूनतम सरणी अनुक्रमणिका है,
 अंत अधिकतम सरणी सूचकांक है
 आउटपुट:
 सरणी डेटा के अन्दर खोजने के लिए पूर्णांक की स्थिति,
 -1 अगर नहीं मिला
*/
इंट बाइनरी_सर्च (इंट * डेटा, इंट टूफाइंड, इंट स्टार्ट, इंट एंड)
{
 // मध्य बिंदु प्राप्त करें।
 int मध्य = प्रारंभ + (अंत - प्रारंभ)/2; // पूर्णांक विभाजन

 अगर (शुरू> अंत) // स्टॉप कंडीशन (बेस केस)
 वापसी -1;
 और अगर (डेटा [मध्य] == toFind) // मिला, वापसी index
 मध्य वापसी;
 और अगर (डेटा [मिड]> टूफाइंड) // डेटा टूफाइंड से अधिक है, तो आधा खोजें
 बाइनरी_सर्च लौटें (डेटा, टूफाइंड, स्टार्ट, मिड -1);
 और // डेटा खोजने से कम है, ऊपरी आधा खोजें
 बाइनरी_सर्च लौटें (डेटा, खोजने के लिए, मध्य + 1, अंत);
}

</वाक्यविन्यास हाइलाइट>

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

Main article: Recursive data type

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

<ब्लॉककोट>

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

</ब्लॉककोट>

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

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

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

Main article: Linked list

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

<वाक्यविन्यास लैंग = सी> संरचना नोड {

 इंट डेटा; // कुछ पूर्णांक डेटा
 संरचना नोड * अगला; // पॉइंटर किसी अन्य स्ट्रक्चर नोड के लिए

}; </वाक्यविन्यास हाइलाइट>

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

<वाक्यविन्यास लैंग = सी> शून्य सूची_प्रिंट (संरचना नोड * सूची) {

 अगर (सूची! = न्यूल) // बेस केस
 {
 प्रिंटफ (% डी, सूची-> डेटा); // प्रिंट पूर्णांक डेटा स्थान के बाद
 list_print (सूची-> अगला); // अगले नोड पर रिकर्सन कॉल
 }

} </वाक्यविन्यास हाइलाइट>

बाइनरी पेड़

Main article: Binary tree

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

 इंट डेटा; // कुछ पूर्णांक डेटा
 संरचना नोड * बायां; // बाईं सबट्री के लिए सूचक
 संरचना नोड * सही; // दाएँ सबट्री की ओर इशारा करें

}; </वाक्यविन्यास हाइलाइट>

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

<वाक्यविन्यास लैंग = सी> // परीक्षण करें कि क्या tree_node में i है; यदि हां, तो 1 लौटाएं, यदि नहीं तो 0। int tree_contains (संरचना नोड * tree_node, int i) {

 अगर (tree_node == न्यूल)
 वापसी 0; // मुख्य स्थिति
 और अगर (tree_node-> डेटा == i)
 वापसी 1;
 वरना
 रिटर्न ट्री_कंटेन्स (ट्री_नोड-> लेफ्ट, आई) || tree_contains(tree_node->right, i);

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

<वाक्यविन्यास प्रकाश लैंग = सी> // इनऑर्डर ट्रैवर्सल: शून्य ट्री_प्रिंट (संरचना नोड * ट्री_नोड) {

 अगर (ट्री_नोड! = न्यूल) {// बेस केस
 ट्री_प्रिंट (ट्री_नोड-> बाएं); // जाना छोड़ दिया
 प्रिंटफ (% डी, ट्री_नोड-> डेटा); // स्थान के बाद पूर्णांक प्रिंट करें
 ट्री_प्रिंट (ट्री_नोड-> राइट); // दायें जाइये
 }

} </वाक्यविन्यास हाइलाइट>

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

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

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

<वाक्यविन्यास लैंग = जावा लाइन = 1> आयात java.io.फ़ाइल;

पब्लिक क्लास फ़ाइल सिस्टम {

सार्वजनिक स्थैतिक शून्य main (String [] args) { पार (); }

/**

• फ़ाइल सिस्टम की जड़ें प्राप्त करें
• रिकर्सन फ़ाइल सिस्टम ट्रैवर्सल के साथ आगे बढ़ता है
• /

निजी स्थिर शून्य ट्रैवर्स () { फ़ाइल [] fs = File.listRoots (); for (int i = 0; i <fs.length; i++) { System.out.println(fs[i]); if (fs[i].isDirectory() && fs[i].canRead()) { आरट्रावर्स (एफएस [i]); } } }

/**

• रिकर्सन रूप से किसी दिए गए निर्देशिका को पार करें
• @पारम एफडी ट्रैवर्सल के शुरुआती बिंदु को इंगित करता है
• /

निजी स्थैतिक शून्य आरट्रावर्स (फ़ाइल एफडी) { फ़ाइल [] fss = fd.listFiles ();

for (int i = 0; i <fss.length; i++) { System.out.println(fss[i]); if (fss[i].isDirectory() && fss[i].canRead()) { आरट्रावर्स (एफएसएस [i]); } } }

} </वाक्यविन्यास हाइलाइट>

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

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

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

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

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

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

Main article: Master theorem (analysis of algorithms)

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

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

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

• यदि $f(n)=O(n^{\log _{b}a-\varepsilon })$ कुछ स्थिरांक के लिए $\varepsilon >0$, तब Failed to parse (Conversion error. Server ("cli") reported: "SyntaxError: Expected "-", "[", "\\", "\\begin", "\\begin{", "]", "^", "_", "{", "}", [ \t\n\r], [%$], [().], [,:;?!'], [/|], [0-9], [><~], [\-+*=], or [a-zA-Z] but "ट" found.in 1:16"): {\displaystyle टी (एन) = \थीटा (एन ^ {\log_b ए})</मठ> * यदि <Math>f(n) = \Theta(n ^ { \log_b a })} , फिर Failed to parse (Conversion error. Server ("cli") reported: "SyntaxError: Expected "-", "[", "\\", "\\begin", "\\begin{", "]", "^", "_", "{", "}", [ \t\n\r], [%$], [().], [,:;?!'], [/|], [0-9], [><~], [\-+*=], or [a-zA-Z] but "ट" found.in 1:16"): {\displaystyle टी (एन) = \ थीटा (एन ^ { \ log_b ए} \ लॉग एन) </ गणित> * यदि <Math>f(n) = \Omega(n ^ { \log_b a + \varepsilon})} कुछ स्थिरांक के लिए $\varepsilon >0$, और यदि $\cdot f(n/b)\leq c\cdot f(n)$ कुछ स्थिरांक के लिए c < 1 और सभी पर्याप्त रूप से बड़े n, फिर <Math>टी (एन) = \ थीटा (एफ (एन)) </ गणित>

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

यह भी देखें

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

इस पेज में लापता आंतरिक लिंक की सूची

• समारोह (कंप्यूटर विज्ञान)
• रिकर्सन
• फ़ंक्शन प्रोग्रामिंग
• संगणनीयता सिद्धांत
• खोज तालिका
• डेमन (कंप्यूटर सॉफ्टवेयर)
• संयोग
• आत्म संदर्भ
• जानकारी
• लिंक्ड सूची
• पूर्णांकों
• स्ट्रीम (कंप्यूटर साइंस)
• अभाज्य सँख्या
• आपसी रिकर्सन
• एनोनिमस रिकर्सन
• एनोनिमस समारोह
• पास-बाय-संदर्भ
• बहाव को काबू करें
• यात्रा
• ढेर (डेटा संरचना)
• उदाहरण (कंप्यूटर विज्ञान)
• क्रम पर्यावरण
• घुमाव के दौरान
• पायथन (प्रोग्रामिंग भाषा)
• परिमाणक्रम
• फ़ंक्शन भाषाएँ
• एक्सेप्शन हेंडलिंग
• मिलान वाइल्डकार्ड
• रूपरेखा (कंप्यूटर प्रोग्रामिंग)
• सॉफ़्टवेयर परीक्षण
• महत्तम सामान्य भाजक
• क्रमबद्ध सरणी
• SQL में श्रेणीबद्ध और रिकर्सन प्रश्न

संदर्भ

• 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.