遞推和遞歸的區(qū)別

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推, 再層層返回


日歷

鏈接

個(gè)人資料

存檔