詳解clojure遞歸（上）
詳解clojure遞歸（下）
這篇blog拖到現在才寫，如果再不寫，估計就只有上篇沒有下篇了，趁周末寫一下。
上篇提到了Clojure僅支持有限的TCO，不支持間接的TCO，但是有一類特殊的尾遞歸clojure是支持，這就是相互遞歸。且看一個例子,定義兩個函數用于判斷奇數偶數：
(declare my-odd? my-even?)
(defn my-odd? [n]
(if (= n 0)
false
(my-even? (dec n))))
(defn my-even? [n]
(if (= n 0)
true
(my-odd? (dec n))))
這里使用declare做前向聲明，不然在定義my-odd?的時候my-even?還沒有定義，導致出錯。可以看到，my-odd?調用了my-even?，而my-even?調用了my-odd?，這是一個相互遞歸的定義:如果n為0，那肯定不是奇數，否則就判斷n-1是不是偶數，反之亦然。
這個遞歸定義看起來巧妙，但是剛才已經提到clojure通過recur支持直接的TCO優化，這個相互遞歸在大數計算上會導致堆棧溢出：
user=> (my-odd? 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
user=> (my-even? 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
怎么解決呢？一個辦法是轉化成一個直接遞歸調用，定義一個parity函數，當偶數的時候返回0，當奇數的時候返回1：
(defn parity [n]
(loop [n n par 0]
(if (= n 0)
par
(recur (dec n) (- 1 par)))))
user=> (parity 3)
1
user=> (parity 100)
0
user=> (parity 10000)
0
user=> (parity 10001)
1
parity是直接的尾遞歸，并且使用了recur優化，重新定義my-odd和my-even就很簡單了：
(defn my-even? [n] (= 0 (parity n)))
(defn my-odd? [n] (= 1 (parity n)))
但是這樣的方式終究不是特別優雅，相互遞歸的定義簡潔優雅，有沒有什么辦法保持這個優雅的定義并且避免堆棧溢出呢？答案是trampoline，翻譯過來是彈簧床，查看trampoline函數文檔：
user=> (doc trampoline)
-------------------------
clojure.core/trampoline
([f] [f & args])
trampoline can be used to convert algorithms requiring mutual
recursion without stack consumption. Calls f with supplied args, if
any. If f returns a fn, calls that fn with no arguments, and
continues to repeat, until the return value is not a fn, then
returns that non-fn value. Note that if you want to return a fn as a
final value, you must wrap it in some data structure and unpack it
after trampoline returns.
簡單來說
trampoline接收一個函數做參數并調用，如果結果為函數，那么就遞歸調用函數，如果不是，則返回結果，主要就是為了解決相互遞歸調用堆棧溢出的問題，查看trampoline的定義：
(defn trampoline
([f]
(let [ret (f)]
(if (fn? ret)
(recur ret)
ret)))
看到
trampoline利用recur做了尾遞歸優化，原有的my-odd?和my-even?需要做一個小改動，就可以利用trampoline來做遞歸優化了：
(declare my-odd? my-even?)
(defn my-odd? [n]
(if (= n 0)
false
#(my-even? (dec n))))
(defn my-even? [n]
(if (= n 0)
true
#(my-odd? (dec n))))
唯一的改動就是函數的末尾行前面加了個#，將遞歸調用修改成返回一個匿名函數了，使用
trampoline調用my-even?和my-odd?不會再堆棧溢出了：
user=> (trampoline my-odd? 10000000)
false
user=> (trampoline my-even? 10000)
true
user=> (trampoline my-even? (* 1000 1000))
true
彈簧床這個名稱很形象，一次調用就是落到彈簧床上，如果是函數，反彈回去再來一次，如果不是，本次表演結束。