Haskell/遞歸

遞歸 (解答)

Elementary Haskell

遞歸這個絕妙想法是Haskell（一般也是計算機科學）的中心：即，遞歸是在一個函數定義的內部用到自身。有此種定義的函數叫做遞歸。聽起來好像會導致無限重複，但只要定義適當，就不會這樣。

一般來說，一個遞歸函數的定義有兩個部分。首先，至少要有一個底線，就是一個簡單的線，越過此處，遞歸會停止（換言之，此時函數會直接返回值，而不會繼續「遞歸般地」調用自身。底線保證了此函數必定結束。其次，是更一般的遞歸區，若參數在此範圍內就會以某種形式調用自身。下面是例子。

數值遞歸

階乘函數

數學上，尤其是組合數學，有一個相當常用的函數叫做階乘(Factorial)。^[1]階乘函數的參數是一個自然數，它會返回1與此數之間所有數的乘積。比如，6的階乘是 1 × 2 × 3 × 4 × 5 × 6 = 720 。這相當有趣，因為對我們來說，它可以用一種遞歸函數來表示。

首先，我們比較相鄰兩個數的階乘。

Example

例子: 相鄰數的階乘

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

注意我們是如何對齊的。明顯可以看出6的階乘和5的階乘有關係。6的階乘就是6 × （5的階乘）。讓我們來看另一個例子。

Example

例子: Factorials of adjacent numbers

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
任何數的階乘都是此數乘以比此數小一的數的階乘。

這個在Haskell中表示為：

Example

例子: 階乘函數

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

這就定義了一個新的叫做factorial的函數。第一行表示0的階乘是1，第二行表示任意別的數n的階乘等於n乘以 n-1的階乘。注意那個把n-1括起來的括弧：沒有這個括弧代碼就會被解析稱為(factorial n) - 1；函數行為的優先級是很高的，會最先執行。 Template:Warning

到現在為止，你都會覺得有點微妙。實際上起作用嗎？來看看到底執行了factorial 3到底會發生什麼事情吧：

3不是0，所以「遞歸」（再次執行factorial函數）：看2的階乘是幾（也就是factorial 3）
- 2不是0，所以「遞歸」
  - 1不是0，遞歸
    - 0就是0，所以我們返回1
  - 我們將得到的1和本來的1相乘，得到 1 ，即(1 × 1)，返回它
- 我們將得到的1和本來的2相乘，得到2，即(2 × 1 × 1)，返回它
我們將得到的2和本來的3相乘，得到6，即6 (3 × 2 × 1 × 1)

我們可以看出乘法如何貫穿整個遞歸過程。

注意，我們最終的式子中1出現了兩次，因為底線是0而不是1；不過這造不成什麼錯誤，因為乘1還會是原來的數。如果我們想讓 factorial 在1處停下也辦得到，但0做底線符合常理，而且會很實用。

還有一點需要注意的：兩個聲明（一個是factorial 0的聲明，一個是factorial n的聲明）的順序很重要。Haskell會先匹配第一個句子，來決定函數的定義。所以，如果我們把兩句聲明掉個，第一個n語句將會匹配任何數（包括0）。所以語句 factorial 0的執行過程是去匹配情況n，於是factorial 0 的結果將會是0 * factorial (-1)，然後就會沒完沒了。無限循環不是我們想要的。一般來說：特殊情況應該置於前，一般情況置於後。

練習

將階乘函數鍵入到一個源文件中，再載入到你的Haskell環境中
- factorial 5是幾?
- 那 factorial 1000呢?如果你有個計算器，先用它算一算，然後看看和電腦中的一樣嗎？
- 要是 factorial (-1)會如何？為何如此？
雙階乘意為：從1（或2）隔一個數字乘一個，一直乘到n。比如，8的雙階乘是 8 × 6 × 4 × 2 = 384, 7的雙階乘是 7 × 5 × 3 × 1 = 105. 定義一個雙階乘函數doublefactorial.

一次小小的跑題

此段落欲為習慣命令式語言如c或Java的用戶提供指導。

在命令式語言中，「循環」是很普遍的。在命令式語言中，階乘函數的通常寫法是用一個「for」循環，如下（用c語言）：

Example

例子: 命令式語言中的階乘函數

int factorial(int n) {
  int res = 1;
  for (i = 1; i <= n; i++)
    res *= i;
  return res;
}

這在Haskell中直接實現是不可能的，因為改變變量res和i的值（以一種破壞性的方式）是不可以的。然而，我們依然可以將一個循環轉換為同作用的遞歸形式。重點是讓每個需要改變的循環變量變成一個遞歸函數的參數。比如，以下將上個循環「直譯」為Haskell。

