是否有可能在Lisp中递归生成40,000+个Fibonacci元素？

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

由于每个偶数Fibonacci数(粗体)是前两个奇数Fibonacci数之和,因此直到F _n的偶数 Fibonacci数的总和恰好是所有 Fibonacci数到F _n之和的一半(如果F _ñ是偶数,当然).

现在,前n个斐波那契数的总和是F _{n +2}  - 1.这很容易通过归纳检查:前n  + 1个斐波那契数的和是F ₁  + F ₂  + ... + F _n  + F _{n +1},通过假设等于F _{n +2}  - 1 + F _{n +1},其 通过Fibonacci数的定义等于F _{n +3} - 1.

所以,如果你能找到的最大的ñ使得F _{3 ñ}  ≤4,000,000那么系统会将此要求将之和(F _{3 ñ +2}  - 1)/ 2.

(我会把剩下的细节留给你,但从这里开始应该很简单.)