我想尝试学习Lisp，但我很快就放弃了。我想我会再试一次。我正在看Problem 2 on Project Euler - 找到所有甚至斐波那契数字低于4百万的总和。
我写了下面的代码，但有各种丑陋。其中最主要的是它太慢了 - 因为它一直在进行天真的递归。
当我用Python编写这个程序时，我按计算建立了一个列表，从不重新计算数字。我知道我可以在这里（不知何故）这样做，但这似乎不是真正的lisp精神，函数式编程。我在＃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解决了斐波那契的问题，逐步改善了实施的时间和记忆性能。
创建斐波那契数列表的简单有效方法：
(defun fibs (n &optional (a 1) (b 1))
(loop repeat n
collect (shiftf a b (+ a b))))（shiftf）占用任意数量的位置，最后取值。每个地方都设置为下一个变量的值，最后一个变量采用它后面的值。它返回第一个地方的值。换句话说，它将所有值保留为1。
但是，您不需要完整列表（您只需要evens）并且您根本不需要列表（您只需要总和），因此可以直接使用该函数。每三个斐波纳契数都是偶数，所以......
(defun euler-2 (limit &optional (a 1) (b 1))
(loop for x upfrom 1
until (> a limit)
if (zerop (mod x 3))
sum a
do (shiftf a b (+ a b))))(defun fib (x &optional (y 0) (z 1))
(if (< x z)
nil
(append (list z) (fib x z (+ y z)))))
CL-USER> (reduce #'+ (remove-if-not #'evenp (fib 1000000)))
这是一个备忘版本。在这种情况下，由于你必须计算每个斐波那契数，直到你发现超过四百万，所以使用封闭形式的解决方案将没有多大帮助。
这种方法通过let创造了一个词汇环境;在该环境中创建字典fib-table和函数fib-memoed。最终产品是fib-table可以从fib-memoed访问，但没有其他地方。
现在是踢球者：因为我们必须为连续值计算fib，直到满足某些条件，我们才能在fib 1处启动求解器。从这里开始，计算下一个fib数需要最多2个字典查找和一个添加：O(1) BOOM！
;; memoised fib function: make a hash table, then create
;; the fib function in the lexical scope of the hash table
(let ((fib-table (make-hash-table)))
(setf (gethash 0 fib-table) 1)
(setf (gethash 1 fib-table) 1)
(defun fib-memoed (n)
(let ((x (gethash n fib-table)))
(cond ((not (null x))
x)
(t
(let ((y (+ (fib-memoed (- n 1))
(fib-memoed (- n 2)))))
(setf (gethash n fib-table) y)
y))))))
(defun solve ()
(let ((maxval 4000000))
(labels ((aux (i acc)
(let ((x (fib-memoed i)))
(cond ((> x maxval) acc)
((evenp x)
(aux (1+ i) (+ x acc)))
(t (aux (1+ i) acc))))))
(aux 1 0))))
;;;我尝试编写代码作为@PESTO的建议
（defun Fibo-Test（n / one_prior two_prior curr sum i）
（setq i 2）（setq one_prior 1 two_prior 1）
（条件
（（= n 0）（我是0）
（（= n 1）（我是1）
（（= n 2）（我是1）
（T
（while（和（<i n）（<sum（* 4 1e6）））
;;;转换为Real-num
（setq sum（+（float one_prior）（float two_prior）））
（网络和（1+和））
（setq curr sum）（setq one_prior two_prior two_prior curr ）
）;结束了
）;结束标志（T）
）;结束了
（princ（strcat“\ nF（”（itoa i）“）=”（RTOS sum）“。”））
（王子）
）;结束功能Fibo-Test
Memoization是一种将结果缓存到函数的方法，以避免重复计算中间结果。 Memoization基本上意味着第一次使用一些args调用函数，计算答案并返回它，并缓存该答案;对于具有相同args的函数的后续调用，只需返回缓存的值。
在Lisp中，您可以轻松使用高阶函数和宏来透明地记忆函数。 Clojure将memoize作为标准函数。另请参阅On Lisp的第65页，了解memoize的Common Lisp实现。这是在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 mailing list上。那里有一个基于Lucas numbers的解决方案，我一点都不懂，但据说它比天真算法快40倍。）
使用tail recursion而不是天真的递归。大多数Lisp实现应该执行tailcall-optimization;没有更多的递归深度限制。
除此之外，尝试根据您可以在这些列表上执行的列表和抽象操作来考虑事物。需要考虑的两个相关操作：
关于其他Lisp资源：
更新：尾递归方案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))))
(let ((a 1) (b 1))
(flet ((nextfib ()
(prog1 a
(psetf a b b (+ a b)))))
(loop for fib = (nextfib)
while (<= fib 4000000)
when (evenp fib)
sum fib)))
上面定义了一个函数NEXTFIB，它将为每个调用生成下一个斐波纳契数。 LOOP将偶数结果加到4000000的限制。
PROG1返回其第一个子表达式的值。 PSETF将'和'设置为'并行'。
这是一种常见的模式。有一个生成器函数，一个重复调用它，过滤结果并将它们组合起来。
解决这个问题的方法是自下而上地工作，逐个生成每个Fibonnaci项，如果它是偶数则将其加到总和中，并在达到400万阈值时停止。我的LISP生锈了，所以这里是psuedocode：
one_prior = 1
two_prior = 1
curr = 2
sum = 0
while curr < 4000000000
if curr % 2 == 0
sum = sum + curr
two_prior = one_prior
one_prior = curr
curr = one_prior + two_prior
danio的回答将极大地帮助解决性能问题。
这是对你风格的简短评论：
(defun fib(i)
(if (= i 1) ;//Could rewrite this as a case statement
1
(if (= i 2)
1
(+ (fib (- i 1)) (fib (- i 2)))
)
)
)
将嵌套的IF重构为CONE。
不要将括号放在一条线上。
(defun solve(i)
(let ((f (fib i))) ;//Store result in local variable
(print f) ;//For debugging
(if (
使用ZEROP更清晰。
(+ f (solve (+ i 1))) ;//add number
(solve (+ i 1)) ;//Don't
为什么要把这些放进去？分号后跟空格就足够了。
)
)
)
)
(print (solve 1))
你最后的PRINT声明让我有点怀疑。您是从文件还是从REPL运行此程序？如果你做前者那么你应该考虑做后者。如果你做后者，你可以说（解决1）得到结果。
除了所有有用的答案之外，以下公式可以提供更高的效率 - 在O（Log（n））中计算Fn而不是O（2 ^ n）。这必须与memoization相结合，并且是解决问题的坚实基础：
F(2*n) = F(n)^2 + F(n-1)^2
F(2*n + 1) = ( 2*F(n-1) + F(n) ) * F(n)
为了扩展Danio的答案，http://fare.tunes.org/files/fun/fibonacci.lisp上的文章提出了两种使代码运行更快的方法。使用直接递归（尾调用或否）是O（2 ^ n）并且非常慢。困难在于每个值一次又一次地计算。你必须以不同的方式做事。这两项建议是：
(defun bubble-fib (n) (declare (optimize (speed 3) (safety 0) (debug 0))) (check-type n fixnum) (loop repeat n with p = 0 with q = 1 do (psetq p q q (+ p q)) finally (return p)))
我对“lisp精神”的理解是将自己从lisp精神的任何固定的，教条的，困难的想法中分离出来，并使用最能反映解决问题所需计算结构的lisp结构。例如，
(defun euler2 (&optional (n 4000000))
(do ((i 1 j)
(j 2 (+ i j))
(k 0))
((<= n i) k)
(when (evenp i) (incf k i))))
如果你坚持递归，这是另一种方式：
(defun euler2 (&optional (n 4000000))
(labels ((fn (i j k)
(if (<= n i) k (fn j (+ i j) (if (oddp i) k (+ k i))))))
(fn 1 2 0)))