1.3.1 什么是遞歸

我們知道，用解析法表示函數(shù)常有：顯函數(shù)形式y= f（x）、隱函數(shù)形式 f（x,y）=0、參數(shù)方程形式（t 為參數(shù)）。在學習數(shù)列時，通項公式可確定一個數(shù)列，遞推公式也可確定數(shù)列。如斐波那契數(shù)列（1,1,2,3,5,8,13,21,…）是用a1=1、a2=1以及當n＞2時， an=an?1+an?2定義的數(shù)列。函數(shù)也有遞歸定義形式，如 f （n）=2f （n?1）+1。計算機術(shù)語中，實現(xiàn)某些功能的程序段也稱為函數(shù)。各種計算機高級語言都有函數(shù)的嵌套調(diào)用和遞歸調(diào)用，什么是遞歸呢？

1.遞歸

自己調(diào)用自己，稱為遞歸。自己調(diào)用自己的函數(shù)，稱為遞歸函數(shù)。遞歸函數(shù)包括直接遞歸和間接遞歸。直接遞歸是指函數(shù)F的代碼中直接包含了調(diào)用F的語句，而間接遞歸是指函數(shù)F調(diào)用了函數(shù)G,G又調(diào)用了H，如此進行下去，直到F又被調(diào)用。

如求n的階乘運算，定義：n!=（n?1）!×n。定義中n！與（n?1）！的算法是相同的，本質(zhì)上它們是同一函數(shù)，求n!，先要求（n?1）!，所以，階乘函數(shù)體現(xiàn)了自己調(diào)用自己。

例1.10 由初值y 0 =1.41和遞推關系yn =10 yn?1?1（n=1, 2, 3, 4, …）確定的數(shù)列（函數(shù)），設f （n）=yn，則yn-1=f （n?1），本質(zhì)上函數(shù)f （n）與f （n?1）是相同的。所以，這個函數(shù)的遞歸定義可表示為

其中，f（n）=10 f（n?1）?1為遞歸關系，f （0）=1.41為遞歸的初始條件。遞歸定義中這兩個條件缺一不可。如果缺少最初的項，即使已知遞歸關系，也不能求出遞歸關系中包含的各項的值。類似的，由初值 x1=1和遞推關系確定的函數(shù)的遞歸定義是

一般的，遞歸函數(shù)包含初始條件和遞歸表達式，可以用如下形式表達。

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

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

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

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

2.遞歸算法的基本思想與構(gòu)成

遞歸方法實際上體現(xiàn)了“以此類推”“用同樣的步驟重復”這樣的思想，是算法和程序設計中的一種重要技術(shù)。如在“s（n）=s（n?1）+n=1+2+…+n”這個語句中，我們求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)用過程可以看到，遞歸算法需要具備的兩個重要條件。

（1）自身調(diào)用的語句，如s（n）=s（n?1）+n；

（2）遞歸終止條件（即已解決的基礎問題），如s（1）=1。

3.遞歸的邏輯過程

計算機執(zhí)行遞歸算法程序時，總是在進行“調(diào)用”與“返回”，程序運行過程是先“調(diào)用”后“返回”。

調(diào)用過程：

每一次調(diào)用自身，參數(shù)值逐漸變小，直到調(diào)用已知條件，即遞歸終止條件，調(diào)用結(jié)束。

如設f（n）=n!，求5!，分別調(diào)用f（5）,f（4）,f（3）,f（2）,f（1）,f（5）=f（4）×5,f（4）=f（3）×4,f（3）=f（2）× 3,f（2）=f（1）×2,f（1）=1。

返回過程：

從已知條件出發(fā)，按“調(diào)用”的逆過程，逐步求值返回。從 f（1）出發(fā)，返回到 f（2）,f（2）的值返回到 f（3）,f（3）的值返回到 f（4）,f（4）的值返回到 f（5），求得結(jié)果。計算機高級語言中有返回語句（return）來指示如何返回（在哪里調(diào)用了就返回到調(diào)用地點）。

計算機執(zhí)行遞歸算法程序時如圖1.11所示。

4.遞歸算法的優(yōu)缺點

遞歸算法的優(yōu)點：可以用簡單的程序來解決某些復雜的計算問題，使源程序非常簡潔。有一些算法本質(zhì)上只有遞歸算法。

遞歸算法的缺點：運算量較大，消耗較多的內(nèi)存和運行時間，且效率不高。

例1.11 遞歸定義的圖形——Koch曲線。

Koch曲線最初形式是一條線段，由G0表示，如圖1.12所示。

將線段3等分，把中間部分用兩條等長的線段代替，被代替的線段與兩條新增線段組成一個等邊三角形，得到G1，如圖1.13所示。

將G1中的每一段線段按上述方法修改，得到G2，如圖1.14所示。

將G2中的每一段線段按上述方法修改，如圖1.15所示。如此一直不斷修改下去，最后得到的圖形稱為Koch曲線。

Koch曲線是以一條線段為基本圖形元素，用相同的規(guī)則對每一條線段進行修改，分割成更小的部分而生成的有趣圖形。生成Koch曲線的遞歸算法需要考慮：

（1）由G0得到G1產(chǎn)生了5個點P1、P2、P3、P4、P5（見圖1.16），其中P1、P5是最初線段的2個端點，P2、P3、P4是修改圖形依次插入的3個端點。P2位于P1右側(cè)線段的處，P4位于P1右側(cè)線段的處，P3由P4繞P2逆時針旋轉(zhuǎn)得到。所以，由線段兩個端點坐標可表示插入的三個點的坐標。旋轉(zhuǎn)矩陣。每次圖形迭代，只需確定和修改P1、P5的坐標。

（2）Koch曲線形成過程中，kn表示第n次迭代產(chǎn)生的結(jié)點數(shù)，則第n+1次迭代產(chǎn)生結(jié)點數(shù)目變化規(guī)律為：kn+1=4kn?3。

Koch曲線的遞歸算法定義為；

初始條件：P1、P5的坐標。

遞歸表達式：計算下一次結(jié)點數(shù)kn+1=4kn?3，計算插入結(jié)點坐標：

旋轉(zhuǎn)矩陣。

數(shù)學中還有許多用相同方法遞歸生成的圖形，如謝爾賓斯基三角形（Sierpinski Triangle）是一種分形，由波蘭數(shù)學家謝爾賓斯基在1915年提出，如圖1.17所示。