recursion - 是否可以在 Lisp 中递归生成 40,000 多个斐波那契元素？

Question

我正在尝试用 Lisp解决Project Euler 问题 2 。这种递归解决方案在执行时会破坏堆栈，但我认为 Lisp（使用 clisp）会识别尾递归。这正在进入顶层。

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"

   (if (> f2 4000000) sum)
   (e2-problem f2 (+ f1 f2) (if (evenp f2) 
                                (+ sum f2) 
                               sum))

我的实现是否没有正确安排优化？我想如果我不能依赖惯用的递归，这会极大地阻碍我的 Lisp 教育。

Answer 1

不需要递归（甚至迭代）！

每三个斐波那契数是偶数：

1 1 2 3 5 8 13 21 34 55 89 144 ...

并且由于每个偶数斐波那契数（粗体）是前面两个奇数斐波那契数的总和，所以直到 F n 的偶数斐波那契数之和正好是直到 F _n的所有_斐波那契数之和的一半（如果 F _n是偶数，当然）。

现在，前n 个斐波那契数的和是 F _{n +2}  - 1。这很容易通过归纳来检查：前n  + 1 个斐波那契数的总和是 F ₁  + F ₂  + ... + F _n  + F _{n +1}，根据假设等于 F _{n +2}  - 1 + F _{n +1 ，根据斐波那契数的定义，它等于 F n +3}  - 1。

因此，如果您能找到最大的N使得 F _{3 N}  ≤ 4,000,000，那么所要求的总和将为 (F _{3 N +2}  − 1) / 2。

（我会把剩下的细节留给你，但从这里应该很简单。）

Answer 2

我认为 Lisp（使用 clisp）会识别尾递归

对于实现尾调用消除的环境在 Scheme 中是强制性的，但在大多数其他 Lisp 方言中却不是，例如 Common Lisp。

Answer 3

1）纠正代码中的语法错误：

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"
   (if (> f2 4000000) 
       sum   ;; here was a closing bracket 
       (e2-problem f2 (+ f1 f2) (if (evenp f2) 
                                    (+ sum f2) 
                                    sum))))  ;; 2 more brackets here

2）使用SBCL。CLISP 不足以检测尾递归。

3）使用最高可用优化级别：

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"
   (declare (optimize (debug 0)))  ;; optimization
   ... 

Answer 4

您的代码实现了无限循环。它不会终止。

使用循环：

(defun e2-problem-a (n)
  "Sum fibonacci sequence, even terms up to n"
  (loop for f1 = 1 then f2
        and f2 = 1 then (+ f1 f2)
        while (<= f2 n)
        when (evenp f2) sum f2))