कोटलिन पुनर्संरचना और पूंछ पुनरावर्ती कार्य (उदाहरण के साथ)

इस लेख में, आप पुनरावर्ती कार्यों को बनाना सीखेंगे; एक फ़ंक्शन जो स्वयं को कॉल करता है। इसके अलावा, आप पूंछ पुनरावर्ती कार्य के बारे में सीखेंगे।

एक फ़ंक्शन जो स्वयं को कॉल करता है, उसे पुनरावर्ती फ़ंक्शन के रूप में जाना जाता है। और, इस तकनीक को रिकर्सन के रूप में जाना जाता है।

एक भौतिक दुनिया का उदाहरण दो समानांतर दर्पणों को एक दूसरे के सामने रखना होगा। उनके बीच की कोई भी वस्तु पुनरावर्ती रूप से परिलक्षित होगी।

प्रोग्रामिंग में रिकर्सन कैसे काम करता है?

 मजेदार मुख्य (args: Array) (… पुनर्खरीद ()…) fun recurse () (… recurse ()…) 

यहां, recurse()फ़ंक्शन को फ़ंक्शन के शरीर से recurse()ही कहा जाता है। यहां बताया गया है कि यह कार्यक्रम कैसे काम करता है:

यहां, पुनरावर्ती कॉल हमेशा के लिए अनंत पुनरावृत्ति का कारण बनता है।

अनंत पुनरावृत्ति से बचने के लिए, यदि … (या समान दृष्टिकोण) का उपयोग किया जा सकता है जहां एक शाखा पुनरावर्ती कॉल करती है और अन्य नहीं करती है।

उदाहरण: पुनरावर्तन का उपयोग करके संख्या का तथ्यात्मक पता लगाएं

 fun main(args: Array) ( val number = 4 val result: Long result = factorial(number) println("Factorial of $number = $result") ) fun factorial(n: Int): Long ( return if (n == 1) n.toLong() else n*factorial(n-1) )

जब आप प्रोग्राम चलाते हैं, तो आउटपुट होगा:

 4 = 24 का गुणनखंड

यह कार्यक्रम कैसे काम करता है?

factorial()फ़ंक्शन के पुनरावर्ती कॉल को निम्न आकृति में समझाया जा सकता है:

इसमें शामिल हैं:

भाज्य (4) // 1 फ़ंक्शन कॉल। तर्क: 4 4 * भाज्य (3) // दूसरा फ़ंक्शन कॉल। तर्क: 3 4 * (3 * भाज्य (2)) // 3 फंक्शन कॉल। तर्क: 2 4 * (3 * (2 * factorial (1))) // 4th फ़ंक्शन कॉल। तर्क: १ ४ * (३ * (२ * १)) २४

कोटलिन टेल रिकर्सियन

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

पूंछ पुनरावृत्ति क्या है?

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

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

पूंछ पुनरावृत्ति के लिए स्थिति

एक पुनरावर्ती कार्य पूंछ पुनरावृत्ति के लिए योग्य है यदि फ़ंक्शन स्वयं को कॉल करता है तो यह अंतिम ऑपरेशन है। उदाहरण के लिए,

उदाहरण 1: पूंछ पुनरावृत्ति के लिए पात्र नहीं है क्योंकि फ़ंक्शन कॉल अपने आप n*factorial(n-1)में अंतिम ऑपरेशन नहीं है।

 मजेदार फैक्टोरियल (n: इंट): लॉन्ग (अगर (n == 1) (रिटर्न एन। लिटलॉन्ग ()) और (रिटर्न एन * फैक्टोरियल (एन - 1)))

उदाहरण 2: पूंछ पुनरावृत्ति के लिए योग्य है क्योंकि फ़ंक्शन कॉल अपने fibonacci(n-1, a+b, a)आप में अंतिम ऑपरेशन है।

 फन रिटायरमेंट्स (n: इंट, a: लॉन्ग, b: लॉन्ग): लॉन्ग (रिटर्न इफ (n == 0) b अन्यथा रिट्रेसमेंट (n-1, a + b, a)) 

कॉटलिन में पूंछ पुनरावृत्ति करने के लिए संकलक को बताने के लिए, आपको फ़ंक्शन को tailrecसंशोधक के साथ चिह्नित करना होगा ।

उदाहरण: टेल रिसर्शन

 import java.math.BigInteger fun main(args: Array) ( val n = 100 val first = BigInteger("0") val second = BigInteger("1") println(fibonacci(n, first, second)) ) tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger ( return if (n == 0) a else fibonacci(n-1, b, a+b) )

जब आप प्रोग्राम चलाते हैं, तो आउटपुट होगा:

 354224848179261915075

यह कार्यक्रम फिबोनाची श्रृंखला के 100 ^वें कार्यकाल की गणना करता है । चूंकि, आउटपुट एक बहुत बड़ा पूर्णांक हो सकता है, इसलिए हमने जावा मानक पुस्तकालय से बिगइंटर श्रेणी का आयात किया है।

यहां, फ़ंक्शन fibonacci()को tailrecसंशोधक के साथ चिह्नित किया गया है और फ़ंक्शन पूंछ पुनरावर्ती कॉल के लिए योग्य है। इसलिए, संकलक इस मामले में पुनरावृत्ति का अनुकूलन करता है।

यदि आप पूंछ पुनरावृत्ति का उपयोग किए बिना फाइबोनैचि श्रृंखला के 20000 ^वें कार्यकाल (या किसी अन्य बड़े पूर्णांक) को खोजने का प्रयास करते हैं , तो कंपाइलर java.lang.StackOverflowErrorअपवाद को फेंक देगा । हालाँकि, ऊपर दिया गया हमारा कार्यक्रम ठीक काम करता है। ऐसा इसलिए है क्योंकि हमने पूंछ पुनरावृत्ति का उपयोग किया है जो पारंपरिक पुनरावृत्ति के बजाय कुशल लूप आधारित संस्करण का उपयोग करता है।

उदाहरण: पूंछ पुनर्संरचना का उपयोग करने वाला तथ्य

उपरोक्त उदाहरण में एक संख्या के भाज्य की गणना करने के लिए उदाहरण (पहला उदाहरण) पूंछ पुनरावृत्ति के लिए अनुकूलित नहीं किया जा सकता है। यहां एक ही कार्य करने के लिए एक अलग कार्यक्रम है।

 fun main(args: Array) ( val number = 5 println("Factorial of $number = $(factorial(number))") ) tailrec fun factorial(n: Int, run: Int = 1): Long ( return if (n == 1) run.toLong() else factorial(n-1, run*n) ) 

जब आप प्रोग्राम चलाते हैं, तो आउटपुट होगा:

 5 = 120 का गुणनखंड

कंपाइलर इस कार्यक्रम में पुनरावृत्ति का अनुकूलन कर सकता है क्योंकि पुनरावर्ती कार्य पूंछ पुनरावृत्ति के लिए पात्र है, और हमने tailrecसंशोधक का उपयोग किया है जो पुनरावर्तन का अनुकूलन करने के लिए संकलक को बताता है।