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