पुनरावर्तन और पुनरावर्ती सूत्र को समझना

यात्रा

Iteration एक प्रक्रिया की पुनरावृत्ति है। एक छात्र जो स्कूल जाता है, वह स्नातक होने तक रोज़ स्कूल जाने की प्रक्रिया को दोहराता है। हम उत्पादों को खरीदने के लिए महीने में कम से कम एक या दो बार किराने की दुकान पर जाते हैं। हम हर महीने इस प्रक्रिया को दोहराते हैं। गणित में, एक फाइबोनैचि अनुक्रम कार्य पुनरावृत्ति के गुणों का भी अनुसरण करता है। आइए फिबोनाची अनुक्रम पर विचार करें जहां पहले दो नंबर 0 और 1 हैं, अन्य सभी संख्याएं पिछले दो संख्याओं का योग हैं।

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

Iteration स्टेप्स

फिबोनाची सूत्र के रूप में लिखा जा सकता है,

एफ (एन) = एफ (एन - 1) + एफ (एन - २)
रिट्रेसमेंट (0) = 0
रिट्रेसमेंट (1) = 1
फाइबोनैचि (2) = फाइबोनैचि (1) + फाइबोनैचि (0) = 1 + 0 = 1
रिट्रेसमेंट (3) = रिट्रेसमेंट (2) + रिट्रेसमेंट (1) = 1 + 1 = 2
रिट्रेसमेंट (4) = रिट्रेसमेंट (3) + रिट्रेसमेंट (2) = 2 + 1 = 3
रिट्रेसमेंट (5) = रिट्रेसमेंट (4) + रिट्रेसमेंट (3) = 3 + 2 = 5
रिट्रेसमेंट (6) = रिट्रेसमेंट (5) + रिट्रेसमेंट (4) = 5 + 3 = 8

नीचे दिया गया एल्गोरिथ्म nth फाइबोनैचि संख्या देता है।

प्रत्यावर्तन

हर बार हमें एक नया फाइबोनैचि नंबर (nth नंबर) मिलता है, जो कि nth नंबर वास्तव में (n - 1) वें नंबर पर होता है जब हम अपने अगले nth फाइबोनैचि के रूप में (n + 1) वें फाइबोनैचि पाते हैं। जैसा कि हम ऊपर बताए गए पुनरावृति चरणों को देखते हैं: यदि n = 2 तब
फाइबोनैचि (2) = फाइबोनैचि (2 - 1) + फाइबोनैचि (2 - 2) = फाइबोनैचि (1) + फाइबोनैचि (0) = 1 + 0 = 1

अब, हम रिट्रेसमेंट (3) जनरेट करना चाहते हैं, जो n = 3 है।

फाइबोनैचि (3) = फाइबोनैचि (3 - 1) + फाइबोनैचि (3 - 2) = फाइबोनैचि (2) + फाइबोनैचि (1) = 1 + 1 = 2
इसका मतलब है कि, प्रत्येक बार n वर्तमान के मान को बढ़ाता है (n - 1) th और (n - 2) वें रिट्रेसमेंट भी बढ़ता है। लेकिन प्रत्येक n के लिए (n - 1) वें और (n - 2) वें रिट्रेसमेंट का ट्रैक रखना थका देने वाला है। कैसे एक विधि लिखने के बारे में जो खुद से पुनरावृत्ति के कार्य को दोहराने के लिए कहता है?

एक विधि जिसे स्वयं कॉल किया जाता है उसे पुनरावर्ती विधि के रूप में नामित किया जाता है। एक पुनरावर्ती विधि में एक आधार मामला होना चाहिए जहां कार्यक्रम खुद कॉल करना बंद कर देता है। फिबोनाची श्रृंखला के लिए हमारा आधार मामला रिट्रेसमेंट (0) = 0 और रिट्रेसमेंट (1) = 1. अन्यथा है, फिबोनाची विधि खुद को दो बार कॉल करती है - रिट्रेसमेंट (एन - 1) और रिट्रेसमेंट (एन - 2)। फिर यह उन्हें रिट्रेसमेंट (एन) प्राप्त करने के लिए जोड़ता है। Nth फाइबोनैचि को खोजने के लिए एक पुनरावर्ती विधि निम्नानुसार लिखी जा सकती है -

