Haskell/遞迴

遞迴 (解決方案)

基礎 Haskell

遞迴
 列表 II (map)
列表 III (folds, comprehensions)
型別宣告
 模式匹配
 控制結構
 關於函式的更多資訊
 高階函式
 有效使用 GHCi

編輯本章

遞迴函式在 Haskell 中扮演著核心角色，並且廣泛應用於計算機科學和數學領域。遞迴本質上是一種重複的形式，我們可以透過區分一個函式是遞迴的含義以及它的行為方式來理解它。

一個遞迴函式簡單來說就是：能夠呼叫自身的函式。

它的行為方式是，它僅在滿足條件時才會呼叫自身，就像 if/else/then 表示式或包含至少一個基本情況（用於終止遞迴）和一個遞迴情況（導致函式呼叫自身，形成迴圈）的模式匹配一樣。

如果沒有終止條件，遞迴函式可能會永遠迴圈，導致無限遞迴。

數值遞迴

階乘函式

數學（特別是組合學）中有一個名為階乘的函式。^[1]它接受一個非負整數作為引數，找到所有小於或等於“n”的正整數，並將它們全部相乘。例如，6 的階乘（表示為 $6!$ ）是 $1\times 2\times 3\times 4\times 5\times 6=720$ 。我們可以使用遞迴風格在 Haskell 中定義它。

讓我們看看兩個相鄰數字的階乘

示例：連續數字的階乘

Factorial of 6 = 6 × 5 × 4 × 3 × 2 × 1
Factorial of 5 =     5 × 4 × 3 × 2 × 1

注意我們是如何對齊的。你可以看到 $6!$ 包含 $5!$ 。事實上， $6!$ 只是 $6\times 5!$ 。讓我們繼續

示例：連續數字的階乘

Factorial of 4 = 4 × 3 × 2 × 1
Factorial of 3 =     3 × 2 × 1
Factorial of 2 =         2 × 1
Factorial of 1 =             1

任何數字的階乘都只是該數字乘以比它小 1 的數字的階乘。有一個例外：如果我們要求 0 的階乘，我們不希望將 0 乘以 -1 的階乘（階乘只適用於正數）。事實上，我們只是說 0 的階乘是 1（我們定義它是這樣。只要相信我們，這是正確的。^[2]）。所以，0 是遞迴的基本情況：當我們到達 0 時，我們可以立即說答案是 1，不需要遞迴。我們可以總結階乘函式的定義如下

0 的階乘是 1。
任何其他數字的階乘是該數字乘以比它小 1 的數字的階乘。

我們可以直接將它翻譯成 Haskell

示例：階乘函式

factorial 0 = 1
factorial n = n * factorial (n - 1)

這定義了一個名為 factorial 的新函式。第一行說 0 的階乘是 1，第二行說任何其他數字 n 的階乘等於 n 乘以 n - 1 的階乘。注意 n - 1 周圍的括號；如果沒有它們，這將被解析為 (factorial n) - 1；請記住，函式應用（將函式應用於值）在沒有指定分組的情況下優先於其他任何操作（我們說函式應用繫結得更緊）。

注意

上面的 factorial 函式最好在檔案中定義，但由於它是一個小函式，因此在 GHCi 中將其寫成單行是可行的。為此，我們需要新增分號來分隔各行。

    > let factorial 0 = 1; factorial n = n * factorial (n - 1)

Haskell 實際上使用行分隔和其他空白來代替分號和括號之類的分隔和分組字元。Haskell 程式設計師通常更喜歡單獨的行和適當縮排帶來的整潔外觀；儘管如此，顯式使用分號和其他標記始終是一種替代方案。

上面的示例演示了數字 n 的階乘與稍微小一點的數字 n - 1 的階乘之間的簡單關係。

將函式呼叫視為委託。遞迴函式的指令委託一個子任務。碰巧的是，委託函式使用與委託者相同的指令；只有輸入資料發生了變化。遞迴函式唯一真正令人困惑的地方是，每個函式呼叫都使用相同的引數名，因此跟蹤多個委託可能會很麻煩。

讓我們看看執行 factorial 3 時會發生什麼

3 不等於 0，因此我們計算 2 的階乘
- 2 不等於 0，因此我們計算 1 的階乘
  - 1 不等於 0，因此我們計算 0 的階乘
    - 0 等於 0，因此我們返回 1。
  - 為了完成 1 的階乘計算，我們將當前數字 1 乘以 0 的階乘（即 1），得到 1（1 × 1）。
- 為了完成 2 的階乘計算，我們將當前數字 2 乘以 1 的階乘（即 1），得到 2（2 × 1 × 1）。
為了完成 3 的階乘計算，我們將當前數字 3 乘以 2 的階乘（即 2），得到 6（3 × 2 × 1 × 1）。

