close
作者：WhiteBlackGoose
譯者：張雨佳

大部分人都知道遞歸的含義，即通過自身來定義一些東西。

但實際上，這種簡單的定義可以完全改變你編寫命令式算法的方式。無論你是使用Java、c#、Python還是F#的開發人員，都可以在通用編程語言中使用遞歸！

定義循環

首先介紹循環，循環不單單是「做n次同一件事」或「條件為真時進行重複」。我認為循環的迭代實際上是一個函數，它可以改變了某些全局變量的狀態。並且循環是從某個初始狀態開始的鏈式函數：循環是初始狀態和轉換（迭代）的有限鏈。

比如下面這個偽代碼：


求和的常用遞歸方法

它的全局狀態是元組「sum」和「i」，轉換是在sum上對arr[i]求和並且令i + 1。


具有初始狀態的鏈式轉換

上面的代碼中使用了三個「func」函數的嵌套，我們如何讓這個鏈式函數自動運行呢？

事實上，我們可以教函數調用自己！

從循環到遞歸

下面我們讓「func」函數調用自己。


對數組所有元素求和的遞歸函數

你可能會發現，上面這個函數會無限次遞歸，所以我們需要添加循環的條件，類似於for或while函數的條件：


把循環轉換成遞歸

可以看出，我們用遞歸操作定義了循環，而且這是一種尾遞歸，即直接將循環轉換成遞歸（後面會進行詳細解釋）。

這同樣也是一種歸納定義（inductive definition）。基礎base是i大於等於3，轉換函數是「假設func是為i + 1定義的，那麼同樣func函數也是為i定義的」。

遞歸的定義是如此簡單，沒有「改變」和變化的變量。它所做的只是返回一個或、】另一個東西，這難道不棒嗎？

為什麼需要遞歸？

因為遞歸更簡單、更容易閱讀、編寫，也更容易調試。

方便閱讀

舉一個非常簡單的例子：階乘。下面是循環定義的階乘操作：


循環定義的階乘

你能直接告訴我factorial(0)返回的值嗎？factorial(4)的值是24嗎？是比factorial(6)少一次迭代還是比factorial(120)多一次迭代呢？你需要知道1到n的循環中是否包含n，然後仔細建模。

那麼階乘的「模型」是什麼？

其定義如下：


遞歸定義的階乘

你不需要去想進行多少次迭代，只需要知道它在base下（0和1）是正確的，那麼它在n轉變到n-1時也會是正確的。

方便編寫代碼

我們再將目光轉向斐波那契數列。在數學中，它的定義如下：


斐波那契數列的數學定義

但由於這樣編寫代碼非常低效，所以沒有人會這樣寫。

下面是一種命令式的編寫方法：


斐波那契數列的循環定義

同樣的，你能預測fib(5)的輸出嗎？你能確定應該返回的是a而不是b嗎？你能確定有n次，n-1次還是n+1次迭代？

實際上，我們可以用遞歸方法寫出相同時間複雜度的解決方案，也叫做memoization。在帶有可以修改函數的修飾器（decorators）的語言中，我們只需要在上面添加一點操作：


memoization的斐波那契數列

這個函數對於相同的輸入會返回相同的答案，並且時間複雜度是線性的，所以我們需要做的就是將其存入緩存。

（對於沒有decorators的語言，你可以手動對輸入進行檢查，這並不難做到）

方便調試

與需要跳進函數的遞歸相比，似乎調試循環方法更容易一些，你只需要遍歷迭代。

但事實上，調試遞歸定義的函數有兩個優點：

（1）可以隨時檢查或計算任何輸入下的函數值（但循環中不能任意選擇迭代次數）。

（2）可以直觀看到調用棧和每個棧幀中變量的值。


查看調用棧幀的變量。交互式地運行函數

遞歸還能幹什麼？

下面會展示一些遞歸的應用，但實際上，你可以將任何循環用遞歸實現。例如，可以遍歷樹結構：


二叉查找樹中查找對應值的循環方法

下面是等價的遞歸方法：


二叉查找樹中查找對應值的遞歸方法

是不是看起來整潔許多！在複雜的算法中，閱讀和編寫這樣的代碼會比較容易，甚至都不需要進行調試。

那最主要的問題是，何時才會給出所需的答案？

下面是命令式代碼：


命令式實現方法

首先為了進入循環，我們必須聲明「n」並將其初值設置為空（null），並且每次都會檢查重複條件「n是否等於null」，以確定輸入的數字是否正確！

讓我們簡化這些繁雜的代碼：


遞歸式實現方法

可見，遞歸方法更加直接明了。對上面代碼的翻譯是：

（1）輸入數字
（2）讀入數字
（3）如果數字為空，報告一個錯誤並再次輸入
（4）否則，返回這個數字

現在，你同樣可以翻譯出之前的命令式循環方法了，它大概是這樣的：

（1）假設數字為空
（2）當數字為空時，請求輸入一個數字
（3）將讀入的值分配給數字
（4）如果數字為空，則報告錯誤
（5）返回步驟2，重新開始
（6）返回數字

其他東西可以遞歸嗎？

不僅可以用遞歸定義函數。我認為世界上所有的東西都可以用遞歸的方式定義，比如下面幾個實際的例子。首先可以遞歸定義的東西是類型（types）。

類型的遞歸

二叉樹節點是最簡單的例子。二叉樹的節點通常有0、1或2個子節點，並且節點的類型相同。

在函數式或函數式優先的語言中，有種叫做列表（list）的數據類型，相當於離散數學中的字符串。那麼，列表滿足以下特點：

（1）要麼是空的

（2）要麼存在第一個元素，且剩下部分也是列表類型

