Haskell/遞歸
遞歸這個絕妙想法是Haskell(一般也是計算機科學)的中心:即,遞歸是在一個函數定義的內部用到自身。有此種定義的函數叫做遞歸。聽起來好像會導致無限重複,但只要定義適當,就不會這樣。
一般來說,一個遞歸函數的定義有兩個部分。首先,至少要有一個底線,就是一個簡單的線,越過此處,遞歸會停止(換言之,此時函數會直接返回值,而不會繼續「遞歸般地」調用自身。底線保證了此函數必定結束。其次,是更一般的遞歸區,若參數在此範圍內就會以某種形式調用自身。下面是例子。
數值遞歸
編輯階乘函數
編輯數學上,尤其是組合數學,有一個相當常用的函數叫做階乘(Factorial)。[1]階乘函數的參數是一個自然數,它會返回1與此數之間所有數的乘積。比如,6的階乘是 1 × 2 × 3 × 4 × 5 × 6 = 720 。這相當有趣,因為對我們來說,它可以用一種遞歸函數來表示。
首先,我們比較相鄰兩個數的階乘。
例子: 相鄰數的階乘
Factorial of 6 = 6 × 5 × 4 × 3 × 2 × 1 Factorial of 5 = 5 × 4 × 3 × 2 × 1
注意我們是如何對齊的。明顯可以看出6的階乘和5的階乘有關係。6的階乘就是6 × (5的階乘)。讓我們來看另一個例子。
例子: 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中表示為:
例子: 階乘函數
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不是0,遞歸
- 我們將得到的1和本來的2相乘,得到2,即(2 × 1 × 1),返回它
- 2不是0,所以「遞歸」
- 我們將得到的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)
,然後就會沒完沒了。無限循環不是我們想要的。一般來說:特殊情況應該置於前,一般情況置於後。
練習 |
---|
|
一次小小的跑題
編輯此段落欲為習慣命令式語言如c或Java的用戶提供指導。
在命令式語言中,「循環」是很普遍的。在命令式語言中,階乘函數的通常寫法是用一個「for」循環,如下(用c語言):
例子: 命令式語言中的階乘函數
int factorial(int n) { int res = 1; for (i = 1; i <= n; i++) res *= i; return res; }
這在Haskell中直接實現是不可能的,因為改變變量res
和i
的值(以一種破壞性的方式)是不可以的。然而,我們依然可以將一個循環轉換為同作用的遞歸形式。重點是讓每個需要改變的循環變量變成一個遞歸函數的參數。比如,以下將上個循環「直譯」為Haskell。
例子: 用遞歸模擬循環
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。這讓我們自然想到了乘法的遞歸定義形式。
例子: 遞歸地定義乘法
mult n 0 = 0 -- 任何数乘 0 是 0 mult n 1 = n -- 任何数乘 1 是它本身 mult n m = (mult n (m - 1)) + n -- 递归体:乘个数减1再加本身
回頭看看,我們可以看到數字遞歸式如何寫成一般遞歸形式的。數字遞歸的基線通常包括一個或更多特殊數字(通常是 0 或 1 ),對這些數字,我們可以立刻給出答案。遞歸體中,通過調用具有更小的參數的函數,相加返回值來產生結果。「更小的參數」通常比本處的參數更小,從而導致遞歸會「朝着更小的數走去」(就像factorial
的例子一樣)。當然,更小的參數也可以由其他方式產生。
練習 |
---|
|
基於表的遞歸
編輯Haskell中「很多」函數都是遞歸函數,尤其是跟表有關的。[3]設想一個可以計算表長度的 length
函數。
例子: 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
訂在前面。
這就是模式:在基於表的函數中,基線通常和空表相關,遞歸區通常會把表的尾部再傳回函數自身以遞歸,這樣表會越來越小。
練習 |
---|
給出以下基於表的函數的遞歸定義。對每一題,想想基線是什麼,而遞歸區又如何,又如何做到參數越來越小?
|
遞歸幾乎是所有表函數和數字函數的實現方法。下一次你再遇到基於表的函數時,先看看空表時的情況,再看看不空時的情況,也就知道這個算法是不是遞歸的了。呵呵。
不要太愛遞歸
編輯雖然我們對遞歸有個牢固的理解很重要,但這並不意味着在Haskell中我們要時時用遞歸編東西。事實上,有各種各樣的用遞歸函數標準庫,你只需要使用它們就可以了。比如,一種實現factorial(階乘)函數的簡單方式是這樣的:
例子: 用標準庫實現 factorial 函數
factorial n = product [1..n]
簡直跟作弊差不多,對吧? :) 這就是有經驗的 Haskell 程序員會如何寫程序,他們不會動輒祭起遞歸這個法寶。當然, product
函數的本質就是表遞歸[4],但當我們用這種方式寫代碼的時候,不用操心其實現方式了。
概要
編輯遞歸是一種在函數定義內部調用自身的一種做法。它幾乎都是由兩種成分構成:基線和遞歸區。遞歸在處理表和數字時特別有用。
遞歸 |
習題解答 |
Elementary Haskell |
Haskell |
Haskell基礎
>> 初級Haskell
>> Haskell進階
>> Monads
|
注釋
編輯- ↑ 在數學上,n的階乘用n!表示,但Haskell可沒有這種語法,所以這裡我們不會這樣用。
- ↑ 事實上,定義0的階乘是1絕非任意,而是因為0的階乘代表了 empty product.
- ↑ 這並非巧合,沒有變量,遞歸是實現控制結構的唯一方法。這聽起來很像限制,但只要習慣了,它絕不會礙手礙腳。
- ↑ 事實上,這個函數叫做
foldl
,經常被用來實現遞歸。