Generieren Fibonacci-Serie in Lisp mit Rekursion?

Question

Ich bin ein Neuling in LISP. Ich versuche, eine Funktion in CLISP zu schreiben, um die ersten n Zahlen der Fibonacci-Reihe zu erzeugen.

Das habe ich bisher gemacht.

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

Das Programm druckt die n-te Fibonacci-Serie. Ich versuche, es so zu modifizieren, dass es die Serie drucken würde, und nicht nur den n-ten Begriff.

Ist es möglich, in nur einer einzigen rekursiven Funktion nur die grundlegenden Funktionen zu verwenden?

Answer 1

Ja:

(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) 

Die Logik dahinter ist, dass Sie die beiden vorherigen Zahlen wissen müssen, um die nächste zu erzeugen.

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

Statt nur ein Ergebnis der Rückkehr ich alle a -s akkumulieren bis n Null ist.

EDIT Ohne Reverse es ist ein bisschen mehr ineffizient:

(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

Das Programm druckt die n-te Zahl der Serie Fibonacci.

Dieses Programm druckt nichts. Wenn Sie die Ausgabe sehen, ist es wahrscheinlich, weil Sie es aus dem Read-eval-Drucken-Loop (REPL) aufrufen, die ein Formular liest, wertet es aus, und dann druckt das Ergebnis. ZB könnten Sie tun:

CL-USER> (fibonacci 4) 
2 

Wenn Sie diesen Anruf in etwas anderes eingewickelt, obwohl, werden Sie sehen, dass es den Druck etwas nicht ist:

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

Wie Sie dies geschrieben habe, Es wird schwierig sein, sie so zu modifizieren, dass sie jede einzelne Fibonacci-Nummer nur einmal ausdrucken, da Sie eine Menge redundanter Berechnungen durchführen. Zum Beispiel der Aufruf

(fibonacci (- n 1)) 

wird berechnet (fibonacci (- n 1)), aber so wird der direkte Aufruf von

(fibonacci (- n 2)) 

Das heißt, dass Sie wahrscheinlich die gesamte Sequenz drucken nicht jeden Aufruf fibonacci wollen. Wenn Sie das tun, beachten Sie jedoch, dass (print x) den Wert von x zurückkehrt, so können Sie einfach tun:

(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 

Sie werden einige wiederholt Teile siehe da, da redundante Berechnung gibt.Sie können die Serie wesentlich effizienter berechnen jedoch durch aus den ersten beiden Zahlen beginnen und Zählen:

(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

Eine Möglichkeit, die Grundstruktur Sie wird verwendet, um zu halten eine zusätzliche Markierung zu übergeben auf die Funktion, wenn Sie Druck oder nicht sagt:

ist

(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)))))) 

die Idee, dass, wenn Sie die zwei rekursive Aufrufe nur in der ersten tun überliefern Sie die Flagge über den Druck und die in dem zweiten Aufruf stattdessen tun Sie ju Übergeben Sie NIL, um erneutes Drucken zu vermeiden.