標籤: 暫無標籤

1遞推的概念與基本思想

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

2遞推定義

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

3遞推與遞歸的比較

相對於遞歸演算法,遞推演算法免除了數據進出棧的過程,也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.
比如階乘函數: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)   
由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推.但是遞歸作為比較基礎的演算法,它的作用不能忽視.所以,在把握這兩種演算法的時候應該特別注意。
逆推法
所謂逆推法從已知問題的結果出發,用迭代表達式逐步推算出問題的開始的條件,即順推法的逆過程,稱為逆推。
上一篇[頻繁項集]    下一篇 [支持度]

相關評論

同義詞:暫無同義詞