迭代过程与递归过程

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”。

- diplosaurus

---

以前不知道有Distilled版本，谢谢！ - fl00r

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

在第二种情况下，我们说+处于尾部位置，支持此特性的解释器将对其进行优化，详情请参见：尾调用。Clojure 无法进行尾调用优化，除非使用recur。

- Óscar López