遞歸算法案例——數列到函數

朱冰桂 改花

【摘要】遞歸算法是一種直接或者間接地調用自身的算法.在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解.遞歸過程一般通過函數或子過程來實現. 遞歸算法：在函數或子過程的內部，直接或者間接地調用自己的算法.本文通過具體的數學例子來體現這一基本思想，對第二個例子進行拓展，揭示了遞推關系數列的函數實質.

【關鍵詞】遞歸；遞歸算法；函數；數列

遞歸函數（recursive function）是一個自己調用自己的函數.遞歸函數包括兩種：直接遞歸（direct recursion）和間接遞歸（indirect recursion）.直接遞歸是指函數F的代碼中直接包含了調用F的語句，而間接遞歸是指函數F調用了函數G，G又調用了H，如此進行下去，直到F又被調用.

還有些數據結構如二叉樹，結構本身固有遞歸特性；此外，有一類問題，其本身沒有明顯的遞歸結構，但用遞歸程序求解比其他方法更容易編寫程序，如八皇后問題、漢諾塔問題等.

遞歸時常用的編程技術，其基本思想就是“自己調用自己”，一個使用遞歸技術的方法即是直接或間接地調用自身的方法.遞歸方法實際上體現了“以此類推”“用同樣的步驟重復”這樣的思想，它可以用簡單的程序來解決某些復雜的計算問題，但是運算量較大.正因為遞歸程序的普遍性，我們應該學會使用遞歸來求解問題.在直接遞歸程序與間接遞歸中都要實現當前層調用下一層時的參數傳遞，取得下一層所返回的結果，并向上一層調用返回當前層的結果.至于各層調用中現場的保存與恢復，均由程序自動實現，不需要人工干預.因此，在遞歸程序的設計中關鍵是找出調用所需要的參數、返回的結果及遞歸調用結束的條件.如在階乘函數Fact(n)中，各層要求傳遞一個自然數n，返回n*Fact(n-1)，遞歸調用結束的條件是n=0，據此，可以方便地寫出它的對應程序

一、遞歸的基本思想

在中學學習數列知道，數列有用通項公式定義也有用遞推式定義.

如an=2n；a0=a1=1，a2=2，n>2時，an=an-1+an-2.

同樣的，表示函數可以用顯式表達式、隱式方程、參數方程形式和遞歸式.

所謂遞歸就是自己調用自己，遞歸包含兩種：直接遞歸和間接遞歸.

遞歸函數：用函數自身給出定義的函數，稱為遞歸函數.

一般的遞歸函數可以用如下形式表達：a1=A，

an+1=f(n，an).

遞歸函數有兩個要素：初始項、遞推式.

與遞歸函數類似的說法，還有：

遞歸調用：在函數內部發出調用自身的操作.

遞歸方法：通過函數或過程調用自身將問題轉換為本質相同但規模較小的子問題的方法.

遞歸算法：直接或者間接地調用自身的算法.

二、遞歸算法的基本思想

遞歸方法實際上體現了“以此類推”、“用同樣的步驟重復”這樣的思想，是算法和程序設計中的一種重要技術.

三、遞歸算法舉例

例1已知s(n)=1+2+3+…+n=s(n-1)+n，當我們去求s(n)時，我們是先求出s(n-1)，然后再算出s(n)，具體語句為：s(n)=s(n-1)+n.

在這個語句中，我們調用s(n)求其值的時候，必須先調用s(n-1)得到其值，而要得到s(n-1)，又必須調用s(n-2)得到其值，同樣，要求s(n-2)又要調用s(n-3)，依次類推，一直要遞推到s(2)=s(1)+2，由于s（1）已知為1，所以可以得到s（2），從而得到s（3），這樣一直可以得到s（n）.

這個遞歸算法中，自身調用的語句是：s（n）=s（n-1）+n，結束遞歸的邊界條件是：s（1）=1.

例2數列f(n)滿足f(n+1)=2+f(n)及f(1)=2，求這個數列的前五項.

解在遞推公式f(n+1)=2+f(n)中，令n=1，可得f(2)=2+f(1)=2+2=2.

再令n=2，3，4，5，

可得f(5)=f(4)=f(3)=2+f(2)=2+2=2.

因此這個數列的前五項都是2.

注容易看出這個數列的各項都是2，即2，2，2，2，2，2，…

如果我們令f(1)=1，則可以求出該數列的前五項分別為：

f(2)=2+f(1)=3，

f(3)=2+f(2)=2+3，

f(4)=2+f(3)=2+2+3，

f(5)=2+f(4)=2+2+2+3.

可見，遞歸函數除了和相應的遞推式有關外，不同的開始項，也會使結果有很大不同.

在上例中，如果我們修改遞推式，改為f(n+1)=y+f(n)，且令f(1)=3，則當y=6時，我們可以得到f(5)=f(4)=f(3)=f(2)=6+f(1)=3，即數列的每一項都是3.

如果令f(1)=4，則當y=12時，我們可以得到f(5)=f(4)=f(3)=f(2)=6+f(1)=4，即數列的每一項都是4.

如果令f(1)=5，則當y=20時，我們可以得到f(5)=f(4)=f(3)=f(2)=6+f(1)=5，即數列的每一項都是5.

對以上各種情況我們列個表格，并設f(1)=x.

xyf(1)f(2)f(3)f(4)f(5)

2222222

3633333

41244444

52055555

63066666

可以發現當x，y滿足一定的關系時，所得數列是常數列，即當y=x(x-1)時，數列為常數列.數列是自變量為自然數的函數這一思想得到體現.

如果我們把遞推式改為f(n+1)=3y+f(n)且令f(1)=x2，我們可以得到當y=x2(x-1)時，數列是值為x的常數列.

綜上所述，我們可以得到遞歸思想最終還是一種函數的思想，只不過在中學階段接觸到的是一些具體的數列例子，讓同學們感到很是新鮮好奇.而在高等數學階段，特別是對于計算機專業的學生，掌握遞歸思想意義重大，可以幫助他們創新，建立新模型，如果把數學中的函數思想很好地融入進去，可以拓展同學們的思路，降低問題的難度.

【參考文獻】

王信峰.計算機數學基礎.北京：高等教育出版社，2009.