（注意，我們最終得到了兩次出現的 1，因為基本情況是 0 而不是 1；但這沒關係，因為乘以 1 不會有任何影響。如果我們想的話，我們可以將 factorial 設計成在 1 處停止，但慣例（通常很有用）是定義 0 的階乘。）

在閱讀或編寫遞迴函式時，你很少需要逐一“展開”遞迴——我們將這項工作留給編譯器。

關於我們對factorial的遞迴定義，還有一個需要注意的地方：這兩個宣告（一個用於factorial 0，另一個用於factorial n）的順序很重要。Haskell 從頂部開始，選擇第一個匹配的函式定義來決定使用哪個函式定義。如果我們在“基本情況”（factorial 0）之前定義一般情況（factorial n），那麼一般情況下的n會匹配傳遞給它的任何東西——包括 0。編譯器會得出結論，factorial 0 等於0 * factorial (-1)，以此類推，直到負無窮大（顯然這不是我們想要的）。因此，始終將多個函式定義從最具體的開始列出，並逐步列出到最一般的。

練習

將階乘函式輸入到 Haskell 原始檔中，並將其載入到 GHCi 中。
嘗試一些示例，例如factorial 5 和 factorial 1000。^[3]
- factorial (-1) 怎麼樣？為什麼會發生這種情況？
一個數字 n 的雙階乘是指從 1 到 n 之間所有與 n 奇偶性相同的整數的乘積。例如，8 的雙階乘是 8 × 6 × 4 × 2 = 384，7 的雙階乘是 7 × 5 × 3 × 1 = 105。在 Haskell 中定義一個doubleFactorial 函式。

迴圈、遞迴和累積引數

命令式語言在 Haskell 程式使用遞迴的相同上下文中使用迴圈。例如，在 C（一種典型的命令式語言）中，使用for迴圈編寫階乘函式的一種慣用法如下所示

示例： 命令式語言中的階乘函式

int factorial(int n) {
  int res = 1;
  for ( ; n > 1; n--)
    res *= n;
  return res;
}

這裡，for 迴圈會導致res被重複乘以n。在每次重複之後，從n中減去1（這就是n--的作用）。當n不再大於1時，重複操作停止。

無法直接將此類函式直接轉換為 Haskell，因為不允許更改變數res 和n的值（破壞性更新）。但是，你可以始終將迴圈轉換為等效的遞迴形式，方法是將每個迴圈變數作為遞迴函式的引數。例如，以下是上述迴圈在 Haskell 中的遞迴“轉換”。

示例： 使用遞迴來模擬迴圈

factorial n = go n 1
    where
    go n res
        | n > 1     = go (n - 1) (res * n)
        | otherwise = res

go是一個輔助函式，它實際上執行階乘計算。它接受一個額外的引數res，該引數用作累積引數來構建最終結果。

注意

根據你熟悉的語言，你可能擔心遞迴會導致效能問題。但是，Haskell 和其他函數語言程式設計語言的編譯器包含了許多針對遞迴的最佳化（考慮到遞迴的頻繁使用，這一點並不奇怪）。此外，Haskell 是惰性的——只有在其他計算需要其結果時才會執行計算，這有助於避免一些效能問題。我們將在後面的章節中進一步討論這些問題以及它們涉及的一些細微差別。

其他遞迴函式

事實證明，factorial函式並沒有什麼特別之處；許多數值函式都可以以自然的方式遞迴定義。例如，讓我們考慮乘法。當你第一次學習乘法的時候（還記得那一刻嗎？），它可能是一個“重複加法”的過程。也就是說，5 × 4 等於將 5 加 4 次。當然，將 5 加 4 次與將 5 加 3 次，然後再加上一個 5 是相同的——也就是說，5 × 4 = 5 × 3 + 5。這使我們得到了一個自然的乘法遞迴定義

示例： 遞迴定義的乘法

mult _ 0 = 0                      -- anything times 0 is zero
mult n m = (mult n (m - 1)) + n   -- recurse: multiply by one less, and add an extra copy

退一步來說，我們可以看到數值遞迴是如何融入一般遞迴模式的。數值遞迴的基本情況通常包括一個或多個特定的數字（通常是 0 或 1），對於這些數字，可以直接給出答案。遞迴情況透過遞迴呼叫函式，使用更小的引數，並使用結果以某種方式生成最終答案。使用的“更小引數”通常比當前引數小 1，從而導致遞迴“沿著數軸向下走”（類似於上面factorial 和mult的示例）。但是，原型模式並非唯一可能的情況；更小的引數也可以透過其他方式生成。

練習

