代码之家 › 专栏 › 技术社区 › diplosaurus

迭代过程与递归过程

sicp tail-recursion clojure recursion

5

diplosaurus · 技术社区 · 7 年前

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

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

我的猜测之前参数应用于函数,而前者必须使堆栈上的连续函数调用等待最后一次调用 + 操作完成后才可以放卷堆栈,运行 inc 在每一步。

1 回复 | 直到 7 年前

1

13

Óscar López 7 年前

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

(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 .