遞歸函數（二）：編寫遞歸函數的思路和技巧

05-21

來自專欄業餘程序員的個人修養

遞歸，是一個熟悉而陌生的概念，說它熟悉，是因為人們經常提起它，

而說它陌生，指的是人們在實際編程中幾乎不會主動使用它。

給定一個問題，如果本質上它能看做一個調用自身的規模較小的一個子問題來求解，

那麼給出一個遞歸的演算法解，就是很自然的。

然而，即使是這樣，編製一個遞歸函數也是一件令人頭疼的事情。

本系列文章的目的，可能並不局限於指出如何編寫一個遞歸函數，

而是期望想從遞歸函數開始，了解它相關的科學知識，以達到對不同領域觸類旁通的效果。

1. 從一個簡單的例子開始

首先，我們來重溫一下遞歸的概念，

維基百科上是這樣描述的，

遞歸（recursion），在數學與計算機科學中，是指在函數的定義中使用函數自身的方法。

我們來看一個簡單的例子吧。（Haskell代碼

fact :: Int -> Intfact 1 = 1fact n = n * fact (n-1)

在這個例子中，

第一行fact :: Int -> Int表示了fact函數的類型，

第二行和第三行定義了函數fact，

我們看到第三行，在對fact函數定義的時候，等式右邊又出現了fact，

這樣定義的函數fact是遞歸的。

我們調用一下fact，來看看結果，

fact 103628800

嗯嗯，fact就是階乘函數。

2. 寫遞歸函數的步驟

那麼，給定一個問題，我們編寫一個遞歸函數，要如何開始呢？

（1）遞推式

首先，我們要找到「遞推式」。

例如，在數學上階乘的定義是， $f(n)=n!$ ，這樣的表述形式，不具有遞推性。

我們先要想辦法把 $f(n)$ 用 $f(n-1)$ 表示出來。

經過思考之後，我們可以證明， $f(n)=n*f(n-1)$ ，

於是，我們就走出了關鍵的第一步，得到了「遞推式」。

（2）找出終止條件

有了「遞推式」還不行，我們還需要確定遞推在什麼時候終止。

我們知道 $f(1)=1$ ， $f(2)=2*f(1)$ ， $f(3)=3*f(2)$ ，等等，

因此，我們只需要指定 $f(1)=1$ ，那麼遞推就會在 $f(n)$ ，當 $n=1$ 的時候終止了。

終止，就是不再調用規模更小的問題了。

這時，終止條件是 $f(1)=1$ 。

（3）用數學歸納法證明解的正確性

這一步是很重要的，有很多人都缺少證明遞推式正確性的環節，

但是，考慮到介紹數學歸納法及其擴展會佔用不少篇幅，

這裡先略去，下一篇我們再回來討論它。

這裡，我們先假定，根據「遞推式」和「終止條件」，使用數學歸納法，

我們已經證明了這樣定義的 $f(n)$ 就是 $n!$ 。

（4）根據遞推式和終止條件，編寫程序

有了「遞推式」和「終止條件」，再編寫程序就水到渠成了。

很多人一上來就開始編碼，就會感覺毫無頭緒。

我們再來看下那段程序，

fact :: Int -> Intfact 1 = 1fact n = n * fact (n-1)

這不就是「遞推式」和「終止條件」的忠實表示嗎？

我們用fact 1 = 1表示了 $f(1)=1$ ，

用fact n = n * fact (n-1)表示了 $f(n)=n*f(n-1)$ 。

3. 小技巧

我們再看個複雜一點的例子。

在實際項目中，我們可能會遇到循環 $n$ 次的場景，

在循環過程中，我們會根據索引進行運算，然後將某些符合條件的運算放到最終的結果中。

例如，我們選擇10以內的所有偶數，

[x|x <- [0..9], x `mod` 2 == 0][0,2,4,6,8]

使用以上列表解析（list comprehension）的方法，我們可以快速得到結果。

但是這裡，我們想要拿它來舉例，介紹一個編寫遞歸函數常用的小技巧。

為了通用性，我們考慮循環n次，將索引傳入函數fn，

根據fn的返回值，將結果放入一個列表中，完成這個功能的函數我們記為myLoop 。

（1）困境

根據前文介紹的編寫步驟，我們需要先找到「遞推式」和「終止條件」。

「終止條件」怎麼寫呢？

假如我們定義的遞歸函數稱為myLoop，那麼 $myLoop(0,fn)$ 就是終止條件，它應該返回一個列表。但是這個列表在參數中沒有，它隨著遞歸調用的過程「積累」得到的。

好吧，那我們看「遞推式」。

$myLoop(n,fn)$ 要用 $myLoop(n-1,fn)$ 的結果計算出來，

我們需要先用索引調用fn，然後再根據fn的返回值，放入結果列表，再繼續調用 $myLoop(n-1,fn)$ 。可是，索引從哪來呢？

（n不是索引，因為索引從0開始，而n是逐漸變小的。

這是兩個典型的困難，

其一，我們在遞歸的過程中「積累」了某些東西，

其二，我們需要傳遞和遞歸過程相關的「索引」。

（2）解法

這時候，我們的小技巧就有用武之地了。

我們可以編寫一個輔助的遞歸函數，通過增加參數的辦法，提高靈活性。

例如，我們可以編寫一個輔助函數myLoop，然後用myLoop來實現myLoop。

myLoop :: Int -> (Int -> Maybe a) -> [a]myLoop n fn = myLoop n 0 fn []myLoop :: Int -> Int -> (Int -> Maybe a) -> [a] -> [a]myLoop 0 i fn lst = lstmyLoop n i fn lst = case fn i of Just x -> myLoop (n-1) (i+1) fn (lst++[x]) Nothing -> myLoop (n-1) (i+1) fn lst

以上，我們為myLoop增加了參數i和lst，分別表示「索引」和「積累」的列表。

然後，myLoop就可以用myLoop來實現了。

別忘了測試一下最終的結果，

myLoop 10 (x -> if x `mod` 2 == 0 then Just x else Nothing)[0,2,4,6,8]

（3）其他考慮

合理的利用遞歸函數的返回值，會減少附加參數的數量，例如，

myLoop :: Int -> (Int -> Maybe a) -> [a]myLoop n fn = myLoop n 0 fnmyLoop :: Int -> Int -> (Int -> Maybe a) -> [a]myLoop 0 i fn = []myLoop n i fn = case fn i of Just x -> x:(myLoop (n-1) (i+1) fn) Nothing -> myLoop (n-1) (i+1) fn

但最終得到的遞歸函數就不是尾遞歸了，

關於尾遞歸，我們將在後續文章中討論它。

參考

維基百科 - 遞歸

維基百科 - 遞推關係式

下一篇：遞歸函數（三）：歸納原理