遞推算法

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

基本介紹

• 中文名：遞推算法
• 外文名：Recursion method
• 學科：數學
• 分類：順推和逆推

概念基本思想

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

相較區別

遞推與遞歸的比較

相對於遞歸算法,遞推算法免除了數據進出棧的過程，也就是說,不需要函式不斷的向邊界值靠攏,而直接從邊界出發,直到求出函式值.

比如階乘函式：f(n)=n*f(n-1)

在f(3)的運算過程中,遞歸的數據流動過程如下:

f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}

而遞推如下:

f(0)-->f(1)-->f(2)-->f(3)

由此可見,遞推的效率要高一些,在可能的情況下應儘量使用遞推.但是遞歸作為比較基礎的算法,它的作用不能忽視.所以,在把握這兩種算法的時候應該特別注意。

順推法

所謂順推法是從已知條件出發，逐步推算出要解決的問題的方法叫順推。

如斐波拉契數列，設它的函式為f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。則我們通過順推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我們要求的解。

逆推法

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