解决斐波纳契的方法

Question

我想尝试学习Lisp,但我很快就放弃了.我想我会再试一次.我正在关注Euler项目的问题2 - 找到所有甚至斐波那契数字低于4百万的总和.

我写了下面的代码,但有各种丑陋.其中最主要的是它太慢了 - 因为它一直在进行天真的递归.

当我用Python编写这个程序时,我按计算建立了一个列表,从不重新计算数字.我知道我可以在这里(不知何故)这样做,但这似乎不是真正的lisp精神,函数式编程.我在#3之后放弃了,当我达到递归深度限制并且不得不重写我的代码以使用循环而不是递归.

所以我想我的问题是:

1. 什么是解决这个问题的'正确,积极的方式'？
2. 你如何协调递归和"只计算一切"的概念与计算一切的实际限制？
3. 除了Little Schemer和Project Euler之外,还有任何关于学习lisp的建议吗？

这是我的代码:

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

Answer 1

http://fare.tunes.org/files/fun/fibonacci.lisp深入探讨了解决斐波纳契问题,逐步改善了实施的时间和记忆性能.

Answer 2

记忆是一种将结果缓存到函数的方法,以避免反复重新计算中间结果.Memoization基本上意味着第一次使用一些args调用函数,计算答案并返回它,并缓存该答案; 对于具有相同args的函数的后续调用,只需返回缓存的值.

在Lisp中,您可以轻松使用高阶函数和宏来透明地记忆函数.Clojure具有memoize标准功能.另请参阅On Lisp的第65页,了解Common Lisp的实现memoize.这是在Clojure中:

(defn fib-naive [i]
  (if (or (= i 1) (= i 2))
    1
    (+ (fib-naive (- i 1)) (fib-naive (- i 2)))))

(def fib-memo
     (memoize (fn [i]
                (if (or (= i 1) (= i 2))
                  1
                  (+ (fib-memo (- i 1)) (fib-memo (- i 2)))))))

user> (time (fib-naive 30))
"Elapsed time: 455.857987 msecs"
832040
user> (time (fib-memo 30))
"Elapsed time: 0.415264 msecs"
832040
user> 

如果在大整数上调用它,仍会导致堆栈溢出.例如,立刻做(fib 10000)会打击堆栈,因为它仍然需要非常深度地递归(一次).但是如果你首先填充缓存,它就不再需要深度递归,这可以避免.简单地这样做(在Clojure中):

(dorun (map fib-memo (range 1 10000)))

这将足以让你(fib 10000)没有问题.

(计算Fibonacci数字的具体主题最近出现在Clojure邮件列表上.那里有一个基于卢卡斯数的解决方案,我一点都不懂,但据说比原始算法快40倍.)

Answer 3

使用尾递归而不是天真的递归.大多数Lisp实现应该执行tailcall-optimization; 没有更多的递归深度限制.

除此之外,尝试根据您可以在这些列表上执行的列表和抽象操作来考虑事物.需要考虑的两个相关操作:

• 过滤
• 折

关于其他Lisp资源:

• Common Lisp- On Lisp
• 方案- 计算机程序的构造和解释

更新:尾递归Scheme fib函数:

(define (fib n)
  (fib-tr n 1 0))

(define (fib-tr n next result)
  (cond ((= n 0) result)
        (else (fib-tr (- n 1) (+ next result) next))))