如何理解 Kotlin 的尾遞歸

要理解尾遞歸，首先要理解遞歸。

所謂遞歸函數，就是直接或間接調用了自身的函數；換句話說，就是用自己來定義自己的函數。

一種常用的遞歸函數由兩部分組成：

• 基準情況：對於一組特定的輸入，不需要遞歸就能得到輸出；
• 遞歸過程：對於基準情況之外的輸入，可以通過一種或多種方式遞歸，不斷向基準情況靠攏，最終回歸到基準情況。「遞歸」一詞描述的就是這種方式：如果輸入不是基準情況，就不斷向基準「遞進」，到達基準後再原路返回，「歸納」出最終的結論。

尾遞歸（tail-recursive）函數首先是一個遞歸函數，只多了一個要求：遞歸調用只能是最後一步。如果函數有返回值，要麼返回基準情況的輸出，要麼返回遞歸調用的結果；如果函數沒有返回值，要麼沒有遞歸直接結束，要麼在最後一步遞歸。

加上了這個限制，我們就有了優化尾遞歸的空間。為什麼要優化？因為遞歸調用的代價太大了。

計算機調用一個過程（即函數）需要做的事情有：(1). 保存當前過程的狀態（局部變數和下一條指令地址）；(2). 申請新的棧空間；(3). 傳遞參數；(4). 跳轉到要執行的函數的第一條指令；(5). 執行函數並返回結果；(6). 銷毀分配的棧空間；(7). 恢復寄存器狀態；(8). 跳轉到當前過程的下一條指令；(9). 繼續執行。而遞歸函數具有調用次數多、每次調用計算量比較小的特點，這就讓計算機的大量時間都花費在函數調用上，同時也消耗了大量的棧空間，容易「爆棧」（JVM 平台就是 StackOverflowError）。

尾遞歸的特殊之處在於，調用了遞歸過程之後就直接返回，沒有其他操作，不需要保存狀態，為它分配的棧空間里只剩返回地址還有用，其他信息都等著被銷毀。這時候我們就有了優化的空間，在尾遞歸調用時省略掉上面的 (1)、(2)、(6)、(7)，改 (3) 為更新局部變數，就能改遞歸為迭代，完全消除掉遞歸，即尾遞歸展開，屬於編譯期優化。編譯器可以通過分析控制流知道一個遞歸函數是不是尾遞歸，如果是的話就進行消除。

Kotlin 的尾遞歸設計做得非常好，增加了 tailrec 關鍵字來修飾函數。如果一個函數沒有用 tailrec 修飾，Kotlin 編譯器就不會對它進行尾遞歸優化；如果用了 tailrec，編譯器就會檢查這個函數是不是尾遞歸函數，是的話就進行優化，不是的話會拋出編譯警告，同樣不會優化。這種設計讓尾遞歸優化可預期、可控，我們可以明確地知道，一個用了 tailrec 的函數如果通過了編譯、沒有警告，一定是成功地進行了尾遞歸展開，不會有「爆棧」的風險。

如何寫出尾遞歸函數

尾遞歸與迭代（while、for 等）是等價的，我們可以把迭代語句改寫成尾遞歸的形式。怎麼改寫呢？我們的迭代語句往往包含了三部分：

• 迭代條件檢查：檢查當前狀態需不需要進行迭代；
• 迭代過程：每次迭代處理的過程；
• 狀態更新：在每次迭代過程之間或之中更新狀態。

在改寫時，我們把不滿足迭代條件檢查的情況劃分為遞歸中的基準情況，進行特殊處理；把迭代過程寫到尾遞歸函數的主體部分，狀態更新則依賴於調用遞歸時的傳遞不同的參數。

首先看標準庫中的一個例子：IntArray.indexOf 函數，它接受一個 Int 值，返回這個值在數組中的索引，不存在則返回 -1：

fun IntArray.indexOf(element: Int): Int { for (index in indices) { if (element == this[index]) { return index } } return -1}

我們來把它改寫成尾遞歸的形式。這裡的 for 循環隱藏了很多細節，既包括了迭代條件的檢查，還承擔著更新狀態的作用，在寫成尾遞歸時都需要分離出來。通過分析可以發現，狀態更新依賴於當前索引值，因此一定要給尾遞歸函數添加索引值的參數來更新狀態。但要注意，如果 IntArray 為空，就不能依賴索引值了，所以一定要另外處理 this.isEmpty()，防止出現 IndexOutOfBoundsExcepiton。考慮到這些情況，我們的尾遞歸形式可以這樣寫：

fun IntArray.indexOf(element: Int): Int = if(isEmpty()) -1 else indexOfImpl(element, 0)private tailrec fun IntArray.indexOfImpl(element: Int, index: Int): Int = when { index == size -> -1 element == this[index] -> index else -> indexOfImpl(element, index + 1)}

在編譯後，indexOfImpl 函數實際上是這樣的：

private fun IntArray.indexOfImpl(element: Int, index: Int): Int { while (true) { if (index == size) return -1 if (element == this[index]) return index index++ }}

Kotlin 編譯器直接在整個函數體外加了一個無限循環，把所有遞歸調用替換為修改局部變數。

這個例子比較簡單，也沒有體現出尾遞歸的優勢：簡潔明了，直達演算法本質 ，我們再看一個例子。

首先定義一個二叉查找樹的節點類：

data class TreeNode( val element: Int, val left: TreeNode?, val right: TreeNode?)

我們需要給它擴展一個查找特定節點的函數 find，它接受一個 Int 類型的參數，在以指定節點為根的樹里查找對應的節點，如果沒有找到就返回 null。首先用迭代的方式：

fun TreeNode?.find(value: Int): TreeNode? { var now = this loop@ while (now != null) { now = when { value < now.element -> now.left value > now.element -> now.right else -> break@loop } } return now}

因為 Kotlin 禁止在 when 語句內用 break / continue，所以必須用標籤跳出 while 循環。這種寫法非常不優雅，我們把它改寫成尾遞歸的形式：

tailrec fun TreeNode?.find(value: Int): TreeNode? = when { this == null || element == value -> this element < value -> left.find(value) else -> right.find(value)}

尾遞歸的寫法簡潔優雅，直擊二叉樹查找的本質：如果查找值小於當前節點，就在左子樹中繼續查找；大於當前節點，就在右子樹中查找；等於的話就直接返回當前節點。同時，尾遞歸優化讓這個函數的性能與上面迭代函數沒有任何區別，有什麼理由不用尾遞歸呢？

當然，尾遞歸也不是萬能的，並不適用於所有需要迭代的場合。比如列印出一個 List 里所有滿足條件的元素，就非常適合用 filter + forEach 處理，如果用尾遞歸就顯得很笨拙了，還得另外定義一個函數。另外，寫出簡潔正確的尾遞歸函數需要一定的練習，也不是每個開發者都讀得懂尾遞歸代碼，這都是它的短板。