recursion - 使用递归创建 clojure 添加函数

Question

我正试图用 clojure 来解决递归问题。我收到以下代码的堆栈溢出错误，有人能发现问题吗？

（我知道这是低效的，但它严格用于学习目的）

user=> (defn addall
         ([] 0)
         ([& x]
           (if (empty? x) 0)
           (+ (first x) (addall (rest x)))))
user/addall
user=> (addall 1)
StackOverflowError   clojure.lang.ArraySeq.next (ArraySeq.java:78)

Answer 1

看起来你的括号是错误的——你if需要一个else表格。我怀疑你的意思是这样的：

(defn addall
  ([] 0)
  ([& x]
     (if (empty? x) 
         0   ;;; <=== no ')' after 0
         (+ (first x) (addall (rest x))))))  ;;; <== extra ')' here

但是即使修复了这个问题，您的代码仍然是错误的：它假定使用多个参数调用它(addall 1 2 3)-- 但通过向自身传递一个列表来重复 -- (addall [2 3])。这会导致它陷入没有取得任何进展的循环中，您可以通过添加print语句来观察：

(defn addall
  ([] 0)
  ([& x]
     (print (str "new x: " x "\n"))
     (if (empty? x) 
         0   ;;; <=== no ')' after 0
         (+ (first x) (addall (rest x))))))

这实际上在我的计算机上产生了段错误！

此外，它有两个基本情况。我建议这样做：

(defn addall
  [xs]
  (if (empty? xs) 
      0
      (+ (first xs) 
         (addall (rest xs)))))

用向量调用：

(addall [1 2 3])

或者，如果您想使用可变参数函数，您还需要apply：

(defn addall
  [& x]
  (print (str "new x: " x "\n"))
  (if (empty? x) 
      0
      (+ (first x) 
         (apply addall (rest x))))) ;;; <=== apply addall

---

也就是说，您应该注意 Clojure 没有尾调用优化，这意味着此代码在输入中等大小时会失败。Clojure 鼓励使用loop/recur内置的序列处理函数。

Answer 2

我认为这就是你想要的：

(defn addall ([x] (if (empty? x) 0 (+ (first x) (addall (rest x))))))

正如 Matt Fenwick 所提到的，您应该使用循环/递归。更惯用的方法是使用 reduce：

(reduce + [1 2 3 4 5])

clojure 中有很多很棒的工具，而且您通常不需要循环/递归或显式递归之类的东西。