Haskell/遞歸

出自Wikibooks
跳至導覽 跳至搜尋

遞歸這個絕妙想法是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),然後就會沒完沒了。無限循環不是我們想要的。一般來說:特殊情況應該置於前,一般情況置於後。

練習
  1. 將階乘函數鍵入到一個源文件中,再載入到你的Haskell環境中
    • factorial 5是幾?
    • factorial 1000呢?如果你有個計算器,先用它算一算,然後看看和電腦中的一樣嗎?
    • 要是 factorial (-1)會如何?為何如此?
  2. 雙階乘意為:從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中直接實現是不可能的,因為改變變量resi的值(以一種破壞性的方式)是不可以的。然而,我們依然可以將一個循環轉換為同作用的遞歸形式。重點是讓每個需要改變的循環變量變成一個遞歸函數的參數。比如,以下將上個循環「直譯」為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的例子一樣)。當然,更小的參數也可以由其他方式產生。

練習
  1. 展開 5 × 4 ,方式參考 factorial 3的展開。
  2. 定義一個遞歸函數 power ,使得 power x y 計數 xy 次冪。
  3. 已有一個函數 plusOne x = x + 1. 不使用任何 (+)(加號), 定義一個 addition,使得 addition x yxy 相加。
  4. (難) 實現函數 log2, 意思是求以 2 為底的對數。 即, log2 會計算以 2 為底的適合參數的最大的冪。比如, log2 16 = 4log2 11 = 3log2 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 訂在前面。

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

練習

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

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

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

不要太愛遞歸[編輯]

雖然我們對遞歸有個牢固的理解很重要,但這並不意味著在Haskell中我們要時時用遞歸編東西。事實上,有各種各樣的用遞歸函數標準庫,你只需要使用它們就可以了。比如,一種實現factorial(階乘)函數的簡單方式是這樣的:

Example

例子: 用標準庫實現 factorial 函數

factorial n = product [1..n]


簡直跟作弊差不多,對吧? :) 這就是有經驗的 Haskell 程式設計師會如何寫程序,他們不會動輒祭起遞歸這個法寶。當然, product 函數的本質就是表遞歸[4],但當我們用這種方式寫代碼的時候,不用操心其實現方式了。

概要[編輯]

遞歸是一種在函數定義內部調用自身的一種做法。它幾乎都是由兩種成分構成:基線和遞歸區。遞歸在處理表和數字時特別有用。



遞歸
習題解答
Elementary Haskell

Template:Haskell章節/Elementary Haskell

Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務


注釋[編輯]

  1. 在數學上,n的階乘用n!表示,但Haskell可沒有這種語法,所以這裡我們不會這樣用。
  2. 事實上,定義0的階乘是1絕非任意,而是因為0的階乘代表了 empty product.
  3. 這並非巧合,沒有變量,遞歸是實現控制結構的唯一方法。這聽起來很像限制,但只要習慣了,它絕不會礙手礙腳。
  4. 事實上,這個函數叫做 foldl ,經常被用來實現遞歸。