2019-11-14 seo達(dá)人
1，從程序上看，遞歸表現(xiàn)為自己調(diào)用自己，遞推則沒(méi)有這樣的形式。
2，遞歸是從問(wèn)題的最終目標(biāo)出發(fā)，逐漸將復(fù)雜問(wèn)題化為簡(jiǎn)單問(wèn)題，最終求得問(wèn)題
是逆向的。遞推是從簡(jiǎn)單問(wèn)題出發(fā)，一步步的向前發(fā)展，最終求得問(wèn)題。是正向的。
3，遞歸中，問(wèn)題的n要求是計(jì)算之前就知道的，而遞推可以在計(jì)算中確定，不要求計(jì)算前就知道n。
4，一般來(lái)說(shuō)，遞推的效率高于遞歸（當(dāng)然是遞推可以計(jì)算的情況下）
最容易理解就是結(jié)合一個(gè)經(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推, 再層層返回
藍(lán)藍(lán)設(shè)計(jì)的小編 http://www.cqzjtgb.com