遞迴函數 (遞迴關係)

簡介

一函數 稱為 遞迴函數 (遞迴關係) 表示 該函數 可用 自身 和 起始條件 來定義。一般來說， 遞迴演算法是一種用程式來實現 Divide and Conquer（分而治之） 策略的重要方法。

什麼樣的問題適合用遞迴函式來解決呢?

一個問題如果可以拆解成規模較小但是性質和原問題完全一樣的問題的時候， 就可以考慮用遞迴函式來處理。 例如：

1. 連加
2. 連乘 ( 階乘 )
3. 輾轉相除
4. 搜尋
5. 排序
6. 老鼠走迷宮
7. 漢諾塔 ( Hanoi Tower, 又名河內塔 )

... 等等。

遞迴函式的設計方法

遞迴函式如何設計呢 ？

我們模仿 "數學歸納法"，分成下列二大步驟來做

1. 設定起始條件：問題要拆到多小才結束？這個最小的結果直接給一個答案當作邊界，讓大問題越拆越小，到這個邊界會結束，而不會陷入無窮迴圈。
2. 分而治之：將一個大的問題拆解為規模較小的幾個問題來分別對付。

我們以一個簡單的例子來說明：

Q1：己知正整數 n ，求 1+2+3+...+ n 之和

我們定義一個遞迴函式名為 sum() 來求這個問題的答案。

sum(n)=1+2+3+. ..          + n
　　　 =1+2+3+...+ (n-1) + n
　　　 = sum(n-1) + n

根據上面兩個步驟，我們將 sum(n) 定義如下：

         　　　    　 　 1 ,      　　　　   當 n=1 ,  (起始條件)
sum(n)=｛
                  　      sum(n-1) +  n,       當 n >1. (分而治之)

求 1+2+3+...+ n 相當於 求 1+2+3+...+ (n-1) 再加一個 己知的 n。

VB的程式碼如下：

VB6 程式碼

VB2008 程式碼

請注意：VB6 和 VB2008 的 Function 傳回值寫法有些不同。

再看一個相似的例子：

Q2：己知正整數 n ，求 n!

我們定義一個遞迴函式名為 Fac() 來求這個問題的答案。

Fac(n)=1×2×3×. ..          × n
              =1×2×3×...× (n-1) × n
              = Fac(n-1) × n

根據上面兩個步驟，我們將 Fac(n) 定義如下：

         　　　    　 　 1 ,      　　　　   當 n=1 ,  (起始條件)
Fac(n)=｛
                  　      Fac(n-1) ×  n,       當 n >1. 　(分而治之)

VB的程式碼如下：

VB6 程式碼

VB2008 程式碼

Q3: 求兩個正整數 a, b 的最大公因數

公元前 300 年 左右 Euclid 已經 使用 "輾轉 相除法" 來求 最大 公因數， 有興趣的人可以試著寫程式做做看，我們在此用遞迴函式來完成。

假設 a 除以 b 得 餘數 r， 則 a = bq + r, 0 <= r < b.　 以 符號 a mod b 表 餘數 r。
我們定義一個遞迴函式名為 gcd(a, b) 來求 a, b 的最大公因數，則有如下關係：

 gcd(a, b) = gcd(b, r) = gcd(b, a mod b)

根據上面兩個步驟，則 a 與 b 的 最大 公因數 可 由 表之如下：

　　　　　　　　　a, 　　　　　　當 b = 0 　　(起始條件)
gcd(a, b) = ｛
　　　　　　　    gcd(b, a mod b), 　　當 b > 0　　(分而治之)

VB的程式碼如下：

VB2008 程式碼

Q4: 月兔問題 與 費氏數列

某人 飼養 一對 新生 兔子， 設 兔子 過了 一個月 後 長大 成熟， 再 過 一個月 即 可 產下 一對 兔寶寶。 不考慮兔子死亡的條件下， 試 問 過了 n 個月後， 會 有 幾對 兔子? 將 每個月 月底 的 兔子 總對數 列成表如下：

月數	00	01	02	03	04	05	06	07	08	09
新生兔	0	1	0	1	1	2	3	5	8	13
成熟兔	0	0	1	1	2	3	5	8	13	21
總數	0	1	1	2	3	5	8	13	21	34

由上表可得兔子總對數就是一個費氏數列： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

設 Fib(n) 表第 n 個 月 兔子的總對數， 由 上表 可得

                           0,                                      當 n = 0,  　(起始條件)
Fib(n) =｛      1,                                      當 n = 1, 　  (起始條件)
                      Fib(n-1) + Fib(n-2) ,    當 n > 1.     　(分而治之)

試著自己完成程式碼。

VB2008 程式碼

Q5:  十進位數值轉二進位字串

 我們有Hex(N)和Oct(N)可以將數值N分別轉為16進位字串和轉為8進位字串。同樣地，也可以用遞迴函式來完成轉為２進位字串的函數--Ｂｉｎ（Ｎ）。

　　　　　　　　　Ｎ, 　　　　　　當 N < 2 　　(起始條件)
Bin(N) = ｛
                          Bin(N \ 2) & (N mod 2) 　　當 N >=2　　(分而治之)

VB的程式碼如下：

VB2008 程式碼

更多的用遞迴定義可以解決的題目請參考 ： 程式設計問題集