迭代过程与递归过程

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.除非你使用,否则Clojure不能做尾调用优化recur.