Lucas数与Fib数相似，只是它以2开头而不是1:
2, 1, 3, 4, 7, 11, 18,
我想写一个函数，生成一个卢卡斯级数列表，按递减顺序排列，直到第n个元素。
我写了这个，但我追踪了它，它太慢了，无法实现到我的列表构建功能中。
(defun lucas (n)
(cond
((equal n 0) 2)
((equal n 1) 1)
(t (+ (lucas (- n 1))
(lucas (- n 2))))))
以下是我为列表函数所写的内容。问题是（lucas n）非常慢，而且我不想在已经使用let的情况下调用助手函数。
(defun lucas-list(n)
(cond
((equal n 0) (cons n nil))
(t (let ((n1 (lucas n)) (n2 (lucas(- n 1))))
(cons n1 (lucas-list n2))))))
我正在努力实现的目标：
(lucas-list 3) => '(4 3 1 2))
任何建议/帮助都将不胜感激
斐波那契数的（伪）线性时间算法可以很容易地扩展到Lucas数：
(define (lucas n)
(let loop ((a 2) (b 1) (n n))
(if (= n 0)
a
(loop b (+ a b) (- n 1)))))
这可以映射到整数上以获得所需的结果：
> (map lucas '(0 1 2 3 4 5))
(2 1 3 4 7 11)
> (reverse (map lucas '(0 1 2 3 4 5)))
(11 7 4 3 1 2)
但实际上有一种更快的方法：如果你意识到上面的算法计算Lᵢ₋₁和Lᵢ₋₂在它计算L之前ᵢ,那么将它们保存在列表中应该会节省很多时间。这就给出了：
(define (lucas n)
(let loop ((a 2) (b 1) (n n) (l '()))
(if (= n 0)
l
(loop b (+ a b) (- n 1) (cons a l)))))
行动中：
> (lucas 20)
(9349 5778 3571 2207 1364 843 521 322 199 123 76 47 29 18 11 7 4 3 1 2)
优化fibonacci类型过程的一种优雅方法是使用memoïze函数缓存之前计算的每个结果：
In Racket（使用哈希表；通用，可扩展性很好）
(define (memoize fn)
(let ((cache (make-hash)))
(lambda arg (hash-ref! cache arg (lambda () (apply fn arg))))))
在R6RS方案中（效率较低，通用性较差，但仍非常适合此目的）
(define (memoize proc)
(let ([cache '()])
(lambda (x)
(cond
[(assq x cache) => cdr]
[else (let ([ans (proc x)])
(set! cache (cons (cons x ans) cache))
ans)]))))
应用于lucas过程（这就像Python装饰器一样工作）：
(define lucas
(memoize
(lambda (n)
(cond
((= n 0) 2)
((= n 1) 1)
(else (+ (lucas (- n 1)) (lucas (- n 2))))))))
列表过程利用了使用累加器反转结果的事实，变成了：
(define (lucas-list n)
(let loop ((i 0) (res null))
(if (= i n)
res
(loop (+ i 1) (cons (lucas i) res)))))
测试：
(display (lucas-list 20))
=> {9349 5778 3571 2207 1364 843 521 322 199 123 76 47 29 18 11 7 4 3 1 2}
怎么样：
(defun lucas-list (n)
(if (equal n 0)
'()
(cons (lucas n) (lucas-list (- n 1)))))
(defun lucas-list-decreasing (n &aux (table (make-hash-table)))
(labels ((lucas-int (n)
(or (gethash n table)
(setf (gethash n table)
(cond ((equal n 0) 2)
((equal n 1) 1)
(t (+ (lucas-int (- n 1))
(lucas-int (- n 2)))))))))
(lucas-int n)
(loop for i downfrom (1- n) downto 0
collect (gethash i table))))
或者：
(defun lucas (n &aux (table (make-hash-table)))
(labels ((lucas-int (n)
(or (gethash n table)
(setf (gethash n table)
(cond ((equal n 0) 2)
((equal n 1) 1)
(t (+ (lucas-int (- n 1))
(lucas-int (- n 2)))))))))
(values (lucas-int n)
table)))
(defun lucas-list-decreasing (n)
(multiple-value-bind (value table)
(lucas n)
(declare (ignore value))
(loop for i downfrom (1- n) downto 0
collect (gethash i table))))