प्राइम फैक्टर

Question

के साथ क्लोजर टेल रिकर्सन मैं खुद को क्लोजर सिखाने की कोशिश कर रहा हूं और मैं ऐसा करने के लिए प्राइम फैक्टर काटा और टीडीडी के सिद्धांतों का उपयोग कर रहा हूं।

इस तरह Midje परीक्षण की एक श्रृंखला के माध्यम से:

(fact (primefactors 1) => (list)) 

(fact (primefactors 2) => (list 2)) 

(fact (primefactors 3) => (list 3)) 

(fact (primefactors 4) => (list 2 2)) 

मैं निम्नलिखित समारोह बनाने के लिए कर रहा था:

(defn primefactors 
    ([n] (primefactors n 2)) 
    ([n candidate] 
     (cond (<= n 1) (list) 
       (= 0 (rem n candidate)) (conj (primefactors (/ n candidate)) candidate) 
       :else (primefactors n (inc candidate)) 
     ) 
    ) 
) 

यह अच्छा काम करता है जब तक मैं इसे निम्नलिखित बढ़त मामले परीक्षण फेंक:

(fact (primefactors 1000001) => (list 101 9901)) 

मैं एक स्टैक ओवरफ़्लो त्रुटि के साथ समाप्त होता हूं। मुझे पता है कि मुझे इसे उचित रिकूर ​​लूप में बदलने की ज़रूरत है, लेकिन मेरे द्वारा देखे जाने वाले सभी उदाहरण बहुत सरल हैं और केवल फोकस के रूप में काउंटर या न्यूमेरिकल वैरिएबल को इंगित करते हैं। मैं यह रिकर्सिव कैसे बना सकता हूं?

धन्यवाद!

Answer 1

यहाँ primefactors प्रक्रिया का एक पूंछ पुनरावर्ती कार्यान्वयन है, यह एक ढेर अतिप्रवाह त्रुटि फेंक बिना काम करना चाहिए:

(defn primefactors 
    ([n] 
    (primefactors n 2 '())) 
    ([n candidate acc] 
    (cond (<= n 1) (reverse acc) 
      (zero? (rem n candidate)) (recur (/ n candidate) candidate (cons candidate acc)) 
      :else (recur n (inc candidate) acc)))) 

चाल परिणाम के भंडारण के लिए एक संचायक पैरामीटर का उपयोग कर रहा है। ध्यान दें कि रिकर्सन के अंत में reverse कॉल वैकल्पिक है, जब तक कि आप परवाह नहीं करते हैं कि कारक रिवर्स ऑर्डर में सूचीबद्ध होते हैं या नहीं।

Answer 2

आपका दूसरा रिकर्सिव कॉल पहले से ही पूंछ की स्थिति में है, आप इसे recur से बदल सकते हैं।

(primefactors n (inc candidate)) 

(recur n (inc candidate)) 

किसी भी समारोह अधिभार एक अंतर्निहित loop ब्लॉक खुलता हो जाता है, तो आप मैन्युअल रूप से सम्मिलित करने के लिए की जरूरत नहीं है। इससे कुछ हद तक ढेर की स्थिति में सुधार होना चाहिए, क्योंकि इस शाखा को अधिक सामान्य रूप से लिया जाएगा। के रूप में अपनी परिणाम conj को पारित कर दिया है

पहले प्रत्यावर्तन

(primefactors (/ n candidate)) 

पूंछ स्थिति में नहीं है। इसे पूंछ की स्थिति में रखने के लिए, आपको एक अतिरिक्त संचयक तर्क में प्रमुख कारकों को इकट्ठा करने की आवश्यकता होगी, जिस पर आप conj वर्तमान रिकर्सन स्तर से परिणाम प्राप्त करते हैं और फिर प्रत्येक आमंत्रण पर recur पर जाते हैं। उस जमाकर्ता को वापस करने के लिए आपको अपनी समाप्ति स्थिति समायोजित करने की आवश्यकता होगी।

Answer 3

सामान्य तरीका एक संचयक को फ़ंक्शन तर्कों में से एक के रूप में शामिल करना है। अपने कार्य परिभाषा करने के लिए एक 3-arity संस्करण जोड़ें:

(defn primefactors 
    ([n] (primefactors n 2 '())) 
    ([n candidate acc] 
    ...) 

फिर (conj ...) रूप (recur ...) फोन और (conj acc candidate) तीसरा तर्क के रूप में पारित करने के लिए संशोधित। सुनिश्चित करें कि आप तीनrecur पर तर्क, यानी (recur (/ n candidate) 2 (conj acc candidate)), ताकि आप primefactors के 3-धर्मार्थ संस्करण को कॉल कर रहे हों।

और (<= n 1) मामले को खाली सूची के बजाय acc वापस करने की आवश्यकता है।

यदि आप स्वयं के लिए समाधान नहीं समझ पा रहे हैं तो मैं अधिक जानकारी में जा सकता हूं, लेकिन मैंने सोचा कि मुझे आपको पहले इसे बाहर करने का प्रयास करने का मौका देना चाहिए।

Answer 4

एक पूंछ पुनरावर्ती, संचायक मुक्त, आलसी-अनुक्रम समाधान:

(defn prime-factors [n] 
    (letfn [(step [n div] 
      (when (< 1 n) 
       (let [q (quot n div)] 
       (cond 
        (< q div)   (cons n nil) 
        (zero? (rem n div)) (cons div (lazy-step q div)) 
        :else    (recur n (inc div)))))) 
      (lazy-step [n div] 
      (lazy-seq 
       (step n div)))] 
    (lazy-step n 2))) 

रिकर्सिव lazy-seq में एम्बेडेड कॉल अनुक्रम पर यात्रा से पहले एक संचायक का सहारा के बिना मूल्यांकन नहीं किया जाता, ढेर-अतिप्रवाह के जोखिम को नष्ट ।

Answer 5

यह फ़ंक्शन वास्तव में पूंछ-रिकर्सिव नहीं होना चाहिए: इसे इसके बजाय आलसी अनुक्रम बनाना चाहिए। आखिरकार, यह जानना अच्छा नहीं होगा कि 4611686018427387902 गैर-प्रधान (यह दो से विभाजित है), संख्याओं को कम करने के बिना और यह पता चलता है कि इसका अन्य प्रमुख कारक 2305843009213693951 है?

(defn prime-factors 
    ([n] (prime-factors n 2)) 
    ([n candidate] 
    (cond (<= n 1)() 
      (zero? (rem n candidate)) (cons candidate (lazy-seq (prime-factors (/ n candidate) 
                       candidate))) 
      :else (recur n (inc candidate))))) 

उपरोक्त आपके द्वारा पोस्ट किए गए एल्गोरिदम का एक काफी आकस्मिक अनुवाद है; निश्चित रूप से बेहतर एल्गोरिदम मौजूद हैं, लेकिन यह आपको शुद्धता और आलस्य प्राप्त करता है, और ढेर अतिप्रवाह को ठीक करता है।