如何编写这个Clojure函数,以便它不会爆炸堆栈？

Question

我是Clojure的新手,我认为到目前为止我编写代码的方法与"Clojure方法"不符.至少,我一直在编写使用大值导致StackOverflow错误的函数.我已经学会了使用recur,这是向前迈出的一大步.但是,如何使像下面这样的函数为2500000这样的值工作？

(defn fib [i]
  (if (>= 2 i)
    1
    (+ (fib (dec i))
       (fib (- i 2)))))

在我看来,这个函数是Fibonacci生成器的"普通"实现.我已经看到其他实现更加优化,但在他们的工作方面不那么明显.即,当你阅读函数定义时,你不会去"哦,斐波那契".

任何指针将不胜感激!

Answer 1

你需要有一个关于你的功能如何工作的心理模型.假设你自己执行你的函数,每次调用使用一张纸.第一个废料,你写(fib 250000),然后你看到"哦,我需要计算(fib 249999),(fib 249998)并最终添加它们",所以你注意到并开始两个新的废料.你不能扔掉第一个,因为当你完成其他计算时,它仍然有你要做的事情.你可以想象这个计算需要很多碎片.

另一种方法不是从顶部开始,而是从底部开始.你怎么用手工做？您将从第一个数字1,1,2,3,5,8 ...开始,然后始终添加最后两个,直到您完成它为止i.您甚至可以在每一步中丢弃除最后两个之外的所有数字,这样您就可以重复使用大多数剪贴画.

(defn fib [i]
  (loop [a 0
         b 1
         n 1]
    (if (>= n i)
        b
        (recur b
               (+ a b)
               (inc n)))))

这也是一个相当明显的实现,但是如何,而不是什么.当你可以简单地写下定义并且它自动转换为有效的计算时,它似乎总是很优雅,但编程就是这种转换.如果某些东西自动转换,那么这个特殊问题已经得到解决(通常以更一般的方式).

思考"我将如何一步一步地在纸上做"通常会导致良好的实施.

Answer 2

以"普通"方式实现的Fibonacci生成器,如序列的定义,将始终打击您的堆栈.两个递归调用都不fib是尾递归的,这样的定义不能被优化.

不幸的是,如果你想编写一个适用于大数字的高效实现,你将不得不接受这样一个事实,即数学符号不能像我们希望的那样干净地转换为代码.

例如,可以在clojure.contrib.lazy-seqs中找到非递归实现.在Haskell wiki上可以找到解决此问题的各种方法.理解函数式编程的基础知识应该不难理解.