Generieren von Fibonacci-Reihe in Lisp mit Rekursion?

Ich bin ein Neuling in LISP. Ich bin versucht zu schreiben, eine Funktion in CLISP zu generieren, die die ersten n zahlen der Fibonacci-Reihe.

Dies ist, was ich bisher getan habe.

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

Das Programm druckt die N-te Zahl der Fibonacci-Reihe. Ich versuche es so zu modifizieren, dass er drucken würde, die Serie, und nicht nur die N-te Begriff.

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

InformationsquelleAutor wackyTechie | 2014-04-14

10

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 brauchen, um wissen der beiden vorherigen zahlen, die zum generieren der nächsten.
```
a     0 1 1 2 3 5 ...
b     1 1 2 3 5 8 ...
new-b 1 2 3 5 8 13 ...     
```
Anstatt nur eine Folge, die ich sammeln alle a-s bis n null ist.

BEARBEITEN Ohne umkehren es ist ein wenig 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)
```
- Eigentlich bin ich nicht erlaubt bei reverse-Funktion. Ich habe es in einer einzigen rekursiven Funktion, ohne Verwendung der eingebauten Funktion wie reverse. Trotzdem danke.
- Erwähnen Sie Einschränkungen in Ihrer Frage. Ich habe Hinzugefügt, wie es zu tun, ohne ein Akkumulator.
- Ja, klar, dass es später. Vielen Dank!
InformationsquelleAutor Sylwester
3

Das Programm druckt die N-te Zahl der Fibonacci-Reihe.

Diesem Programm nicht alles drucken. Wenn Sie sehen, Ausgang, ist es wahrscheinlich, weil Sie fordern es von der read-eval-drucken-loop (REPL), das liest sich ein Formular, bewertet es, und dann Drucke das Ergebnis. E. g., Sie möglicherweise tun:
```
CL-USER> (fibonacci 4)
2
```
Wenn Sie eingewickelt, dass call-in etwas anderes, obwohl, werden Sie sehen, dass es nicht den Druck alles:
```
CL-USER> (progn (fibonacci 4) nil)
NIL
```
Als Sie habe dies geschrieben, wird es schwierig sein ihn zu ändern, zu drucken, jede fibonacci-Zahl nur einmal, da Sie eine Menge redundanter Berechnungen. Zum Beispiel, wird der Anruf zu
```
(fibonacci (- n 1))
```
berechnen (fibonacci (- n 1)), aber so wird der direkte Aufruf zu
```
(fibonacci (- n 2))
```
Das bedeutet, dass Sie wahrscheinlich nicht wollen, dass jeder Aufruf fibonacci zum drucken der gesamten Sequenz. Wenn Sie dies tun, aber beachten Sie, dass (print x) gibt den Wert von x, 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
```
Sehen Sie einige wiederholt Teile gibt, da gibt es redundante Berechnung. Sie können berechnen die Serie viel mehr effizient, jedoch, ausgehend von den ersten beiden zahlen und das zählen bis:
```
(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 
```
InformationsquelleAutor Joshua Taylor
2

Ein-option, um die grundlegende Struktur, die verwendet wird, um eine weitere Flagge, um die Funktion, die sagt, wenn Sie möchten, drucken oder nicht:
```
(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 ist, dass wenn du die zwei rekursive Aufrufe nur in den ersten passieren Sie unten die Flagge über das tun der Druck-und in der zweiten rufen Sie stattdessen übergeben Sie NULL, um zu vermeiden, erneut zu drucken.

InformationsquelleAutor 6502

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.