Haskell函數式程式設計之二-遞歸

在Haskell的世界中，沒有變量指派，流程跳轉，如果要實作一些簡單的功能，比如求一個數組中的最大值，都需要借助遞歸實作。

遞歸函數的定義:

A function may be partly defined in terms of itself.

即如果一個函數的定義中使用了其自身，這個函數就叫做遞歸函數。

我們就寫一個簡單的對數組求和的函數。

第一行定義了了一個名為<code>sum'</code>的函數的參數及傳回值。這個函數接收一個類型為Num的數組并傳回一個Num型的數值。（這裡的<code>'</code>是函數名的一部分，因為Haskell允許<code>'</code>作為函數名的一部分。由于系統已經有了sum函數，是以我們加個<code>'</code>與标準sum函數區分開。）

第二行的(x:xs)就是我們傳入的數組參數。我們這裡使用了Haskell的pattern matching。x表示的是數組中的第一個元素，xs表示數組中的其它元素。我們可以描述求數組中值的和的行為為：數組中的第一個元素與數組中剩餘元素的和。是以這就是我們的實作。

第三行則說明了如果給一個空的數組則直接傳回0。這也叫做遞歸的退出條件，否則遞歸會沒完沒了。

第二行和第三行共同完成了這個<code>sum'</code>函數的定義。當你傳遞給它一個參數時，它會根據參數的情況自動選擇調用那個實作。

假設我們這樣調用它：<code>sum' [1,2,3]</code>,程式的執行過程是這樣子的：

這種遞歸有個問題就是我們一直到等到遞歸結束才進行算術運算，這樣在執行過程既要儲存函數調用的堆棧，還要儲存中間計算結果的堆棧，如果遞歸過深，很容易引起stackOverFlow.

針對上述問題，我們可以換種寫法。

我們這樣調用它: <code>sum' [1,2,3] 0</code>。

它的執行順序是這樣的:

第二種寫法其實就是尾遞歸。

尾遞歸的定義：

A recursive function is tail recursive if the final result of the recursive call is the final result of the function itself.

即:如果一個遞歸函數，它的最終的遞歸調用結果就是這個函數的最終結果，那它就是尾遞歸的。

是以我們可以明顯看出，第一個不是尾遞歸，第二個是。

在大多數程式設計語言中，調用函數需要消費堆棧空間，一個實作了尾遞歸的遞歸函數在進行遞歸調用時，其實隻關心遞歸調用的結果，是以當我們調用下層函數時，可以舍去上層函數的堆棧調用情況，下層遞歸調用可以重用這個堆棧空間，這種就叫做尾遞歸優化。一個可能的實作方式是：隻需要把彙編代碼call改成jmp, 并放棄所有 局部變量壓棧處理，就可以了。

盡管尾遞歸比遞歸更節省堆棧空間，但并非所有的遞歸算法都可以轉成尾遞歸的，因為尾遞歸本質上執行的是疊代的計算過程。這與并非所有的遞歸算法都可以轉成疊代算法的原因是一樣的。

互遞歸就是多個遞歸函數之間互相調用。互遞歸的一個簡單的例子就是判斷一個自然數是偶數還是還是奇數。

這個實作很有意思。

任何一個互遞歸都可以被轉變為直接遞歸(direct recursion)，即将另一個調用inline到目前遞歸函數中。

下面是isOdd和isEven的直接遞歸版本。