引子

著名的 Hanoi 問題是這樣描述的：

［1］

漢諾塔

（港臺：

河內塔

）是根據一個傳說形成的數學問題：

有三根杆子

A,B,C

。

A

杆上有

N

個 （

N>1

） 穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至

C

杆：

每次只能移動一個圓盤；

大盤不能疊在小盤上面。

提示：可將圓盤臨時置於

B

杆，也可將從

A

杆移出的圓盤重新移回

A

杆，但都必須遵循上述兩條規則。

問：如何移？最少要移動多少次？

遞推關係總結

Hanoi問題圖示

遞推關係總結

八塊圓盤的Hanoi玩具

解：

記

f(n)

是

n

個圓盤需要從

A

搬到

C

柱所需的最小次數。整個搬運過程可以分為三個階段

將上面的

n-1

個盤從

A

移動到

B

將最下面的第

n

個盤從

A

移動到

C

將

n-1

個盤從

B

移動到

C

那麼就有下面的等式成立

f(n)=2f(n-1)+1

這個等式的意思就是：

n

個圓盤從

A

移動到

C

的次數=

n-1

個盤從

A

移動到

B

次數+ 第

n

個盤移動到

C

次數+

n-1

個盤從

B

移動到

C

次數

n

個圓盤從

A

移動到

C

的次數=

f(n)

n-1

個盤從

A

移動到

B

次數=

f(n-1)

n-1

個盤從

B

移動到

C

次數=

f(n-1)

第

n

個盤移動到

C

次數=

1

也不難理解，如果只有一個盤子，那麼我直接

A\rightarrow C

即可，即

f(1)=1

這就是一個遞迴式出現了

