Common Lisp 中的递归、推值和斐波那契数列

Question

这不是家庭作业。在以下代码中:

(defparameter nums '())

(defun fib (number)
  (if (< number 2)
      number
    (push (+ (fib (- number 1)) (fib (- number 2))) nums))
  return nums)

(format t "~a " (fib 100))

由于我对 Common Lisp 非常缺乏经验，所以我对函数不返回值的原因感到困惑。我正在尝试打印斐波那契数列的前“n”个值，例如 100。

谢谢。

Answer 1

计算斐波那契数的一个明显方法是这样的:

(defun fib (n)
  (if (< n 2)
      n
    (+ (fib (- n 1)) (fib (- n 2)))))

(defun fibs (n)
  (loop for i from 1 below n
        collect (fib i)))

稍加思考就会告诉您为什么没有像这样的方法可以帮助您计算前 100 个斐波那契数:计算 (fib n) 所花费的时间等于或多于计算 (fib (- n 1)) 所花费的时间加上计算 (fib (- n 2)) 所花费的时间:这是指数级的(请参阅 this stack overflow answer )。

一个很好的解决方案是内存:(fib n) 的计算重复子计算很多次，如果我们能记住我们计算的答案上次我们可以避免再次这样做。

(这个答案的早期版本在这里有一个过于复杂的宏:类似的东西通常可能有用，但在这里不需要。)

这是内存fib的方法:

(defun fib (n)
  (check-type n (integer 0) "natural number")
  (let ((so-far '((2 . 1) (1 . 1) (0 . 0))))
    (labels ((fibber (m)
               (when (> m (car (first so-far)))
                 (push (cons m (+ (fibber (- m 1))
                                  (fibber (- m 2))))
                       so-far))
               (cdr (assoc m so-far))))
      (fibber n))))

这保留了一个表——一个列表——包含到目前为止计算的结果，并使用它来避免重新计算。

使用这个函数的内存版本:

> (time (fib 1000))
Timing the evaluation of (fib 1000)

User time    =        0.000
System time  =        0.000
Elapsed time =        0.000
Allocation   = 101944 bytes
0 Page faults
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

上面的定义为每次调用 fib 使用了一个新的缓存:这很好，因为本地函数 fibber 确实重用了缓存。但是你可以通过将缓存完全放在函数之外来做得更好:

(defmacro define-function (name expression)
  ;; Install EXPRESSION as the function value of NAME, returning NAME
  ;; This is just to avoid having to say `(setf ...)`: it should
  ;; probably do something at compile-time too so the compiler knows
  ;; the function will be defined.
  `(progn
     (setf (fdefinition ',name) ,expression)
     ',name))

(define-function fib
  (let ((so-far '((2 . 1) (1 . 1) (0 . 0))))
    (lambda (n)
      (block fib
        (check-type n (integer 0) "natural number")
        (labels ((fibber (m)
                   (when (> m (car (first so-far)))
                     (push (cons m (+ (fibber (- m 1))
                                      (fibber (- m 2))))
                           so-far))
                   (cdr (assoc m so-far))))
          (fibber n))))))

此版本的 fib 将在调用之间共享其缓存，这意味着它速度更快，分配的内存更少，但线程安全性可能更差:

> (time (fib 1000))
[...]
Allocation   = 96072 bytes
[...]

> (time (fib 1000))
[...]
Allocation   = 0 bytes
[...]

有趣的是，记忆化是由 Donald Michie 发明(或至少命名)的，他致力于打破 Tunny(因此与 Colossus 一起工作)，我也略微了解他:计算的历史仍然很短!

---

请注意，记忆化是您最终可能与编译器进行战斗的时间之一。特别是对于这样的功能:

(defun f (...)
  ...
  ;; no function bindings or notinline declarations of F here
  ...
  (f ...)
  ...)

然后允许编译器(但不是必需的)假定对 f 的明显递归调用是对其正在编译的函数的递归调用，从而避免了很多开销一个完整的函数调用。特别是不需要检索符号 f 的当前函数值:它可以直接调用函数本身。

这意味着尝试编写一个函数，memoize，它可用于 mamoize 现有的递归函数，如 (setf (fdefinition ' f) (memoize #'f)) 可能不起作用:函数 f 仍然直接调用其自身的未内存版本，并且不会注意到 f 的函数值 已更改。

事实上，即使递归在许多情况下是间接的，这也是正确的:允许编译器假设对函数 g 的调用在同一文件中有一个定义是调用文件中定义的版本，并再次避免完整调用的开销。

处理这个问题的方法是添加合适的 notinline 声明:如果一个调用被 notinline 声明覆盖(编译器必须知道)那么它必须作为一个完整的电话。来自 spec :

A compiler is not free to ignore this declaration; calls to the specified functions must be implemented as out-of-line subroutine calls.

这意味着，为了内存函数，您必须为递归调用添加合适的 notinline 声明，这意味着内存要么需要通过宏完成，要么必须依赖用户向要内存的函数添加适当的声明。

这只是一个问题，因为允许 CL 编译器变得聪明:几乎总是好!