遞推演演算法

遞推演演算法

遞推演演算法是一種簡單的演演算法,即通過已知條件,利用特定關係得出中間推論,直至得到結果的演演算法。遞推演演算法分為順推和逆推兩種。

概念基本思想


給定一個數的序列若存在整數n0,使當時,可以用等號(或大於號、小於號)將Hn與其前面的某些項聯繫起來,這樣的式子就叫做遞推關係。

相較區別


遞推與遞歸的比較
相對於遞歸演演算法,遞推演演算法免除了數據進出棧的過程,也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.
比如階乘函數
在f(3)的運算過程中,遞歸的數據流動過程如下:
而遞推如下:
由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推。但是遞歸作為比較基礎的演演算法,它的作用不能忽視。所以,在把握這兩種演演算法的時候應該特別注意。

順推法

所謂順推法是從已知條件出發,逐步推算出要解決的問題的方法叫順推
如斐波拉契數列,設它的函數為f(n),已知。則我們通過順推可以知道直至我們要求的解。

逆推法

所謂逆推法從已知問題的結果出發,用迭代表達式逐步推算出問題的開始的條件,即順推法的逆過程,稱為逆推