解决斐波那契的捷径 [英] The lisp-way to solve Fibonnaci

问题描述

我想尝试学习Lisp，但很快就放弃了.我想我会再试一次.我正在查看项目Euler上的问题2 -求和甚至低于400万的斐波那契数.

I wanted to try and learn Lisp, but I very quickly gave up. I figured I'd try again. I'm looking at Problem 2 on Project Euler - finding the sum of all even Fibonacci numbers under 4 Million.

我写了下面的代码，它很有效，但是很丑陋.其中最主要的事实是它是如此之慢-因为它一直都在进行幼稚的递归.

I wrote the following code which works, but is all kinds of ugly. Chief among them is the fact that it's so slow - because it's doing naive recursion all the time.

当我用Python编写该程序时，我在计算和从未重新计算数字时建立了一个列表.我知道我可以在这里(以某种方式)做到这一点，但这似乎不符合Lisp的函数式编程精神.当我达到递归深度限制时，我在#3之后放弃了，不得不重写我的代码以使用循环而不是递归.

When I wrote this program in Python I built up a list as I calculated and never recalculated numbers. I know I could do that here (somehow) but that doesn't seem to be true to the spirit of lisp, of functional programming. I gave up after #3, when I hit a recursion depth limit and had to rewrite my code to use a loop instead of recursion.

所以我想我的问题是:

1. 解决此问题的正确，狡猾的方法"是什么?
2. 您如何将递归和仅计算所有内容"的概念与计算所有内容的实际限制相协调?
3. 除了小计划者"和欧拉计划"之外，还有其他关于学习口齿不清的建议吗?

这是我的代码:

 (defun fib(i)
   (if (= i 1)                   ;Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2))))))

 (defun solve(i)
   (let ((f (fib i)))            ;Store result in local variable
     (print f)                   ;For debugging
     (if (< 4000000 f)
       0                         ;return
       (if (= 0 (mod f 2))
         (+ f (solve (+ i 1)))   ;add number
         (solve (+ i 1))))))     ;don't

 (print (solve 1))

推荐答案

http://fare.tunes.org/files/fun/fibonacci.lisp 逐步解决了斐波那契问题，逐步改善了实现的时间和内存性能.

http://fare.tunes.org/files/fun/fibonacci.lisp has a walk through of solving fibonacci, gradually improving the time and memory performance of the implementation.

这篇关于解决斐波那契的捷径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！