Haskell/遞迴

遞迴 (解決方案)

基礎 Haskell

遞迴
 列表 II (map)
列表 III (摺疊，推導)
型別宣告
 模式匹配
 控制結構
 更多關於函式
 高階函式
 有效使用 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 相加四次的結果相同。當然，將 5 相加四次與將 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一樣。