Tạo chuỗi Fibonacci trong Lisp bằng cách sử dụng đệ quy?

Question

Tôi là người mới trong LISP. Tôi đang cố gắng viết một hàm trong CLISP để tạo ra các số đầu tiên của dãy Fibonacci.

Đây là những gì tôi đã thực hiện cho đến thời điểm này.

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

Chương trình in số thứ n của dãy Fibonacci. Tôi đang cố gắng sửa đổi nó để nó sẽ in series, và không chỉ là thuật ngữ thứ n.

Có thể làm như vậy chỉ trong một hàm đệ quy đơn lẻ, chỉ sử dụng các chức năng cơ bản không?

Answer 1

Có:

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

Logic đằng sau nó là những gì bạn cần phải biết hai con số trước đó để tạo ra tiếp theo.

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

Thay vì trả lại chỉ là một kết quả tôi tích lũy tất cả các a -s đến n là zero.

EDIT Nếu không có đảo ngược đó là một chút hiệu quả hơn: chương trình

(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

Các in số thứ n của Fibonacci loạt.

Chương trình này không in được gì. Nếu bạn đang nhìn thấy đầu ra, có thể là do bạn đang gọi nó từ read-eval- in-vòng lặp (REPL), đọc biểu mẫu, đánh giá nó, và sau đó in kết quả. Ví dụ, bạn có thể thực hiện:

CL-USER> (fibonacci 4) 
2 

Nếu bạn quấn rằng cuộc gọi trong cái gì khác, tuy nhiên, bạn sẽ thấy bất cứ điều gì mà nó không in:

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

Như bạn đã có này bằng văn bản, nó sẽ khó khăn để sửa đổi nó để in mỗi mã số chỉ một lần, kể từ khi bạn làm rất nhiều tính toán dư thừa. Ví dụ, các cuộc gọi đến

(fibonacci (- n 1)) 

sẽ tính (fibonacci (- n 1)), nhưng như vậy sẽ gọi trực tiếp đến

(fibonacci (- n 2)) 

Điều đó có nghĩa bạn có thể không muốn mỗi cuộc gọi đến fibonacci phép in toàn bộ chuỗi. Nếu bạn làm thế, tuy nhiên, lưu ý rằng (print x) trả về giá trị của x, vì vậy bạn chỉ có thể làm:

(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 

Bạn sẽ thấy một số phần lặp đi lặp lại ở đó, kể từ khi có tính toán dự phòng.Bạn có thể tính toán series nhiều hiệu quả hơn, tuy nhiên, bằng cách bắt đầu từ hai chữ số đầu tiên, và đếm lên:

(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

Một lựa chọn để giữ cấu trúc cơ bản mà bạn sử dụng là để vượt qua một lá cờ khác đến chức năng mà nói nếu bạn muốn in ấn hay không:

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

ý tưởng là khi bạn thực hiện hai cuộc gọi đệ quy chỉ trong lần đầu tiên bạn vượt qua xuống cờ về làm việc in ấn và trong các cuộc gọi thứ hai thay vào đó bạn ju st vượt qua NIL để tránh in lại.