迭代过程与递归过程

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))))

其中哪一个是迭代过程（状态完全由迭代函数的参数维护）并且是递归过程（状态必须在“幕后”保留，同时等待先前的函数调用完成。

我的猜测是第二个是迭代的，因为参数可以在参数应用于函数之前进行评估，而前者必须在堆栈上保持连续的函数调用，等待最后一个+操作完成才能解开堆栈，每一步都运行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。除非你使用recur，否则Clojure不能进行尾调用优化。