2019-11-14 seo達人
1，從程序上看，遞歸表現(xiàn)為自己調(diào)用自己，遞推則沒有這樣的形式。
2，遞歸是從問題的最終目標出發(fā)，逐漸將復雜問題化為簡單問題，最終求得問題
是逆向的。遞推是從簡單問題出發(fā)，一步步的向前發(fā)展，最終求得問題。是正向的。
3，遞歸中，問題的n要求是計算之前就知道的，而遞推可以在計算中確定，不要求計算前就知道n。
4，一般來說，遞推的效率高于遞歸（當然是遞推可以計算的情況下）
最容易理解就是結(jié)合一個經(jīng)典的例子：斐波那契數(shù)列
遞歸求解
int fib(n){
return n < 2 ? 1 : fib(n-1)+f(n-2);
}
遞推求解
int fib(int n){
int fn = 1;
int fn_1 = 0;
for(int i=0; i<n; i++) {
int t = fn
fn = fn + fn_1;
fn_1 = t;
}
return fn;
}
遞推 Inductive 是從1 往 n推(未知)
遞歸Recursive是從n(未知)往1推, 再層層返回