類似於我們上面對factorial 3 的展開，展開乘法 5 × 4。
定義一個遞迴函式power，使得power x y將x提升到y次方。
你有一個函式plusOne x = x + 1。在不使用任何其他(+)的情況下，定義一個遞迴函式addition，使得addition x y將x和y加在一起。
（更難）實現函式log2，它計算其引數的整數對數（以 2 為底）。也就是說，log2計算小於或等於其引數的 2 的最大冪的指數。例如，log2 16 = 4，log2 11 = 3，log2 1 = 0。（小提示：閱讀這些練習之前的那段話的最後一句話。）

基於列表的遞迴

Haskell 有許多遞迴函式，特別是在列表方面。^[4] 考慮找到列表長度的length函式

示例： length的遞迴定義

length :: [a] -> Int
length []     = 0
length (x:xs) = 1 + length xs

注意

如果你嘗試從原始檔中載入上面的定義，GHCi 會在你嘗試使用它時抱怨“模糊的出現”，因為 Prelude 已經提供了length。在這種情況下，只需將你正在定義的函式的名稱更改為其他名稱，例如length' 或myLength。

因此，length 的型別簽名告訴我們它接受任何型別的列表並生成一個Int。下一行表示空列表的長度為 0（這是基本情況）。最後一行是遞迴情況：如果一個列表不是空的，那麼它可以分解成第一個元素（這裡稱為x）和列表的其餘部分（如果沒有任何其他元素，這將是空列表），按照慣例，將被稱為xs（即x 的複數）。列表的長度是 1（考慮x）加上xs 的長度（就像在下一步中的tail示例中一樣，當引數列表與 (:) 模式匹配時，xs 被設定）。

考慮連線函式(++)，它將兩個列表連線在一起

示例： 遞迴(++)

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
Prelude> "Hello " ++ "world" -- Strings are lists of Chars
"Hello world"

(++) :: [a] -> [a] -> [a]
[] ++ ys     = ys
(x:xs) ++ ys = x : xs ++ ys

這比length稍微複雜一些。該型別表示(++)接受兩個相同型別的列表，並生成另一個相同型別的列表。基本情況表示將空列表與列表ys連線起來與ys本身相同。最後，遞迴情況將第一個列表分解成其頭部（x）和尾部（xs），並表示要連線兩個列表，將第一個列表的尾部與第二個列表連線起來，然後將頭部x附加到前面。

這裡有一個模式：對於基於列表的函式，基本情況通常涉及一個空列表，遞迴情況涉及將列表的尾部再次傳遞給我們的函式，這樣列表就會逐漸變小。

練習

為以下基於列表的函式提供遞迴定義。在每種情況下，考慮基本情況是什麼，然後考慮一般情況在比它小的所有東西方面是什麼樣的。（注意，所有這些函式都可以在 Prelude 中使用，因此你在 GHCi 中測試定義時，需要為它們指定不同的名稱。）

replicate :: Int -> a -> [a]，它接受一個計數和一個元素，並返回一個列表，該列表是該元素重複該計數次數的結果。例如replicate 3 'a' = "aaa"。（提示：考慮計數為 0 時任何東西的複製是什麼；計數為 0 是你的“基本情況”。）
(!!) :: [a] -> Int -> a，它返回給定“索引”處的元素。第一個元素位於索引 0 處，第二個元素位於索引 1 處，依此類推。請注意，對於此函式，你正在對數字和列表進行遞迴^[5]。
（有點難）zip :: [a] -> [b] -> [(a, b)]，它接受兩個列表並將其“壓縮”在一起，以便結果列表中的第一對是兩個列表的前兩個元素，依此類推。例如zip [1,2,3] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')]。如果任何一個列表比另一個列表短，那麼可以在任何一個列表用完時停止。例如zip [1,2] "abc" = [(1, 'a'), (2, 'b')]。
使用輔助函式和累積引數定義length，就像迴圈式的factorial的備用版本一樣。

遞迴用於定義幾乎所有與列表和數字相關的函式。下次你需要一個基於列表的演算法時，從空列表的情況和非空列表的情況開始，看看你的演算法是否遞迴。

不要對遞迴太興奮…

儘管遞迴在 Haskell 中無處不在，但很少有人需要編寫顯式遞迴的函式。相反，標準庫函式以各種方式為我們執行遞迴。例如，實現factorial函式的一個更簡單的方法是

示例： 使用標準庫函式實現階乘

factorial n = product [1..n]

這看起來幾乎像是作弊，不是嗎？:) 這是大多數經驗豐富的 Haskell 程式設計師會編寫的 factorial 版本，而不是我們最初使用的顯式遞迴版本。當然，product 函式在幕後使用了一些列表遞迴，^[6] 但以這種方式編寫 factorial 意味著你，程式設計師，不必擔心它。