रिकर्सन का उपयोग करके लिस्प में फाइबोनैकी श्रृंखला उत्पन्न करना?

Question

मैं LISP में नौसिखिया हूं। मैं फाइबोनैकी श्रृंखला की पहली एन संख्या उत्पन्न करने के लिए सीएलआईएसपी में एक समारोह लिखने की कोशिश कर रहा हूं।

यही वह है जो मैंने अभी तक किया है।

(defun fibonacci(n) 
    (cond 
    ((eq n 1) 0) 
    ((eq n 2) 1) 
    ((+ (fibonacci (- n 1)) (fibonacci (- n 2)))))))) 

कार्यक्रम फिबोनाची श्रृंखला की नौवीं संख्या को प्रिंट करता है। मैं इसे संशोधित करने की कोशिश कर रहा हूं ताकि यह श्रृंखला को मुद्रित करे, न केवल एनएच टर्म।

क्या केवल बुनियादी कार्यों का उपयोग करके, केवल एक ही पुनरावर्ती कार्य में ऐसा करना संभव है?

Answer 1

हाँ:

(defun fibonacci (n &optional (a 0) (b 1) (acc())) 
    (if (zerop n) 
     (nreverse acc) 
     (fibonacci (1- n) b (+ a b) (cons a acc)))) 

(fibonacci 5) ; ==> (0 1 1 2 3) 

इसके पीछे तर्क यह है कि आप पिछले दो संख्या पता करने के लिए अगले उत्पन्न करने के लिए की जरूरत है।

a  0 1 1 2 3 5 ... 
b  1 1 2 3 5 8 ... 
new-b 1 2 3 5 8 13 ...  

इसके बजाय सिर्फ एक परिणाम मैं सभी a -s जमा जब तक n शून्य है लौटने का

।

संपादित बिना रिवर्स उसे कुछ अतिरिक्त अक्षम है:

(defun fibonacci (n &optional (a 0) (b 1)) 
    (if (zerop n) 
     nil 
     (cons a (fibonacci (1- n) b (+ a b))))) 

(fibonacci 5) ; ==> (0 1 1 2 3) 

Answer 2

कार्यक्रम फिबोनैकी श्रृंखला के n वें नंबर प्रिंट करता है।

यह प्रोग्राम कुछ भी प्रिंट नहीं करता है। यदि आप आउटपुट देख रहे हैं, तो शायद यह है कि आप इसे रीड-eval- प्रिंट -loop (REPL) से कॉल कर रहे हैं, जो एक फॉर्म पढ़ता है, इसका मूल्यांकन करता है, और फिर प्रिंट परिणाम देता है। उदाहरण के लिए, तुम क्या कर किया जा सकता है:

CL-USER> (fibonacci 4) 
2 

आप कुछ में है कि कॉल लिपटे तो बाकी है, हालांकि, आप देखेंगे कि यह मुद्रण नहीं कर रहा है कुछ भी:

CL-USER> (progn (fibonacci 4) nil) 
NIL 

आप इस प्रश्न के लिखित मिल गया है के रूप में, प्रत्येक फाइबोनैकी संख्या को मुद्रित करने के लिए इसे एक बार संशोधित करना मुश्किल होगा, क्योंकि आप बहुत अनावश्यक गणना करते हैं। उदाहरण के लिए,

(fibonacci (- n 1)) 

करने के लिए कॉल (fibonacci (- n 1)) गणना होगी, लेकिन इतना

(fibonacci (- n 2)) 

के लिए सीधी कॉल इसका मतलब है कि आप शायद fibonacci की प्रत्येक कॉल पूरे अनुक्रम मुद्रित करने के लिए नहीं करना चाहते हैं जाएगा। यदि आप करते हैं, हालांकि, ध्यान दें कि (print x)x का मान देता है, तो आप बस कर सकते हैं:

(defun fibonacci(n) 
    (cond 
    ((eq n 1) 0) 
    ((eq n 2) 1) 
    ((print (+ (fibonacci (- n 1)) (fibonacci (- n 2))))))) 

CL-USER> (progn (fibonacci 6) nil) 

1 
2 
1 
3 
1 
2 
5 
NIL 

आप कुछ दोहराया भागों वहाँ देखेंगे, वहाँ के बाद से अनावश्यक गणना।आप अधिक कुशलता से श्रृंखला गणना कर सकता है, हालांकि, पहले दो नंबर से शुरू, और ऊपर की गणना के द्वारा:

(defun fibonacci (n) 
    (do ((a 1 b) 
     (b 1 (print (+ a b))) 
     (n n (1- n))) 
     ((zerop n) b))) 

CL-USER> (fibonacci 6) 

2 
3 
5 
8 
13 
21 

Answer 3

एक विकल्प बुनियादी संरचना आप इस्तेमाल किया रखने के लिए है एक अतिरिक्त ध्वज पारित करने के लिए समारोह बताता है कि अगर आप चाहते हैं करने के लिए मुद्रण या नहीं:

(defun fibo (n printseq) 
    (cond 
    ((= n 1) (if printseq (print 0) 0)) 
    ((= n 2) (if printseq (print 1) 1)) 
    (T 
    (let ((a (fibo (- n 1) printseq)) 
      (b (fibo (- n 2) NIL))) 
     (if printseq (print (+ a b)) (+ a b)))))) 

विचार है कि जब आप दो पुनरावर्ती कॉल करते ही में पहले आप नीचे झंडा मुद्रण करने के बारे में और इसके बजाय दूसरी कॉल में पास है आप जू दोबारा प्रिंटिंग से बचने के लिए एनआईएल पास करें।