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

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

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

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

पुनरावर्ती फ़ंक्शनस और एल्गोरिदम

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

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

पुनरावर्ती डेटा प्रकार

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

पुनरावृत्ति के प्रकार

एकल पुनरावर्तन और एकाधिक पुनरावर्तन

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

अप्रत्यक्ष पुनरावृत्ति

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

अनाम पुनरावृत्ति

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