遞推法和遞歸法-tft每日頭條

遞推法和遞歸法?這兩個概念其實應該從不同維度，或者說不同學科去理解應該比較好，我來為大家科普一下關于遞推法和遞歸法?以下内容希望對你有幫助!

遞推法和遞歸法

這兩個概念其實應該從不同維度，或者說不同學科去理解應該比較好。

1、遞推:其對應英文應該是recurrence relation(Inductive)，即遞推關系。什麼是遞推關系呢？從數學角度，遞推關系往往可以用數學公式來表示。比如，高中學的等比數列，a1=1, an=再比如fibonacci，Fn = Fn-1 Fn-2.遞推可以理解是數學上的概念。從已知到未知，從1 往 n推(未知)。

遞進依次推算

2、遞歸:對應英文recursion,這是一個計算機科學裡的概念，其定義為函數自己調用自己。計算機科學裡除了遞歸，還有一個是叠代，它們和遞推三者的關系，可以理解為：

在編程裡,遞推關系可以通過遞歸或者叠代來實現,但是遞歸和叠代又不僅僅隻能用來實現遞推關

從未知到已知 Recursive是從n(未知)往1推, 再層層返回

歸納

3.叠代（輾轉） --Iterative 不斷将結果當做變量帶入，就叫叠代

叠代與遞歸： 1，從程序上看，遞歸表現為自己調用自己，叠代則沒有這樣的形式。 2，遞歸是從問題的最終目标出發，逐漸将複雜問題化為簡單問題，最終求得問題是逆向的。叠代是從簡單問題出發，一步步的向前發展，最終求得問題。是正向的。 3，遞歸中，問題的n要求是計算之前就知道的，而叠代可以在計算中确定，不要求計算前就知道n。 4，一般來說，遞推的效率高于遞歸（當然是遞推可以計算的情況下）

遞歸：

int fib(int n){

if(n>1) return fib(n-1) fib(n-2);

else return n; // n = 0, 1時給出recursion終止條件

}

叠代：

int fib(int n){

int i, temp0, temp1, temp2;

if(n<=1) return n;

temp1 = 0;

temp2 = 1;

for(i = 2; i <= n; i ){

temp0 = temp1 temp2;

temp2 = temp1;

temp1 = temp0;

}

return temp0;

}