我正在尝试编写一个程序，根据给定的数字返回 Pell 数字 序列。
例如(pellNumb 6)应该返回一个列表(0 1 2 5 12 29 70)
到目前为止，这是我的代码。 我能够计算数字，但我无法跳过双重递归。
(defun base (n)
(if (= n 0)
0
(if (= n 1)
1)))
(defun pellNumb (n)
(if (or (= n 0) (= n 1))
(base n)
(let ((x (pellNumb (- n 2))))
(setq y (+ (* 2 (pellNumb (- n 1))) x))
(print y))))
(pellNumb 4) 的输出是 2 2 5 12，这是因为我递归到 (pellNumb 2)两次。
有没有办法跳过它，并将这些值存储在列表中？
谢谢!
最佳答案
获取第n个数
是的，有办法 - 使用 multiple values :
(defun pell-numbers (n)
"Return the n-th Pell number, n-1 number is returned as the 2nd value.
See https://oeis.org/A000129, https://en.wikipedia.org/wiki/Pell_number"
(check-type n (integer 0))
(cond ((= n 0) (values 0 0))
((= n 1) (values 1 0))
(t (multiple-value-bind (prev prev-1) (pell-numbers (1- n))
(values (+ (* 2 prev) prev-1)
prev)))))
(pell-numbers 10)
==> 2378 ; 985
这是递归序列的标准技巧，它依赖于几个先前的值，例如 Fibonacci .
性能
请注意，您的双重递归意味着 (pell-numbers n) 具有指数级 (!) 性能(计算需要 O(2^n) 时间)，而我的单一递归是线性的(即 O(n))。
此外，斐波那契数列有一个方便的属性，允许 logarithmic recursive implementation ，即花费 O(log(n)) 时间。
获取列表中直到n的所有数字
如果您需要直到第 n 个的所有数字，您需要一个简单的循环:
(defun pell-numbers-loop (n)
(loop repeat n
for cur = 1 then (+ (* 2 cur) prev)
and prev = 0 then cur
collect cur))
(pell-numbers-loop 10)
==> (1 2 5 12 29 70 169 408 985 2378)
如果你坚持递归:
(defun pell-numbers-recursive (n)
(labels ((pnr (n)
(cond ((= n 0) (list 0))
((= n 1) (list 1 0))
(t (let ((prev (pnr (1- n))))
(cons (+ (* 2 (first prev)) (second prev))
prev))))))
(nreverse (pnr n))))
(pell-numbers-recursive 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)
请注意递归是非尾递归的，因此循环版本可能更有效。
当然，可以生成尾递归版本:
(defun pell-numbers-tail (n)
(labels ((pnt (i prev)
(if (= i 0)
prev ; done
(pnt (1- i)
(cond ((null prev) (list 0)) ; n=0
((null (cdr prev)) (cons 1 prev)) ; n=1
(t
(cons (+ (* 2 (or (first prev) 1))
(or (second prev) 0))
prev)))))))
(nreverse (pnt (1+ n) ()))))
(pell-numbers-tail 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)
关于lisp - 如何在 LISP 中不递归两次，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53195333/