अगर हम ध्यान से देखें तो रिकर्सन स्टैक की संपत्ति का अनुसरण करता है। यह एक समस्या का हल पाने के लिए छोटे उपप्रकारों को हल करता है। N> 1 के लिए, यह अंतिम लाइन निष्पादित करता है। इसलिए, यदि n = 6, फ़ंक्शन कॉल करता है और रिट्रेसमेंट (6 - 1) और रिट्रेसमेंट (6 - 2) जोड़ता है। रिट्रेसमेंट (6 - 1) या रिट्रेसमेंट (5) कॉल और रिटोग्राफी (5 - 1) और रिट्रेसमेंट (5 - 2) जोड़ता है। यह पुनरावृत्ति तब तक जारी रहती है जब तक कि 6 अपने बेस केस वैल्यू तक नहीं पहुंच जाता है जो कि रिट्रेसमेंट (0) = 0 या रिट्रेसमेंट (1) = 1. बेस केस हिट होने के बाद यह दो बेस वैल्यू को जोड़ता है और तब तक ऊपर जाता है जब तक कि यह वैल्यू की वैल्यू न मिल जाए ( 6)। नीचे पुनरावर्तन का एक पेड़ प्रतिनिधित्व है।

पुनरावर्तन वृक्ष

जैसा कि हम देख सकते हैं कि एक पुनरावृत्ति कितनी शक्तिशाली हो सकती है। कोड की केवल एक पंक्ति ऊपर पेड़ बना रही है (आधार मामलों सहित कोड के ऊपर अंतिम पंक्ति)। रिकर्सियन एक स्टैक रखता है और यह तब तक गहरा जाता है जब तक कि यह बेस केस तक नहीं पहुंच जाता। डायनामिक प्रोग्रामिंग (DP): रिकर्सन को समझना और कोड करना आसान है लेकिन समय और मेमोरी के मामले में महंगा हो सकता है। नीचे दिए गए पुनरावर्ती वृक्ष को देखें। फ़ाइबर (4) से शुरू होने वाली लेफ्ट सबट्री और फ़ाइबर (4) से शुरू होने वाली राइट सबट्री बिल्कुल एक जैसी हैं। वे एक ही परिणाम उत्पन्न करते हैं जो 3 है लेकिन एक ही कार्य को दो बार कर रहे हैं। यदि n एक बड़ी संख्या है (उदाहरण: 500000) तो पुनरावृत्ति एक कार्यक्रम को बहुत धीमा कर सकती है क्योंकि यह एक ही उप कार्य को कई बार कॉल करेगा।

पुनरावर्तन ट्री-सर्किल

इस समस्या से बचने के लिए डायनेमिक प्रोग्रामिंग का उपयोग किया जा सकता है। डायनामिक प्रोग्रामिंग में हम भविष्य में हल किए गए सबटैक का उपयोग उसी प्रकार के भविष्य के कार्य को हल करने के लिए कर सकते हैं। यह मूल समस्या को हल करने के लिए कार्य को कम करने का एक तरीका है। आइए हम एक सरणी फ़ाइबर तैयार करें] जहां हम पहले से हल किए गए सबटस्क समाधानों को संग्रहीत करते हैं। हम पहले से ही जानते हैं कि फ़ाइब [0] = 0 और फ़ाइबर [1] = 1. इन दो मूल्यों को संग्रहीत करते हैं। अब, फ़ाइब [2] का मूल्य क्या है? जैसा कि फ़ाइब [0] = 0 और फ़ाइब [1] = 1 पहले ही संग्रहीत किया जा चुका है, हमें केवल फ़ाइब [2] = फ़ाइब [1] + फ़ाइब [0] कहना है और यह सब है। हम इसी तरह से फ़ाइबर [3], फ़ाइब [4], फ़ाइब [5], ..., फ़ाइब [एन] उत्पन्न कर सकते हैं। पूर्व में हल किए गए सबटैक्सेस को अगले सबटास्क प्राप्त करने के लिए बुलाया जा रहा है जब तक कि मूल कार्य हल नहीं किया जाता है, इस प्रकार निरर्थक गणना कम हो जाती है।