\begin{equation} \left\{ \begin{array}{**lr**} f(n)=2f(n-1)+1, & \\ f(1)=1. & \end{array} \right. \end{equation}\\

這個遞迴式求出來了，那麼怎麼求解呢？

還有一個著名的斐波那契數

［2］

根據高德納（Donald Ervin Knuth）的《計算機程式設計藝術》（

The Art of Computer Programming

），1150年印度數學家Gopala和金月在研究箱子包裝物件長寬剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是比薩的列奧那多（義大利人斐波那契Leonardo Fibonacci），他描述兔子生長的數目時用上了這數列：

遞推關係總結

兔子的數量就是斐波那契數

第一個月初有一對剛誕生的兔子

第二個月之後（第三個月初）它們可以生育

每月每對可生育的兔子會誕生下一對新兔子

兔子永不死去

假設在

n

月有兔子總共

a

對，

n+1

月總共有

b

對。在

n+2

月必定總共有

a+b

對：因為在

n+2

月的時候，前一月（

n+1

月）的b對兔子可以存留至第

n+2

月（在當月屬於新誕生的兔子尚不能生育）。而新生育出的兔子對數等於所有在

n

月就已存在的

a

對。

這個問題可以來畫個表

［3］

遞推關係總結

兔子數量變化

最終可以得到遞推式：

\left\{ \begin{array}{**lr**} f(n)=f(n-1)+f(n-2), n\geq3& \\ f(1)=1,f(2)=1. & \end{array} \right. \\

這個遞推關係又怎麼求解呢？

這就是接下來要說的東西了。

常係數線性齊次遞推關係的求解

定義

設

k

是給定的正整數，若數列

f(0),f(1),...f(n),...

的相鄰

k+1

項之間滿足關係

f(n)=c_1(n)f(n-1)+c_2(n)f(n-2)+...+c_k(n)f(n-k)+g(n)

對

n\geq k

成立。

若

c_k(n)\neq 0

，則稱該關係為

\{f(n)\}

的

k

階線性遞推關係。

若滿足1的情況下，還滿足

c_1(n),c_2(n),c_3(n),...c_k(n)

都是常數，則成之為為

k

階常係數線性遞推關係。

若滿足1，2的情況下，還滿足

g(n)=0

，則稱其為

k

階常係數齊次線性遞推關係。

這個定義和微分方程的定義十分類似，只不過把導數的階次換成了遞推的階次。

例子

求解斐波那契數列遞推式的解

\left\{ \begin{array}{**lr**} f(n)=f(n-1)+f(n-2), n\geq3& \\ f(1)=1,f(2)=1. & \end{array} \right. \\

列特徵方程：

x^2=x+1

，求解得到

x_1=\frac{1+\sqrt{5}}{2},x_2=\frac{1-\sqrt{5}}{2}

遞迴方程的通解為

f(n)=c_1x_1^n+c_2x_2^n=c_1\cdot(\frac{1+\sqrt{5}}{2})^n+c_2\cdot (\frac{1-\sqrt{5}}{2})^n

帶入邊界條件

f(1)=1,f(2)=1

，得到線性方程組

\left\{ \begin{array}{**lr**} c_1\cdot\frac{1+\sqrt{5}}{2}+c_2\cdot \frac{1-\sqrt{5}}{2}=1& \\ c_1\cdot(\frac{1+\sqrt{5}}{2})^2+c_2\cdot (\frac{1-\sqrt{5}}{2})^2=1. & \end{array} \right. \\

求解得到

c_1=\frac{1}{\sqrt5},c_1=-\frac{1}{\sqrt5}

\therefore f(n)=\frac{1}{\sqrt5}(x_1^n-x_2^n)=\frac{1}{\sqrt5}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)\\

這個也就是在鄧俊輝版的資料結構

［4］

第25頁推匯出來的結果。

求解遞推關係

\left\{ \begin{array}{**lr**} f(n)=4f(n-1)-4f(n-2), & \\ f(0)=1,f(1)=3. & \end{array} \right. \\

列特徵方程

x^2=4x-4

，求解得到

x_1=x_2=2

遞迴方程的通解為

f(n)=c_1x_1+c_2nx_2=c_1x_1^n+c_2nx_2^n

帶入邊界條件

f(0)=1,f(1)=3

，得到線性方程組

\left\{ \begin{array}{**lr**} c_1\cdot 2^0=1& \\ 2c_1+2c_2=3 \end{array} \right. \\

求解得到

c_1=1,c_2=\frac{1}{2}

\therefore f(n)=2^n+2^{n-1}n

求解

\left\{ \begin{array}{**lr**} g(t)=3f(t-1)+2g(t-1), &t\geq1 \\ f(t)=g(t-1),&t\geq1\\ g(0)=0,f(0)=1. & \end{array} \right. \\

對於這個方程，要先把它化成一個變數的遞推方程，由遞推式可知

f(t-1)=g(t-2)

，所以有下列關於

g

的遞推式：

\left\{ \begin{array}{**lr**} g(t)=3g(t-2)+2g(t-1)&t\geq2 \\ g(0)=0,g(1)=3. \end{array} \right. \\

這個求解就跟之前的一模一樣了。

列特徵方程：

x^2-2x-3=0

，根為

x_1=-1,x_2=3

遞迴方程的通解為：

f(n)=\frac{3}{4}\cdot 3^t-\frac{3}{4}\cdot (-1)^t

根據邊界條件列出線性方程組：

\left\{ \begin{array}{**lr**} c_1+c_2=0 \\ 3c_1-c_2=3 \end{array} \right. \Rightarrow c_1=\frac{3}{4},c_2=-\frac{3}{4}\\

\therefore g(t)=\frac{3}{4}3^t-\frac{3}{4}(-1)^t,f(t)=g(t-1)=\frac{3}{4}3^{t-1}-\frac{3}{4}(-1)^{t-1}\\

求解總結

對於

常係數線性齊次

遞推方程

f(n)=c_1f(n-1)+c_2f(n-2)+...+c_kf(n-k)

的求解步驟如下

列出特徵方程：

x^k-c_1x^{k-1}-c_2x^{k-2}-...-c_k=0,\Rightarrow x_i=q_i

，設求解的解為

q_i

寫出帶係數的通項公式：

f(n)=b_1q_1^n+b_2q_2^n+...+b_kq_k^n

代入

邊界條件

，或者叫

遞迴基

，得到一個關於

k

的線性方程組，要想有唯一解要求邊界條件的數目和冪次一致，這個原因學過線性代數肯定是沒有問題的

證明過程可以參考組合數學引論

［5］

，寫的比較清楚。

其實證明過程也可以參考微分方程的求解，兩個的求解方式有很多的相似之處。

常係數非齊次遞推關係的求解1-利用已知的解形式

定義

前面看了常係數齊次遞迴，知道了齊次是因為

g(n)=0

，那麼

g(n)\neq0

就是非齊次了。

非齊次通常是沒有普遍的解法的。

書上會給一些關於特殊的

g(n)

的解的形式，但是記憶起來比較麻煩，很容易記錯，推薦碰到非齊次的時候考慮使用生成函式來解題。生成函式的作用比記憶這些特殊解的構造要有用的多。

對於非齊次線性遞推方程寫 2 個例子。

例子

求解 Hanoi 遞推式

\begin{equation} \left\{ \begin{array}{**lr**} f(n)=2f(n-1)+1, & \\ f(1)=1. & \end{array} \right. \end{equation}\\

f

代表通解，

f

代表通解。

對於其對應的齊次線性遞迴式列特徵方程：

x-2=0\rightarrow x=2,f

計算特解：

g(n)=1

，對應著有

\beta^n

這樣形式的解的

\beta=1

，將

\beta=1

代入特徵多項式，得到

P(\beta)=\beta-2=1-2\neq0

（這個特徵多項式就是前面的特徵方程的去掉0的一個函式）。根據書上

［5］

的特解形式的對應，

遞推關係總結

對應的特解形式為

\alpha\beta^n=\alpha1^n=\alpha

，所以特解為

f

，這裡可以看出來，

f

的取值和

n

無關，所以

f

，將其帶入遞推方程

f

因此，特解為

f

，綜合非齊次特解和齊次通解可知

f(n)=b2^n-1

，代入邊界條件，有

f(0)=b2^0-1=0\rightarrow b=1

，所以，遞推關係為

f(n)=2^n-1

總結

求解非齊次遞推關係的解的時候，要先求解出對應的齊次方程帶係數的通解

f

觀察非齊次項

g(n)

的表示式是否是特殊的表示式，如果是，根據已知的特解的表達形式得到帶係數的特解

將帶係數的特解直接帶入遞推關係，代入邊界條件得到特解的係數，得到不帶係數的特解

f

將帶係數的通解和特解相加

f

帶入原來的遞推表示式中，根據邊界條件求出解的係數，這時候去掉係數的解就是遞推表示式的解。

常係數非齊次遞推關係的求解2-使用生成函式

如果不知道生成函式（或者母函式）是什麼，應該先補一下這方面的知識。

例子

還是來求解前面的 Hanoi 問題

總結

先寫到這兒，有空有人看了再往下面寫。

分析遞迴

程式實現

複雜度分析

遞迴與迭代的轉化

關係

轉化方法

參考

^

Hanoi問題維基百科

https：//zh。wikipedia。org/wiki/%E6%B1%89%E8%AF%BA%E5%A1%94

^

Fibonacci

https：//zh。wikipedia。org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97

^

陳景潤。組合數學

https：//book。douban。com/subject/10808577/

^

鄧俊輝。資料結構

https：//book。douban。com/subject/25859528/

^

a

b

組合數學引論

https：//book。douban。com/subject/4867855/