आर

Question

में पूंछ रिकर्सन मैं पूंछ रिकर्सन को गलत समझता हूं; to this stackoverflow question आर के अनुसार पूंछ रिकर्सन का समर्थन नहीं करता है।

Iterative संस्करण:

Fibo <- function(n){ 
    a <- 0 
    b <- 1 
    for (i in 1:n){ 
     temp <- b 
     b <- a 
     a <- a + temp 
    } 
    return(a) 
} 

"अनुभवहीन" पुनरावर्ती संस्करण:

FiboRecur <- function(n){ 
    if (n == 0 || n == 1){ 
     return(n) 
    } else { 
     return(FiboRecur(n-1) + FiboRecur(n-2)) 
     } 
} 

और अंत में एक उदाहरण मैंने पाया कि होना चाहिए हालांकि, की अमुक फिबोनैकी संख्या की गणना करने के निम्नलिखित कार्य पर विचार करते हैं पूंछ कॉल रिकर्सिव:

FiboRecurTail <- function(n){ 
    fib_help <- function(a, b, n){ 
     if(n > 0){ 
      return(fib_help(b, a+b, n-1)) 
     } else { 
      return(a) 
     } 
    } 
    return(fib_help(0, 1, n)) 
} 

अब अगर हम ट्रेस पर नज़र डालें

Fibo(25) 
trace: Fibo(25) 
[1] 75025 


trace(FiboRecur) 
FiboRecur(25) 
Thousands of calls to FiboRecur and takes a lot of time to run 

FiboRecurTail(25) 
trace: FiboRecurTail(25) 
[1] 75025 

Fibo(25) और FiboRecurTail(25) के मामलों में, इस सवाल का जवाब तुरंत प्रदर्शित किया जाता है और केवल एक कॉल किया जाता है: रों जब इन कार्यों कहा जाता है, यहाँ हम क्या मिलता है। FiboRecur(25) के लिए, हजारों कॉल किए गए हैं और परिणाम दिखाने से पहले कुछ सेकंड तक चलते हैं।

हम भी पैकेज rbenchmark से benchmark फंक्शन का उपयोग करके रन बार पर एक नज़र ले जा सकते हैं:

benchmark(Fibo(30), FiboRecur(30), FiboRecurTail(30), replications = 5) 
       test replications elapsed relative user.self sys.self user.child sys.child 
1   Fibo(30)   5 0.00  NA  0.000  0   0   0 
2  FiboRecur(30)   5 13.79  NA 13.792  0   0   0 
3 FiboRecurTail(30)   5 0.00  NA  0.000  0   0   0 

तो अगर आर पूंछ प्रत्यावर्तन का समर्थन नहीं करता, क्या FiboRecurTail(25) यह जितनी जल्दी चलाने करता है कि में हो रहा है अनुवांशिक संस्करण के रूप में "बेवकूफ" रिकर्सिव फ़ंक्शन गुड़ की तरह चलता है? क्या यह है कि आर पूंछ रिकर्सन का समर्थन करता है, लेकिन किसी फ़ंक्शन के "बेवकूफ" रिकर्सिव संस्करण को अन्य प्रोग्रामिंग भाषाओं (उदाहरण के लिए हास्केल) की तरह पूंछ-कॉल रिकर्सिव करने के लिए अनुकूलित नहीं करता है? यह मैं इस post in R's mailing list से समझता हूं।

अगर कोई इसमें कुछ प्रकाश डालेगा तो मैं बहुत सराहना करता हूं। धन्यवाद!

Answer 1

अंतर यह है कि प्रत्येक रिकर्सन के लिए, FiboRecur स्वयं को दो बार कॉल करता है। FiboRecurTail के भीतर, fib_help स्वयं केवल एक बार कॉल करता है।

इस प्रकार आपके पास पूर्व के साथ बहुत अधिक फ़ंक्शन कॉल हैं। FiboRecurTail(25) के मामले में आपके पास ~ 25 कॉल की रिकर्सन गहराई है। FiboRecur(25) परिणाम 242,785 फ़ंक्शन कॉल (पहले सहित) में परिणाम।

मैंने किसी भी दिनचर्या का समय नहीं लिया, लेकिन ध्यान दें कि आप दोनों तेज दिनचर्या के लिए 0.00 दिखाते हैं। आपको उच्च इनपुट मान के साथ कुछ अंतर देखना चाहिए, लेकिन ध्यान दें कि FiboFiboRecurTail रिकर्स का पुनरावृत्ति करता है।

Answer 2

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

FiboRecur(4) की एक छोटी सी सारांश: FiboRecur(0) गणना की जाती है दो बार, तीन बार FiboRecur(1) गणना की जाती है, FiboRecur(2) दो बार गणना की जाती है और FiboRecur(3) एक बार की जाती है। पूर्व तीनों को वास्तव में एक बार गणना की जानी चाहिए और कहीं भी संग्रहीत किया जाना चाहिए ताकि जब भी आवश्यकता हो, आप मूल्यों को निकाल सकें। और यही कारण है कि आप इतनी सारी फ़ंक्शन कॉल देखते हैं, भले ही यह बड़ी संख्या न हो।

पूंछ रिकर्सिव संस्करण में, हालांकि, पहले से गणना किए गए मान अगले चरण में a + b पैरामीटर के माध्यम से पारित किए जाते हैं, जो बेकार पुनरावर्ती संस्करण के रूप में अनगिनत दोहराव गणनाओं से बचाता है, और इस प्रकार अधिक कुशल होता है।