मुझे एक सामान्य लिस्प फ़ंक्शन के प्रदर्शन को समझने में समस्या है (मैं अभी भी एक नौसिखिया हूं)। मेरे पास इस फ़ंक्शन के दो संस्करण हैं, जो किसी दिए गए n तक सभी पूर्णांक के योग की गणना करता है।आम लिस्प: मेरी पूंछ-रिकर्सिव फ़ंक्शन क्यों स्टैक ओवरफ़्लो का कारण बनता है?
गैर पूंछ पुनरावर्ती संस्करण:
(defun addup3 (n)
(if (= n 0)
0
(+ n (addup (- n 1)))))
पूंछ पुनरावर्ती संस्करण:
(defun addup2 (n)
(labels ((f (acc k)
(if (= k 0)
acc
(f (+ acc k) (- k 1)))))
(f 0 n)))
मैं इनपुट n = 1000000 साथ CLISP में इन कार्यों को चलाने के लिए कोशिश कर रहा हूँ। यहाँ परिणाम
[2]> (addup3 1000000)
500000500000
[3]> (addup2 1000000)
*** - Program stack overflow. RESET
मैं SBCL में दोनों को सफलतापूर्वक चला सकते है, लेकिन गैर-पूंछ पुनरावर्ती एक तेजी से होता है (केवल एक छोटे से से है, लेकिन यह मेरे लिए अजीब लगता है)। मैंने जवाब के लिए Stackoverflow प्रश्नों को खराब कर दिया है लेकिन कुछ ऐसा नहीं मिला। मुझे स्टैक ओवरफ़्लो क्यों मिलता है हालांकि पूंछ-रिकर्सिव फ़ंक्शन को सभी रिकर्सिव फ़ंक्शन कॉल को स्टैक पर नहीं डालने के लिए डिज़ाइन किया गया है? क्या मुझे पूंछ कॉल को अनुकूलित करने के लिए दुभाषिया/कंपाइलर को बताना है? (मैंने (proclaim '(optimize (debug 1)) जैसे कुछ डीबग स्तर सेट करने और ट्रेसिंग क्षमताओं की लागत पर अनुकूलित करने के लिए कुछ पढ़ा है, लेकिन मुझे नहीं पता कि यह क्या करता है)। शायद उत्तर स्पष्ट है और कोड बकवास है, लेकिन मैं इसे समझ नहीं सकता। सहायता की सराहना की जाती है।
संपादित करें: डैनलेई ने टाइपो को इंगित किया, यह पहले समारोह में addup3 पर कॉल होना चाहिए, इसलिए यह रिकर्सिव है। अगर सही है, दोनों संस्करणों अतिप्रवाह, उसका नहीं बल्कि एक
(defun addup (n)
"Adds up the first N integers"
(do ((i 0 (+ i 1))
(sum 0 (+ sum i)))
((> i n) sum)))
यह यह करने के लिए एक और अधिक विशिष्ट तरीका हो सकता है, मैं इसे अजीब मुझे बताने की यह है की तरह पूंछ प्रत्यावर्तन हमेशा अनुकूल नहीं है, मेरे प्रशिक्षकों यह देखते हुए कि लगता है बहुत अधिक कुशल और सामान।
जैसा कि डैनले द्वारा इंगित किया गया है, पहले फ़ंक्शन में एक टाइपो है, इसे स्वयं कॉल करना चाहिए, न कि 'एडुप', जो अनिवार्य रूप से आपके द्वारा वर्णित कार्य है। यदि मैं टाइपो को सही करता हूं, तो यह भी बहती है। फिर भी, मुझे परेशान है कि 'डू' निर्माण रिकर्सिव एक से अधिक सक्षम है। मुझे clisp.org पर spec goling और ब्राउज़ करते समय सीएलआईएसपी के लिए टीसीओ के बारे में कुछ भी नहीं लगता है। अगर यह सामान्य रिकर्सन की तुलना में पूंछ की पुनरावृत्ति अधिक शक्तिशाली नहीं है तो क्या यह अजीब नहीं होगा? – oarfish
आपको आश्चर्यचकित नहीं होना चाहिए। टेल कॉल ऑप्टिमाइज़ेशन केवल एक रिकर्सिव परिभाषा को निरंतर (स्टैक) स्पेस में चलाता है, ताकि यह एक पुनरावृत्ति परिभाषा के रूप में तेज़ हो सके। इसमें कोई जादू शामिल नहीं है जो इससे तेज हो सकता है। – Svante
बास्की की लिस्प की भूमि में, मैंने अभी पढ़ा है कि वास्तव में सीएलआईएसपी केवल पूंछ कॉल को अनुकूलित करता है, जब कोई फ़ंक्शन संकलित करता है। वास्तव में, पूंछ रिकर्सिव एक थोड़ा तेज है, इसलिए यहां कोई रहस्य नहीं है। – oarfish