朱冰桂 改花

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

【關(guān)鍵詞】遞歸；遞歸算法；函數(shù)；數(shù)列

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

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

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

一、遞歸的基本思想

在中學(xué)學(xué)習(xí)數(shù)列知道，數(shù)列有用通項公式定義也有用遞推式定義.

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

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

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

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

一般的遞歸函數(shù)可以用如下形式表達(dá)：a1=A，

an+1=f(n，an).

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

與遞歸函數(shù)類似的說法，還有：

遞歸調(diào)用：在函數(shù)內(nèi)部發(fā)出調(diào)用自身的操作.

遞歸方法：通過函數(shù)或過程調(diào)用自身將問題轉(zhuǎn)換為本質(zhì)相同但規(guī)模較小的子問題的方法.

遞歸算法：直接或者間接地調(diào)用自身的算法.

二、遞歸算法的基本思想

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

三、遞歸算法舉例

例1已知s(n)=1+2+3+…+n=s(n-1)+n，當(dāng)我們?nèi)デ髎(n)時，我們是先求出s(n-1)，然后再算出s(n)，具體語句為：s(n)=s(n-1)+n.

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

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

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

解在遞推公式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.

因此這個數(shù)列的前五項都是2.

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

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

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.

可見，遞歸函數(shù)除了和相應(yīng)的遞推式有關(guān)外，不同的開始項，也會使結(jié)果有很大不同.

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

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

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

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

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

2222222

3633333

41244444

52055555

63066666

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

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

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

【參考文獻(xiàn)】

王信峰.計算機數(shù)學(xué)基礎(chǔ).北京：高等教育出版社，2009.