Generazione di serie di Fibonacci in Lisp utilizzando la ricorsione?

Question

Sono un principiante in LISP. Sto cercando di scrivere una funzione in CLISP per generare i primi n numeri della serie di Fibonacci.

Questo è quello che ho fatto finora.

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

Il programma stampa l'ennesimo numero di serie Fibonacci. Sto cercando di modificarlo in modo che stampi la serie, e non solo l'ennesima volta.

È possibile farlo in una singola funzione ricorsiva, utilizzando solo le funzioni di base?

Answer 1

Sì:

(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 logica dietro di esso è che è necessario conoscere i due numeri precedenti per generare il successivo.

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

Invece di restituire un solo risultato accumulo tutte le a -s fino n è zero.

EDIT Senza invertire è un po 'più inefficiente:

(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

Il programma stampa il numero n di serie di Fibonacci.

Questo programma non stampa nulla. Se visualizzi l'output, è probabilmente perché lo stai chiamando dalla read-eval-stampa -loop (REPL), che legge un modulo, lo valuta e quindi stampa il risultato. Ad esempio, si potrebbe fare:

CL-USER> (fibonacci 4) 
2 

Se avvolto la chiamata in qualcosa d'altro, però, vedrete che non è nulla di stampa:

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

Come hai questo scritto, sarà difficile modificarlo per stampare ogni numero di fibonacci una sola volta, dato che si esegue un grande calcolo ridondante. Per esempio, la chiamata a

(fibonacci (- n 1)) 

calcolerà (fibonacci (- n 1)), ma così sarà la chiamata diretta al

(fibonacci (- n 2)) 

Questo significa che probabilmente non si vuole ogni chiamata a fibonacci per stampare l'intera sequenza. Se lo fai, però, notare che (print x) restituisce il valore di x, in modo da poter semplicemente fare:

(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 

vedrete alcune parti ripetute lì, perché non c'è calcolo ridondante.È possibile calcolare la serie in modo più efficiente, tuttavia, a partire dai primi due numeri, e contando su:

(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

Un'opzione per mantenere la struttura di base che hai utilizzato è quello di passare una bandiera addizionale alla funzione che indica se si desidera la stampa o no:

(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'idea è che quando si fanno le due chiamate ricorsive solo nella prima si passa la bandiera di fare la stampa e in seconda convocazione, invece si ju passare NIL per evitare di stampare nuovamente.