时间戳

首页 > 解决方案 > Common Lisp 中的递归、推送值和斐波那契数列

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

问题描述

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

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

谢谢你。

标签： recursionlispcommon-lispfibonacciclisp

解决方案

计算斐波那契数的一个明显方法是：

(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))：这是指数（请参阅此堆栈溢出答案）。

一个很好的解决方案是记忆化：(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
[...]

有趣的是 memoization 是由 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声明覆盖（编译器必须知道），那么它必须作为一个完整的调用。从规格：

编译器不能随意忽略这个声明；对指定函数的调用必须作为离线子程序调用来实现。

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

这只是一个问题，因为 CL 编译器可以很聪明：几乎总是这样！

推荐阅读