關于遞歸與遞推的討論

摘 要: 遞推一般用循環來解決，從已知條件到未知逐漸接近結果;遞歸一般自己調用自己，從未知到已知，把規模大的、較難解決的問題變成規模較小的、易解決的同一問題。規模較小的問題又變成規模更小的問題，并且小到一定程度可以直接得出它的解，從而得到原來問題的解。

關鍵詞: 遞歸 遞推 算法

一、前言

遞歸和遞推都是算法設計中的難點，算法又十分相近，很多學生誤認為是一回事，非常容易混淆。其實它們之間既有相似點，又有明顯的區別。下面筆者從一個簡單的階乘實例進行分析。

二、用遞歸法解階乘

數學上經常這樣描述:f(n)=1n=0，n=1n×f(1-1)n>1。

算法設計:

long f(int n)

{if(n=0||n=1)

return 1;

else

return n*f(n-1);

}

以上算法中，在調用函數f(n)的過程中又調用自身f(n-1)，這樣在一個子程序(過程或函數)的定義中直接或間接地調用該子程序本身，稱為遞歸。顯然，遞歸是一種非常有用的程序設計方法。用遞歸算法編寫的程序結構清晰，具有很好的可讀性。

遞歸算法的基本思想是:把規模大的、較難解決的問題變成規模較小的、易解決的同一問題。規模較小的問題又變成規模更小的問題，并且小到一定程度可以直接得出它的解，從而得到原來問題的解。我們利用遞歸算法解題，首先要對問題的以下三個方面進行分析:

1.決定問題規模的參數。需要用遞歸算法解決的問題，其規模通常都是比較大的，在問題中決定規模大小(或問題復雜程度)的量有哪些?把它們找出來。

2.問題的邊界條件及邊界值(又叫結束條件或出口)。在什么情況下可以直接得出問題的解?這就是問題的邊界條件及邊界值。

3.解決問題的通式(又叫遞歸體)。把規模大的、較難解決的問題變成規模較小、易解決的同一問題，需要通過哪些步驟或等式來實現?這是解決遞歸問題的難點。把這些步驟或等式確定下來。

我們把以上三個方面分析好之后，就可以在子程序中定義遞歸調用。例如上面階乘的例子中:n=1或n=0時的階乘值是1，此時n為1或0就是遞歸出口。f(n)=n×f(n-1)便是遞歸體。

可見遞歸是一種思想，是一種把原問題復雜度進一步降低以后再求解的思路，這個定義本身就有“遞歸性”，遞歸性指的是一種特征:函數或者過程還是什么，自身計算的時候，調用到自身的特征。遞歸會把原問題的未知撥開“一層”，越來越接近已知，而此時遞歸算法根本沒有算出一個中間量，在遞歸深度達到最大的時候，達到已知條件，然后已知條件作為上一層的已知，一層一層地返回，最后未知就這樣被求解。另外遞歸的算法進棧和回溯思想結合。

三、用遞推法解階乘

數學上一般這樣描述:n!=1×2×3×4×…×(n-1)×n。

算法設計:

longf(int n)

{long s=1;

int i;

for(i=1;i<=n;i++)

s=s*i;

return s;

}

可見遞推也是一種思想，是從已知條件出發，用一種具體的算法，一步一步接近未知，一般采用循環結構。遞推算法在求解的過程中，每一個中間量都是已知，而且沒有重復計算，運算簡潔，但是書寫代碼和理解代碼比較難。

四、遞歸和遞推的區別

遞歸是利用子問題與父問題的關系，進而構造成有遞歸性的函數。而遞推恰恰與此相反，從已知到未知，類似于一般解數學題的思路。從未知與已知的順序上來看，它們好像是逆過程，但其實不是，遞歸把問題簡單化，抓的是問題與子問題的聯系，而遞推是把中間解推進，抓得是中間量與更靠近未知的中間量的聯系，兩者不同，所以不能看成逆過程。

我們再看一個例子:斐波那契數列:1，1，2，3，5，8，13，21……公式F(n)=F(n-1)+F(n-2)，F(1)=F(2)=1;這個公式本身是具有遞歸性的。

1.遞歸解

long f(int n)

{if(n<=2)

return 1;

else

return f(n-1)+f(n-2);

}

這行代碼充分地顯示了遞歸算法的簡潔。

2.遞推解

long f(int n)

{long t;f1=1，f2=1;

if(n<=2)reutrn 1;

for(int i=3;i<=n;i++)

{t=f1+f2;

f1=f2;

f2=t;

}

}

五、結語

由此可見，遞歸重在“歸”，你要求的是什么，就直接求什么，至于要怎么去調用、怎么去求，讓函數自己一步一步去反復調用;遞推重在“推”，是按照我們平時做數學的方法來算。編程時遞歸比較特殊，表現在函數自身調用自身，這樣編程代碼緊湊，程序的可讀性好，但效率低，還可能導致堆棧溢出，特別是遞歸層次比較多時。一般來說，遞歸程序都可以用循環程序實現，用循環程序實現雖然較難理解，但安全可靠。

參考文獻:

[1]譚浩強.C程序設計(第二版).清華大學出版社.

[2]嚴蔚敏，吳偉民.數據結構(C語言版).清華大學出版社.