下面是列表的定義：


歸納法定義的列表

其中，T是通用類型參數，可以用任何類型進行替換。

這樣構建的列表可以避免對所有索引進行遍歷，並允許我們動態地構建列表，而不必預先創建集合併填充它。例如，下面是對列表中所有整形（int）元素進行求和的函數：


遍歷列表

所以我們只需要考慮列表的兩種狀態：當它為空的時，和是0；當有第一個元素和其餘元素時，和是第一個元素加上其餘元素的和。

這是多麼簡單、方便啊！

假如你只想取索引為偶數的元素，最直接的方法是用i進行循環並判斷它是不是偶數，但也可以用以下方法：

（1）如果列表為空，那就返回空列表。
（2）如果只有一個元素，那就返回包含這個元素的列表。
（3）如果列表有兩個元素及剩餘部分元素，那就取第一個元素和剩餘部分元素的函數遞歸結果。

按照上述過程，寫出的代碼如下：


遍歷列表

這種類型的列表叫做單鍊表（singly linked list）

相互遞歸

相互遞歸的含義是用B定義A，同時B又是通過A定義的，並且在這個循環中可以有任意數量的「實體（entities）」。紅綠樹（Red-green trees）就是通過相互遞歸定義的。通常這種類型的遞歸比較少見。

語言支持

以上，已經展示了如何在大多數通用編程語言中使用遞歸方法來代替生硬和可讀性差的代碼。
同時，還可以通過語言的語法、數據結構和編譯工具的特殊功能繼續對遞歸進行優化。

優化尾遞歸

尾調用優化（TCO，tail call optimization）是指將尾遞歸編寫成實際的循環，常用編譯器進行優化，以便讓遞歸定義的函數與循環一樣高效。

下面來談談調用問題。當調用函數時，會保存當前指令，然後調用函數，調用後又會返回執行前的指令。

如果你想在調用後繼續完成某些功能，就必須按照上述過程進行。例如，對於定義為n *factorial (n-1)的階乘計算，你想在調用內部階乘函數之後，再將結果乘以n後返回。

那它的偽代碼如下：


sumSquares的偽代碼

sumSquares的功能是將從0到n的整數平方進行相加。因此，當輸入參數為0時，將0賦給返回值，並跳轉到返回地址。否則，我們保存當前地址，遞歸調用sumSquares (n-1)，與n²相加，然後跳轉到返回地址。

如果在函數調用後不進行任何操作，就可以直接跳轉。比如從累加器「accumulator」 中添加參數「acc」來實現累加。其具體實現如下：


利用累加器的遞歸定義

它看起來與我們最初討論的循環非常接近，用「i」替換「n」，用「sum」替換「acc」，就會變成循環操作。因此，其偽代碼如下：


可以直接轉換的偽代碼

但是事實上，調用時會把結果放入ret中，所以把調用的結果賦值給ret是完全沒有必要的。而且如果我們只想要函數返回的值，其實並不需要跳回到原來的地址。如果在調用「ret」後包含所需的值，那麼我們只用跳轉到自己並結束函數運行即可。


用跳轉代替尾調用

將其反編譯為偽代碼如下：


反編譯後的偽代碼

事實上，這是一種while循環，可以理解為：如果n是零那麼返回，否則運行某些代碼後跳轉到開頭，其功能與下面的while循環等價：


反編譯後的while循環

因此，當你用遞歸方法編寫函數後，編譯器會自動把它展開成循環！

但可惜的是，並不是所有的編譯器都支持該功能，只有在有tailrec的Kotlin、F#（和ML系列）、Scala和其他一些編譯器中可以使用。

數據結構

雖然遞歸不必處理不可變結構，但它可能需要動態地構造新對象。比如F#語言中就包括：

（1）單鍊表
（2）通過紅黑樹構成的Persistent maps 和sets
（3）可識別聯合（DUs）

我們的目的是讓人們在不損害其他方面的情況下使用遞歸函數，減少潛在的錯誤或誤差。

語法

當有合適的語法支持時，編寫遞歸定義的函數就會更加容易，比如有以下支持時：

（1）用於考慮不同情況的模式匹配（pattern matching）
（2）構造和解構列表和元組

例如，通過decorators，編程語言就可以提供緩存函數（memoize）的方法。

還有一些語言可以確保函數進行TCO優化。例如，Kotlin提供了「tailrec」功能，它會在無法優化時給出警告。

無法使用遞歸的情況

遞歸只是一種工具。如果是函數隻調用自身不超過一次的單遞歸的操作，就可以使用順序進行，比如C#中的LINQ，Kotlin中的sequences等等。

所以只有當遞歸比它的替代方法更好時，才需使用遞歸方法。比如寫一個過濾偶數的顯式函數時，就應該使用filter順序函數。

或者當編譯器不支持TCO，或者函數不受TCO約束，但有成千上萬次嵌套調用時，遞歸方法會消耗大量的堆棧，甚至達到溢出。但日常使用中，很少通過函數遍歷這麼大的序列。

關於數據實戰派
數據實戰派希望用真實的數據和行業實戰案例，幫助讀者提升業務能力，共建有趣的大數據社區。
點這裡關注我👇記得標星~


熱門視頻推薦


更多精彩視頻，歡迎關注學術頭條視頻號


#往期推薦 #

winter

【學術頭條】持續招募中，期待有志之士的加入

【招人】學術頭條多崗位招聘，我們一起見證改變生活的科技

2022-05-06


arrow
arrow
    全站熱搜
    創作者介紹
    創作者 鑽石舞台 的頭像
    鑽石舞台

    鑽石舞台

    鑽石舞台 發表在 痞客邦 留言(0) 人氣()