Génération de la suite de Fibonacci en Lisp utilise la récursivité?

Je suis un newbie en LISP. Je suis en train d'écrire une fonction dans CLISP pour générer des n premiers nombres de la suite de Fibonacci.

C'est ce que j'ai fait jusqu'à présent.

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

Le programme imprime le n-ième nombre de Fibonacci de la série. Je suis en train de le modifier pour qu'il affiche la série, et pas seulement le n-ième terme.

Est-il possible de le faire en une seule fonction récursive, en utilisant seulement les fonctions de base?

OriginalL'auteur wackyTechie | 2014-04-14

10

Oui:
```
(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)
```
La logique derrière cela est que vous devez connaître les deux numéros précédents pour générer le prochain.
```
a     0 1 1 2 3 5 ...
b     1 1 2 3 5 8 ...
new-b 1 2 3 5 8 13 ...     
```
Au lieu de revenir à seulement un résultat, je cumuler tous les a-s jusqu'à ce que n est égale à zéro.

MODIFIER Sans inverse c'est un peu plus inefficace:
```
(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)
```
En fait, je ne suis pas autorisé à utiliser la fonction reverse. Je n'ai qu'à le faire en une seule fonction récursive, sans l'aide de tous intégré la fonction inverse. Merci quand même.
Vous devez mentionner les restrictions dans votre question. J'ai ajouté la manière de le faire sans un accumulateur.
Ouais, réalisé plus tard. Merci beaucoup!

OriginalL'auteur Sylwester
3

Le programme imprime le n-ième nombre de Fibonacci de la série.

Ce programme n'a pas d'imprimer quoi que ce soit. Si vous êtes voyant de sortie, c'est probablement parce que vous êtes en l'appelant depuis le read-eval-impression-boucle (REPL), qui se lit d'une forme, évalue, et puis imprime le résultat. E. g., vous pourriez être en train de faire:
```
CL-USER> (fibonacci 4)
2
```
Si vous avez enveloppé cet appel à quelque chose d'autre, mais vous, vous verrez que ce n'est pas l'impression de rien:
```
CL-USER> (progn (fibonacci 4) nil)
NIL
```
Que vous avez écrit, il sera difficile de le modifier pour imprimer un nombre de fibonacci juste une fois, puisque vous faites beaucoup de calcul redondant. Par exemple, l'appel à
```
(fibonacci (- n 1))
```
permettra de calculer (fibonacci (- n 1)), mais ce sera l'appel direct à
```
(fibonacci (- n 2))
```
Cela signifie que vous ne voulez probablement pas à chaque appel fibonacci pour imprimer l'ensemble de la séquence. Si vous le faites, cependant, noter que (print x) renvoie la valeur de x, de sorte que vous pouvez tout simplement faire:
```
(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
```
Vous allez voir quelques répété pièces de il y, car il est redondant de calcul. Vous pouvez calculer la série de manière beaucoup plus efficace, cependant, en commençant par les deux premiers numéros, et en comptant jusqu':
```
(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 
```
OriginalL'auteur Joshua Taylor
2

Une option pour garder la structure de base utilisée est de passer un indicateur supplémentaire de la fonction qui indique si vous souhaitez que l'impression ou non:
```
(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))))))
```
L'idée est que lorsque vous avez les deux appels récursifs que dans le premier vous passe le drapeau à propos de faire de l'impression et dans le deuxième appel à la place que vous venez de passer NÉANT pour éviter d'imprimer à nouveau.

OriginalL'auteur 6502

Vous devez vous connecter pour publier un commentaire.