詳解clojure遞歸（上）
詳解clojure遞歸（下）
遞歸可以說是LISP的靈魂之一，通過遞歸可以簡潔地描述數學公式、函數調用，Clojure是LISP的方言，同樣需要遞歸來扮演重要作用。遞歸的價值在于可以讓你的思維以what的形式思考，而無需考慮how，你寫出來的代碼就是數學公式，就是函數的描述，一切顯得直觀和透明。如果你不習慣遞歸，那只是因為命令式語言的思維根深蒂固，如x=x+1這樣的表達式，從數學的角度來看完全不合法，但是在命令式語言里卻是合法的賦值語句。
遞歸可以分為直接遞歸和間接遞歸，取決于函數是否直接或者間接地調用自身。如果函數的最后一個調用是遞歸調用，那么這樣的遞歸調用稱為尾遞歸，針對此類遞歸調用，編譯器可以作所謂的尾遞歸優化（TCO），因為遞歸調用是最后一個，因此函數的局部變量等沒有必要再保存，本次調用的結果可以完全作為參數傳遞給下一個遞歸調用，清空當前的棧并復用，那么就不需要為遞歸的函數調用保存一長串的棧，因此不會有棧溢出的問題。在Erlang、LISP這樣的FP語言里，都支持TCO，無論是直接遞歸或者間接遞歸。
但是由于JVM自身的限制，Clojure和Scala一樣，僅支持直接的尾遞歸優化，將尾遞歸調用優化成循環語句。例如一個求階乘的例子：
;;第一個版本的階乘函數
(defn fac [n]
(if (= 1 n)
1
(* n (fac (dec n)))))
第一個版本的階乘并非尾遞歸，這是因為最后一個表達式的調用是一個乘法運算，而非(fac (dec n))，因此這個版本的階乘在計算大數的時候會導致棧溢出：
user=> (fac 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
將第一個版本改進一下，為了讓最后一個調用是遞歸調用，那么我們需要將結果作為參數來傳遞，而不是倚靠棧來保存，并且為了維持接口一樣，我們引入了一個內部函數fac0：
;;第二個版本，不是尾遞歸的“尾遞歸”
(defn fac [n]
(defn fac0 [c r]
(if (= 0 c)
r
(fac0 (dec c) (* c r))))
(fac0 n 1))
這個是第二個版本的階乘，通過將結果提取成參數來傳遞，就將fac0函數的遞歸調用修改為尾遞歸的形式，這是個尾遞歸嗎？這在Scala里，在LISP里，這都是尾遞歸，但是Clojure的TCO優化卻是要求使用recur這個特殊形式，而不能直接用函數名作遞歸調用，因此我們這個第二版本在計算大數的時候仍然將棧溢出：
user=> (fac 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
在Clojure里正確地TCO應該是什么樣子的呢？其實只要用recur在最后調用那一下替代fac0即可，這就形成我們第三個版本的階乘：
;;第三個版本，TCO起作用了
(defn fac [n]
(defn fac0 [c r]
(if (= 0 c)
r
(recur (dec c) (* c r))))
(fac0 n 1))
此時你再計算大數就沒有問題了，計算(fac 10000)可以正常運行（結果太長，我就不貼出來了）。recur只能跟函數或者loop結合在一起使用，只有函數和loop會形成遞歸點。我們第三個版本就是利用函數fac0做了尾遞歸調用的優化。
loop跟let相似，只不過loop會在頂層形成一個遞歸點，以便recur重新綁定參數，使用loop改寫階乘函數，這時候就不需要定義內部函數了：
;;利用loop改寫的第四個版本的階乘函數
(defn fac [n]
(loop [n n r 1]
(if (= n 0)
r
(recur (dec n) (* n r)))))
loop初始的時候將n綁定為傳入的參數n（由于作用域不同，同名沒有問題），將r綁定為1，最后recur就可以將新的參數值綁定到loop的參數列表并遞歸調用。
Clojure的TCO是怎么做到的，具體可以看看我前兩天寫的
這篇博客，本質上是在編譯的時候將最后的遞歸調用轉化成一條goto語句跳轉到開始的Label，也就是轉變成了循環調用。
這個階乘函數仍然有優化的空間，可以看到，每次計算其實都有部分是重復計算的，如計算(fac 5)也就是1*2*3*4*5，計算(fac 6)的1*2*3*4*5*6，如果能將前面的計算結果緩存下來，那么計算(fac 6)的時候將更快一些，這可以通過memoize函數來包裝階乘函數：
;;第五個版本的階乘,緩存中間結果
(def fac (memoize fac))
第一次計算(fac 10000)花費的時間長一些，因為還沒有緩存：
user=> (time (fac 10000))
"Elapsed time: 170.489622 msecs"
第二次計算快了非常多（其實沒有計算，只是返回緩存結果）：
user=> (time (fac 10000))
"Elapsed time: 0.058737 msecs"
可以看到，如果沒有預先緩存，利用memoize包裝的階乘函數也是快不了。memoize的問題在于，計算(fac n)路徑上的沒有用到的值都不會緩存，它只緩存最終的結果，因此如果計算n前面的其他沒有計算過的數字，仍然需要重新計算。那么怎么保存路徑上的值呢？這可以將求階乘轉化成另一個等價問題來解決。
我們可以將所有的階乘結果組織成一個無窮集合，求階乘變成從
這個集合里取第n個元素，這是利用Clojure里集合是lazy的特性，集合里的元素如果沒有使用到，那么就不會預先計算，而是等待要用到的時候才計算出來，定義一個階乘結果的無窮集合，可以利用map將fac作用在整數集合上,map、reduce這樣的高階函數返回的是LazySeq：
(def fac-seq (map fac (iterate inc 0)))
(iterate inc 0)定義了正整數集合包括0，0的階乘沒有意義。這個集合的第0項其實是多余的。
查看fac-seq的類型，這是一個LazySeq:
user=> (class fac-seq)
clojure.lang.LazySeq
求n的階乘，等價于從這個集合里取第n個元素：
user=> (nth fac-seq 10)
3628800
這個集合會比較耗內存，因為會緩存所有計算路徑上的獨立的值，哪怕他們暫時不會被用到。但是這種采用LazySeq的方式來定義階乘函數的方式有個優點，那就是在定義fac-seq使用的f
ac函數無需一定是符合TCO的函數，我們的第一個版本的階乘函數稍微修改下也可以使用，并且不會棧溢出：
(defn fac [n]
(if (<= n 1)
1
(* n (fac (dec n)))))
(def fac (memoize fac))
(def fac-seq (map fac (iterate inc 0)))
(nth fac-seq 10000)
因為集合從0開始，因此只是修改了fac的if條件為n<=1的時候返回1。至于為什么這樣就不會棧溢出，有興趣的朋友可以自己思考下。
從這個例子也可以看出，一些無法TCO的遞歸調用可以轉化為LazySeq來處理，這算是彌補JVM缺陷的一個辦法。