金淵智

（三門峽職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院，河南三門峽472000）

0 引言

由于遞歸具有直觀、易理解等特性，因此，在程序設(shè)計時，我們經(jīng)常使用遞歸來解決某些特定問題。遞歸[1-3]（Recursion）即某個函數(shù)（或功能）一次或多次地在函數(shù)體內(nèi)調(diào)用自身來解決相關(guān)子問題。當(dāng)一個問題規(guī)模較大時，可以通過遞歸方法將問題規(guī)模逐步減小，最后再合并所有的遞歸結(jié)果，得出整個問題的解。

將函數(shù)的遞歸調(diào)用寫成方程的形式就是遞推方程[4（]Recurrence Equation）。其數(shù)學(xué)定義是：設(shè)序列a0,a1,a2…,an,…,簡記為 {an}，一個把an與某些個ai(i＜n)聯(lián)系起來的等式叫做關(guān)于序列 {an}的遞推方程。當(dāng)給定遞推方程和適當(dāng)?shù)某踔?，就唯一地確定了序列。

在計算機算法分析和程序設(shè)計中，使用遞歸技術(shù)往往使得函數(shù)的定義和算法的描述非常簡潔，通俗易懂，但是有許多問題隨著問題規(guī)模的增大，計算量呈指數(shù)形式增長，那么再高的CPU處理速度，也無法滿足人們對算法執(zhí)行時間的需求。因此在處理實際問題時，通常將時間復(fù)雜度為指數(shù)級別的算法先求出遞推方程的解，再來對算法進行設(shè)計、改進和效率評估。

常見遞推方程的求解方法有迭代法、嘗試法、遞歸樹和主公式法等。本文主要討論特征方程法和生成函數(shù)法，利用Hanoi塔的例子分別驗證了這兩種方法的正確性。最后利用MATLAB程序測試了Hanoi塔的遞歸函數(shù)運行時間以及求解方程后的程序運行時間。

1 常系數(shù)線性遞推方程的解法

文獻[5]給出常系數(shù)線性遞推方程的一般定義：

其中a1,a2,…,ak為常數(shù)，ak≠0，當(dāng)f(n)=0稱為k階常系數(shù)線性齊次遞推方程，b0,b1,b2,…,bk-1為k個初值。當(dāng)f(n)≠0稱為k階常系數(shù)線性非齊次遞推方程。

公式（1）的齊次特征方程為

該特征方程的根就是原遞推方程的特征根，根據(jù)方程階的不同，公式（2）可能多重根，利用多重根來構(gòu)造通解的線性組合，然后再根據(jù)初值列出方程組，求出待定常數(shù)。如果構(gòu)造的線性組合有兩個或多個線性相關(guān)的話，就無法求出待定系數(shù)。對于非齊次的情況可以通過先求齊次通解再加上一個非齊特解來構(gòu)造。

Hanoi塔的遞推方程如下

根據(jù)定義這是一個非齊次方程，其齊次特征方程為：x-2=0，即x=2，因此構(gòu)造線性無關(guān)的通解是c2n，設(shè)P為原方程的特解，代入原方程得

即P=-1，再加上齊次通解既是公式（3）的解

再代入初值T(1)=1，得c=1，最終公式（3）的解

2 利用生成函數(shù)求解遞推方程

生成函數(shù)[6]也可以用于求解遞推方程。一個序列對應(yīng)一個生成函數(shù)，同時一個序列可以滿足某個遞推關(guān)系，因此，可以將遞推關(guān)系表示成生成函數(shù)，然后在利用生成函數(shù)與冪級數(shù)的關(guān)系來求解遞推方程。對于公式（3）Hanoi塔的例子使用生成函數(shù)求解的過程如下：

1）先計算生成函數(shù)

整理得

2）用生成函數(shù)表達遞推序列

與前述方法求解結(jié)果一致。

3 求解遞推方程對于程序設(shè)計的意義

如果要編寫計算Hanoi塔盤子的移動次數(shù)的程序，最簡單的就是使用遞推公式編寫遞歸函數(shù)，

其中xn項的系數(shù)就是遞推方程的解，即其MATLAB程序代碼如下：

隨著問題規(guī)模n（盤子個數(shù)）的增加，這個遞歸函數(shù)的計算量程指數(shù)級增長，這是我們無法接受的。印度僧侶預(yù)測，將64盤子轉(zhuǎn)移完畢，就是世界末日?？梢姰?dāng)n=64時問題的規(guī)模已經(jīng)相當(dāng)大了。那么，利用公式（8）遞推方程的求解結(jié)果，我們很容易計算盤子的移動次數(shù)，其MATLAB的程序代碼如下：

為了程序計時，引入t0和t1變量。為了對比遞歸程序和求解遞推方程后的程序效率，對不同大小的n做了實驗，數(shù)據(jù)如表1所示。

表1 遞歸程序與求解方程后的程序運行時間對比

其中的“0”表示時間太短，MATLAB系統(tǒng)無法計時，“-”表示時間過長，大于100分鐘。由此可以看出，當(dāng)n=25兩種方法的求解用時已經(jīng)差距非常大了；當(dāng)n=35時，遞歸算法用時已經(jīng)接近80分鐘；當(dāng)n=40時，實驗用的計算機已經(jīng)無法快速計算遞歸算法了。求解遞歸方程后的程序運行時間幾乎全部為“0”秒，當(dāng)n=64時，若采用配置較高的計算機，程序用時也是“0”秒。

4 結(jié)束語

由于遞推方程的類型較多，求解的方法很難統(tǒng)一，因此對于遞推方程解法的研究從未停止。本文討論了兩種特殊的遞推方程解法，對于非數(shù)學(xué)領(lǐng)域，特別是計算機程序員有一定的參考價值。最后通過MATLAB實例仿真對比，論證了求解遞推方程的必要性和現(xiàn)實意義。因此，在程序設(shè)計時盡量避免使用遞歸算法，可以先將遞歸算法利用求解遞推方程轉(zhuǎn)化為非遞歸算法，再編寫程序代碼，以提高程序的執(zhí)行效率。