Clojure 零基礎 學習筆記 遞歸 尾遞歸
遞歸，或者說函數(shù)的遞歸，在程序設計語言里指的是函數(shù)內部又調用函數(shù)本身的用法。
一個經典的例子就是階乘的計算。我們來分析一下，數(shù)學上的階乘是什么意思呢？簡單來說，N 的階乘就等于 1 * 2 * 3 ... * N 的值。如果不使用遞歸，我們可以先搞一個從 1 到 N 的數(shù)列，然后把它們相乘。
我們可以用 reduce 函數(shù)來實現(xiàn)：
(defn factorial
[number]
(reduce * (range 1 (inc number)))) ;; 注意這里 range 的第二個參數(shù)要加一。
也可以用 apply 函數(shù)實現(xiàn)：
(defn factorial
[number]
(apply * (range 1 (inc number))))
apply 函數(shù)可以把一個序列展開作為某個函數(shù)的參數(shù)：
(apply * [1 2 3])
;; 等價于
(* 1 2 3)
但是，當你試圖計算 100 的階乘的時候，就會出現(xiàn)問題。為什么呢？因為 Clojure 中整數(shù) 字面量[1] 默認為 int 類型，而 100 的階乘已經大于 int 類型所能表達的最大值。為了解決這個問題，Clojure 提供了可以支持無限精度的 “大數(shù)” 字面量。你只需要在整數(shù)字面量后面加上大寫的 N，就可以把它變?yōu)榭芍С?無限范圍[2] 的 “大整數(shù)”。順帶一提，如果在小數(shù)后加上大寫的 M，就可以把它變?yōu)闊o限精度的小數(shù)。大數(shù)類型和普通類型進行運算，結果自動變成大數(shù)類型。
(defn factorial
[number]
(reduce * (range 1N (inc number))))
=> (factorial 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000N
說了半天，還是沒有說到本次的主題。如何使用遞歸來解決階乘的問題呢？首先，我們可以觀察出，N 的階乘其實等于 N-1 的階乘的值 再乘以 N。如果可以得出 N-1 的階乘的值，計算出 N 的階乘就很簡單了。那 N-1 的階乘等于多少呢？它等于 N-2 的階乘 乘以 N-1 …… 不行太繞了。
其實仔細想一下，N-1 的階乘的值，不也是我們這個階乘函數(shù)的 “責任范圍” 么？如果假裝我們的函數(shù)已經做好了，那我們直接調用我們的階乘函數(shù)不就好了？這么神奇么？是的，就是這么神奇。
代碼看起來還是很清晰的：
(defn factorial-recursive
[number]
(* number (factorial-recursive (dec number)))) ;; 假裝能計算 N-1 的階乘
看起來很完美。但是，如果你真的這么做了，分分鐘系統(tǒng)就罷工了??。
為什么呢？其實在函數(shù)里面我們調用自己的時候，相當于又重新執(zhí)行了這個函數(shù)，系統(tǒng)會記下來當前的情況，然后就去新世界冒險了，但是這個新世界函數(shù)里面又調用了新函數(shù)，子子孫孫無窮盡，根本停不下來了。所以到最后系統(tǒng)資源耗盡，就崩潰了。
怎么辦呢？我們要想辦法讓它停下來。怎么停下來呢？我們知道，1 的階乘的值 就是 1，計算到 1 的時候，就可以直接返回 1 這個值了：
(defn factorial-recursive
[number]
(if (= 1 number)
1N
(* number (factorial-recursive (dec number)))))
這樣，當層層調用到 1 的時候，就會停下，然后層層返回，最終得到結果。
所以“遞歸”，最后要“歸”。
我們總結一下寫出一個遞歸的要點：
- 找到函數(shù)內需要執(zhí)行函數(shù)自己的地方
- 找到結束條件，避免無限遞歸
你可能會聽到許多關于遞歸的 “詆毀”，比如遞歸效率極其緩慢，遞歸容易引起堆棧溢出等等。其實他們說的也不算錯，不過，也不算全對。只需要做一點小小的手段，遞歸的速度和空間占用就可以媲美非遞歸形式，有時候甚至比非遞歸形式更快更好！
這種手段叫做尾遞歸優(yōu)化。
什么叫尾遞歸優(yōu)化呢？首先我們要知道什么是尾遞歸。
從字面上看，尾遞歸就是在尾巴處進行遞歸，這個尾巴的意思指的是，函數(shù)的最后一行（也就是函數(shù)返回值的位置）。在最后一行調用自己來遞歸，系統(tǒng)本來是要記錄調用的情況方便調用完畢之后能找到回來的路來執(zhí)行下面的代碼，但是由于我們是在最后一行進行遞歸，下面已經沒有代碼來執(zhí)行了，系統(tǒng)也就不用保存什么記錄了，也就不會占用空間。
但是我們的階乘函數(shù)，最后一行不僅要執(zhí)行遞歸，而且還需要乘上一個數(shù)字，系統(tǒng)不得不保留那個數(shù)字，以便遞歸返回時進行乘法，怎么才能既保留那個數(shù)字，又能讓最后一行只有遞歸調用呢？
答案是：把必要的數(shù)據(jù)保存在參數(shù)中，以參數(shù)的形式傳遞給下一次遞歸。我們來看一下尾遞歸形式的階乘函數(shù)：
(defn factorial-tail-recursive
[number result]
(if (= 1 number)
result
(factorial-recursive (dec number) (* (bigint result) number)))) ;; 使用 bigint 函數(shù)和在整數(shù)字面量后加大寫 N 的效果一樣，可以把一個整型變量變成大整型
=> (factorial-tail-recursive 4 1)
24N
我們來觀察一下，最后一行的確只有遞歸調用了，但是多的這個參數(shù)是什么意思呢？其實它用來保存每一步的結果，這里我們利用了乘法的交換律，以及任一個數(shù)字乘以 1 都等于它本身這兩個性質。使用這個函數(shù)的時候，第二個參數(shù)要為 1。每次遞歸都會把 number 乘上這個數(shù)字，其實相當于倒著乘了一遍。最后遞歸終止的位置，直接返回這個結果就可以了。
這樣是不是就算優(yōu)化完成了？很抱歉還差最后一步。我們要把尾遞歸函數(shù)位置改為 recur，也就是遞歸的英文 recursive 的縮寫。
(defn factorial-tail-recursive
[number result]
(if (= 1 number)
result
(recur (dec number) (* (bigint result) number))))
這樣，一個滿血版本，不會造成堆棧溢出，無限精度的，階乘遞歸函數(shù)就完成了。
為什么要搞一個 recur 出來呢？Clojure 并沒有強制要求 recur 必須放在末尾，如果你把 recur 放在其它地方，它會立即遞歸，而且遞歸完畢之后不會繼續(xù)執(zhí)行下面的代碼。這樣就提供了更多的靈活性。
遞歸在函數(shù)世界里面非常常見，它不僅表達清晰，代碼簡練，而且利用尾遞歸優(yōu)化，可以讓遞歸形式也擁有很高的效率。但尾遞歸要求你能用一個合理的手段把信息以參數(shù)的形式傳遞給下次遞歸，這就增加了編寫遞歸的難度。如果你沒有超凡的智力，也沒有扎實的數(shù)學基礎，那就多看例子，多寫代碼。代碼量提高，才有充足的經驗供你寫出漂亮的遞歸來。
參考博客：
zx-dennis《詳解Clojure的遞歸(上）—— 直接遞歸及優(yōu)化》
zx-dennis《Clojure的recur尾遞歸優(yōu)化探秘》
p.s.: 本文開頭的引用也是一個 “遞歸” 引用。(靈感來自 什么是遞歸？)
