迭代过程与递归过程

Question

通读 SICP Distilled 并尝试围绕迭代与递归过程思考。给出的例子是：

(defn + [a b]
  (if (= a 0) b (inc (+ (dec a) b))))

(defn + [a b]
  (if (= a 0) b (+ (dec a) (inc b))))

其中哪些是迭代过程（状态完全由迭代函数的参数维护），哪些是递归过程（在等待先前的函数调用完成时必须保留状态 "behind-the-scenes" .

我的猜测这里是第二个是迭代的，因为参数可以在在参数应用于函数之前被评估，而前者必须在堆栈上保持连续的函数调用，等待最后一个 + 操作完成，然后才能展开堆栈，每一步运行 inc。

Answer 1

有一种简单的方法可以区分迭代过程和递归过程，问问自己：在递归调用之后还有什么要做的吗？如果答案是肯定的，那么就是一个递归过程，就是这里发生的事情：

(inc (+ (dec a) b))
  ^
this is invoked after the recursive call

如果答案是否定的，那么这是一个迭代过程，这就是这里发生的事情：

(+ (dec a) (inc b))
 ^
the recursive call is the last thing we do

第二种情况我们说+在尾部位置，支持它的解释器会优化它，见：tail call. Clojure can't do tail call optimisation, unless you use recur.

Iterative process vs a recursive process