क्लोजर

Question

में रिकूर ​​का उपयोग करते समय ओवरफ़्लो मेरे पास क्लोजर (एक अक्षम एल्गोरिदम) में एक साधारण प्राइम नंबर कैलकुलेटर है, लेकिन मैं अभी रिकर के व्यवहार को समझने की कोशिश कर रहा हूं)। कोड है:

(defn divisible [x,y] (= 0 (mod x y))) 

(defn naive-primes [primes candidates] 
    (if (seq candidates) 
     (recur (conj primes (first candidates)) 
       (remove (fn [x] (divisible x (first candidates))) candidates)) 
     primes) 
) 

यह तब तक काम करता है जब तक मैं बहुत अधिक संख्याओं को खोजने की कोशिश नहीं कर रहा हूं। उदाहरण के लिए

(print (sort (naive-primes [] (range 2 2000)))) 

काम करता है। अधिक रिकर्सन की आवश्यकता के लिए, मुझे एक अतिप्रवाह त्रुटि मिलती है।

(print (sort (naive-primes [] (range 2 20000)))) 

काम नहीं करेगा। आम तौर पर, क्या मैं टीसीओ के प्रयास के बिना दोबारा रिकूर ​​या कॉल बेवकूफ-प्राइम का उपयोग करता हूं, कोई फर्क नहीं पड़ता है। रिकूर ​​का उपयोग करते समय मुझे बड़ी रिकर्सन के लिए त्रुटियां क्यों मिल रही हैं?

Answer 1

recur हमेशा पूंछ रिकर्सन का उपयोग करता है, भले ही आप लूप या फंक्शन हेड के लिए आवर्ती हो रहे हों। मुद्दा remove पर कॉल है। remove अंतर्निहित सीक से तत्व प्राप्त करने के लिए first पर कॉल करता है और यह देखने के लिए जांच करता है कि वह तत्व मान्य है या नहीं। यदि अंतर्निहित सीक remove पर कॉल द्वारा बनाया गया था, तो आपको first पर एक और कॉल मिलती है। यदि आप remove 20000 बार उसी सीक पर कॉल करते हैं, तो first पर कॉल करने के लिए first 20000 बार कॉल करना आवश्यक है, और कोई भी कॉल पूंछ रिकर्सिव नहीं हो सकती है। इसलिए, ढेर अतिप्रवाह त्रुटि।

, (remove ...)(doall (remove ...)) को समस्या ठीक करता है बदलने के बाद से यह remove कॉल की अनंत स्टैकिंग से बचाता है (हर एक पूरी तरह से तुरंत लागू हो जाता है और एक ठोस seq, नहीं एक आलसी seq रिटर्न)। मुझे लगता है कि यह विधि केवल एक उम्मीदवार सूची को स्मृति में रखती है, हालांकि मैं इसके बारे में सकारात्मक नहीं हूं। यदि ऐसा है, तो यह बहुत अधिक अक्षम नहीं है, और कुछ परीक्षण से पता चलता है कि यह वास्तव में बहुत धीमी नहीं है।