Example

例子: 用遞歸模擬循環

factorial n = factorialWorker 1 n 1 where
factorialWorker i n res | i <= n    = factorialWorker (i+1) n (res * i)
                        | otherwise = res

垂直號之後的表達式叫做「guards」（衛士），更詳細的可以參考control structures。現在，我們應該可以通過與以上的c語言代碼相比弄懂它是如何工作的。

很明顯，在Haskell中，要實現階乘函數，這不是一個簡明、優雅的方式，但我們應該也知道，這種翻譯也可以實現。

另一點需要提醒的是不必擔心Haskell中遞歸性能會很低。一般來說，函數式語言的編譯器都會對遞歸多所優化，包括一個重要的「尾遞歸優化」；記住：Haskell很懶，如果不必要，就不會發生。

其他遞歸函數

正如它本身所揭示的，factorial函數沒有什麼特殊之處；一大批數學函數都可以一種自然地方式遞歸定義。比如，乘法。你第一次接觸乘法（回憶一下那是什麼時候？:)），你認為那就是「重複加」而已。就是說， 5 × 4 和加四個5的結果是一樣的。當然，加四個5和先加三個5再加一個5是一樣的——也就是說， 5 × 4 = 5 × 3 + 5。這讓我們自然想到了乘法的遞歸定義形式。

Example

例子: 遞歸地定義乘法

mult n 0 = 0                      -- 任何数乘 0 是 0
mult n 1 = n                      -- 任何数乘 1 是它本身
mult n m = (mult n (m - 1)) + n   -- 递归体：乘个数减1再加本身

回頭看看，我們可以看到數字遞歸式如何寫成一般遞歸形式的。數字遞歸的基線通常包括一個或更多特殊數字（通常是 0 或 1 ），對這些數字，我們可以立刻給出答案。遞歸體中，通過調用具有更小的參數的函數，相加返回值來產生結果。「更小的參數」通常比本處的參數更小，從而導致遞歸會「朝着更小的數走去」（就像factorial的例子一樣）。當然，更小的參數也可以由其他方式產生。

練習

展開 5 × 4 ，方式參考 factorial 3的展開。
定義一個遞歸函數 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中「很多」函數都是遞歸函數，尤其是跟表有關的。^[3]設想一個可以計算表長度的 length 函數。

Example

例子: length的遞歸定義

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

別被眼花繚亂的語法弄蒙了，我們會在模式匹配章節更深入的了解。現在，我們把代碼翻譯成人話，搞懂它如何發揮作用。第一行說明了 length的類型：它允許任何表進去，並且產生一個 Int，也就是整數。下一行表示一個空表的長度是 0 。當然，這也是基線（底線）。最後一行是遞歸區：如果一個表包括一個第一元素 x 和表的其餘部分、另外一個表 xs ，那麼表的長度是 xs 的長度加1。

那麼一個 (++) 函數，這個函數可以實現兩個表相連，該如何實現呢？（下面給出這個運算符的幾個例子，因為我們還沒見到過這個功能呢。）

{{HaskellExample|<遞歸的code>(++)函數|

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 訂在前面。

這就是模式：在基於表的函數中，基線通常和空表相關，遞歸區通常會把表的尾部再傳回函數自身以遞歸，這樣表會越來越小。

練習

給出以下基於表的函數的遞歸定義。對每一題，想想基線是什麼，而遞歸區又如何，又如何做到參數越來越小？

replicat :: Int -> a -> [a]，作用是接受一個數字和一個元素，返回有此數字個元素的表。比如： replicat 3 'a' = "aaa" 。（提示：考慮下0個元素的表是什麼樣子，個數 0 就是你的基線。
(!!) :: [a] -> Int -> a在給出的 index（指針）處返回元素。第一個元素是 index 0第二個是 1 ，以此類推。注意在此函數中，你得對數字和表同時「遞歸」。
（有點難度） zip :: [a] -> [b] -> [(a, b)] ，拉鏈函數，將每個表中對應位置的元素連在一起，組成一個大表。比如 zip [1,2,3] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')] 。如果某個表比較短，則立即停止即可。如 zip [1,2] "abc" = [(1, 'a'), (2, 'b')] 。

遞歸幾乎是所有表函數和數字函數的實現方法。下一次你再遇到基於表的函數時，先看看空表時的情況，再看看不空時的情況，也就知道這個算法是不是遞歸的了。呵呵。