使用递归在Lisp中生成Fibonacci系列？

Question

我是LISP的新手.我正在尝试在CLISP中编写一个函数来生成前n个Fibonacci系列.

这就是我到目前为止所做的.

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

该程序打印出第n个Fibonacci系列.我正在尝试修改它以便打印系列,而不仅仅是第n个术语.

是否可以仅使用基本功能在单个递归函数中执行此操作？

Answer 1

是:

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

它背后的逻辑是你需要知道前两个数字才能生成下一个数字.

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

我没有返回一个结果,而是累积所有a-s直到n为零.

编辑没有反向它有点效率低:

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