递归调用导致溢出

Question

我正在尝试解决项目euler第二个问题.为什么下面的代码导致堆栈溢出？我正在使用recur所以它不应该存储堆栈上的所有递归调用.

(defn sum
  [[a b]]
  [b (+ a b)])

(defn fib-r
  ([n] (fib-r n 0 [0 1]))
  ([n s [a b]]
     (if (= n 0)
       s
       (let [[c d] (sum [a b])
             e (if (even? c) c 0)
             f (+ s e)]
         (recur (dec n) f [c d])))))

(fib-r 4000000)

Answer 1

你得到一个整数溢出(而不是堆栈溢出)如果你使用BigInts(BigInt文字以N结尾),那么Clojure将很乐意计算出正确的结果:

(defn fib-r                                                                                          
  ([n] (fib-r n 0N [0N 1N]))                                                                     
  ([n s [a b]]                                                                                     
     (if (= n 0N)                                                                            
       s                                                                            
       (let [[c d] (sum [a b])                                               
             e (if (even? c) c 0N)                               
             f (+ s e)]                             
         (recur (dec n) f [c d])))))
#'autotestbed.core/fib-r                                                                                               
autotestbed.core> (fib-r 40000)
1158997879999727672946417013062336891791160667328280503727448.... big number