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