是否有可能产生 40,000+ Lisp 中递归斐波那契元素？

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_3N ≤ 4,000,000，那么要求的总和将是 ( F_3N+2 − 1) / 2。

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

Answer 2

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< /a>。 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 3

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

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

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))