मेरे सामान्य रिकर्सन और पूंछ रिकर्सन उदाहरण के बीच एक गोल अंतर क्यों है?

Question

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

scala> def fact(n: Int): Double = if(n < 1) 1 else n * fact(n - 1) 
fact: (n: Int)Double 

scala> fact(30) 
res31: Double = 2.6525285981219103E32 

scala> @tailrec def fact(n: Int, acc: Double = 1): Double = if(n < 1) acc else fact(n - 1, n * acc) 
fact: (n: Int, acc: Double)Double 

scala> fact(30) 
res32: Double = 2.652528598121911E32 

बस जिज्ञासा से बाहर, किसी ने मुझे कृपया उसका वर्णन क्यों या जहां गोल हो रहा है। मेरा अनुमान है कि स्कैला कंपाइलर पूंछ रिकर्सिव संस्करण को लूप में अनुवाद करता है, acc पैरामीटर लूप के प्रत्येक पुनरावृत्ति पर असाइन किया जाता है, और छोटी गोलिंग त्रुटि वहां फिसल जाती है।

Answer 1

परिणाम अलग है क्योंकि दोनों संस्करण अलग-अलग क्रम में गुणा करते हैं, इस प्रकार अलग-अलग गोलियां होती हैं।

सामान्य पुनरावर्ती कॉल, एक अभिव्यक्ति n*([n-1]*([n-2]*(...))) की ओर जाता है क्योंकि आप पहली बार इस तथ्य के मूल्य की गणना (n-1) और फिर n के साथ गुणा, जबकि पूंछ पुनरावर्ती एक ((n*[n-1])*[n-2])*... की ओर जाता है क्योंकि आप पहले n से गुणा करें और फिर एन -1 पर फिर से शुरू करें।

संस्करणों में से एक को फिर से लिखने का प्रयास करें ताकि यह दूसरी तरफ पुनरावृत्त हो और आपको सैद्धांतिक रूप से वही उत्तर मिल सके।

Answer 2

आपके दो कार्य एक ही क्रम में संचालन नहीं कर रहे हैं।

सी में:

int main(int c, char **v) 
{ 
    printf ("%.16e %.16e\n", 
     30.*29*28*27*26*25*24*23*22*21*20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2, 
     2.*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26*27*28*29*30); 
} 

प्रिंट:

2.6525285981219110e+32 2.6525285981219103e+32 

अपने समारोह के

एक संस्करण की गणना करता है 30.*29*... (मैं एक मंच सी में फ्लोटिंग प्वाइंट जाहिर काम करता है जिस पर प्रयोग किया जाता है) और अन्य 2.*3*... की गणना करता है। इन दो परिणामों के लिए थोड़ा अलग होना सामान्य है: फ़्लोटिंग-पॉइंट ऑपरेशंस सहयोगी नहीं हैं। लेकिन कृपया ध्यान दें कि परिणामों के बारे में कुछ भी अचूक नहीं है। आपके कार्यों में से एक बिल्कुल आईईईई 754 डबल-परिशुद्धता अभिव्यक्ति 30.*29*... और अन्य गणना बिल्कुल2.*3*... की गणना करता है। वे दोनों डिजाइन के रूप में काम करते हैं।

अगर मुझे लगता है कि मुझे लगता है कि 2.*3*... अधिक सटीक (असली संख्याओं के साथ प्राप्त परिणाम के करीब) है, लेकिन इससे कोई फर्क नहीं पड़ता: दोनों संख्याएं बहुत नजदीक हैं और असली परिणाम के बहुत करीब हैं।

Answer 3

अंतर इस तथ्य के बारे में नहीं है कि स्कैला पूंछ की पुनरावृत्ति को लूप में बदल देती है। परिणाम उस अनुकूलन के बिना समान होगा। लूप की तुलना में गोल करने वाली त्रुटियों के संबंध में भी रिकर्सन अलग-अलग कार्य नहीं करता है।

अंतर वह क्रम है जिसमें संख्या गुणा हो जाती है। संख्याओं को गुणा करने से पहले आपका पहला समाधान 1 तक सभी तरह से नीचे आता है। तो यह n * ((n - 1) * (... * (2 * 1))) की गणना समाप्त हो जाएगा। पूंछ रिकर्सिव संस्करण तुरंत गुणा शुरू होता है, इसलिए यह n * (n-1) * ... * 2 * 1 की गणना समाप्त होता है।

बेशक, हम कहेंगे कि वे दोनों समान हैं क्योंकि गुणात्मक सहयोगी है, लेकिन यह अस्थायी बिंदु अंकगणित के लिए सच नहीं है। फ़्लोटिंग पॉइंट्स (x * y) * z का उपयोग x * (y * z) से बहुत अलग हो सकता है क्योंकि गोलाकार त्रुटियां अलग-अलग प्रचार करती हैं। तो यह आपके व्यवहार को बताता है।

ध्यान दें कि फोरमोरियल को लागू करने के लिए एन से 1 तक की गणना करने वाले एक फॉर-लूप का उपयोग करते समय आप एक ही अंतर देखेंगे।