14 递归

优质

小牛编辑

119浏览

2023-12-01

递归

递归发生在一个函数直接或者间接调用自己的时候。一般来说递归的退出条件有检查一个集合是否为空，或者一个状态变量是否变成了某个特定的值(比如0)。这一种情况一般利用连续调用集合里面的 next 函数来实现。后一种情况一般是利用 dec 函数来递减某一个变量来实现。

如果递归的层次太深的话，那么可能会产生内存不足的情况。所以一些编程语言利用 “ tail call optimization ” (TCO)的技术来解决这个问题。但是目前Java和Clojure都不支持这个技术。在Clojure里面避免这个问题的一个办法是使用special form: loop 和 recur 。另一个方法是使用 trampoline 函数。

loop / recur 组合把一个看似递归的调用变成一个迭代 — 迭代不需要占用栈空间。 loop special form 跟 let special form 类似的地方是它们都会建立一个本地binding，但是同时它也建立一个递归点，而这个递归点就是recur的参数里面的那个函数。 loop 给这些binding一个初始值。对 recur 的调用使得程序的控制权返回给 loop 并且给那些本地binding赋了新的值。给recur传递的参数一定要和loop所创建的binding的个数一样。同样recur只能出现在loop这个special form的最后一行。

(defn factorial-1 [number]
  "computes the factorial of a positive integer
   in a way that doesn't consume stack space"
  (loop [n number factorial 1]
    (if (zero? n)
      factorial
      (recur (dec n) (* factorial n)))))

(println (time (factorial-1 5))) ; -> "Elapsed time: 0.071 msecs"\n120

defn 宏跟 loop special form一样也会建立一个递归点。 recur special form 也可以被用在一个函数的最后一句用来把控制权返回到函数的第一句并以新的参数重新执行。

另外一种实现 factorial 函数的方法是使用 reduce 函数。这个我们在 “集合” 那一节就已经介绍过了。它支持一种更加“函数”的方式来做这个事情。不过不幸的是，在这种情况下，它的效率要低一点。注意一下 range 函数返回一个数字的范围，这个范围包括它的左边界，但是不包括它的右边界。

(defn factorial-2 [number] (reduce * (range 2 (inc number))))

(println (time (factorial-2 5))) ; -> "Elapsed time: 0.335 msecs"\n120

你可以把上面的 reduce 换成 apply, 可以得到同样的结果，但是apply要更慢一点。这也说明了我们要熟悉每个方法的特点的重要性，以在各个场合使用合适的函数。

recur 不支持那种一个函数调用另外一个函数，然后那个函数再回调这个函数的这种递归。但是我们没有提到的 [trampoline](http://clojure.github.com/clojure/clojure.core-api.html) 函数是支持的。