## 遞歸 遞歸發生在一個函數直接或者間接調用自己的時候。一般來說遞歸的退出條件有檢查一個集合是否為空，或者一個狀態變量是否變成了某個特定的值(比如0)。這一種情況一般利用連續調用集合里面的 `next` 函數來實現。后一種情況一般是利用 `dec` 函數來遞減某一個變量來實現。 如果遞歸的層次太深的話，那么可能會產生內存不足的情況。所以一些編程語言利用 “ [tail call optimization](http://en.wikipedia.org/wiki/Tail_call) ” (TCO)的技術來解決這個問題。但是目前Java和Clojure都不支持這個技術。在Clojure里面避免這個問題的一個辦法是使用special form: `loop` 和 `recur` 。另一個方法是使用 [trampoline](http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/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#clojure.core/trampoline)` 函數是支持的。