遞歸在解決某些問題的時(shí)候使得我們思考的方式得以簡化兵扬，代碼也更加精煉，容易閱讀口蝠。那么既然遞歸有這么多的優(yōu)點(diǎn)器钟，我們是不是什么問題都要用遞歸來解決呢？難道遞歸就沒有缺點(diǎn)嗎妙蔗？今天我們就來討論一下遞歸的不足之處傲霸。談到遞歸就不得不面對它的效率問題。
為什么遞歸是低效的
還是拿斐波那契（Fibonacci）數(shù)列來做例子灭必。在很多教科書或文章中涉及到遞歸或計(jì)算復(fù)雜性的地方都會將計(jì)算斐波那契數(shù)列的程序作為經(jīng)典示例狞谱。如果現(xiàn)在讓你以最快的速度用C#寫出一個(gè)計(jì)算斐波那契數(shù)列第n個(gè)數(shù)的函數(shù)（不考慮參數(shù)小于1或結(jié)果溢出等異常情況），我不知你的程序是否會和下列代碼類似：
1publicstaticulong Fib(ulong n)
2{
3return(n == 1 || n == 2) ? 1 : Fib(n - 1) + Fib(n - 2);
4}
這段代碼應(yīng)該算是短小精悍（執(zhí)行代碼只有一行）禁漓，直觀清晰跟衅，而且非常符合許多程序員的代碼美學(xué)，許多人在面試時(shí)寫出這樣的代碼可能心里還會暗爽播歼。但是如果用這段代碼試試計(jì)算Fib(1000)我想就再也爽不起來了伶跷，它的運(yùn)行時(shí)間也許會讓你抓狂。
看來好看的代碼未必中用秘狞，如果程序在效率不能接受那美觀神馬的就都是浮云了叭莫。如果簡單分析一下程序的執(zhí)行流，就會發(fā)現(xiàn)問題在哪烁试，以計(jì)算Fibonacci(5)為例：
從上圖可以看出雇初，在計(jì)算Fib(5)的過程中，F(xiàn)ib(1)計(jì)算了兩次减响、Fib(2)計(jì)算了3次靖诗，F(xiàn)ib(3)計(jì)算了兩次，本來只需要5次計(jì)算就可以完成的任務(wù)卻計(jì)算了9次支示。這個(gè)問題隨著規(guī)模的增加會愈發(fā)凸顯刊橘，以至于Fib(1000)已經(jīng)無法再可接受的時(shí)間內(nèi)算出。
我們當(dāng)時(shí)使用的是簡單的用定義來求 fib(n)颂鸿，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)促绵。這樣的想法是很容易想到的，可是仔細(xì)分析一下我們發(fā)現(xiàn)，當(dāng)調(diào)用fib(n-1)的時(shí)候败晴，還要調(diào)用fib(n-2)浓冒，也就是說fib(n-2)調(diào)用了兩次，同樣的道理位衩，調(diào)用f(n-2)時(shí)f(n-3)也調(diào)用了兩次裆蒸，而這些冗余的調(diào)用是完全沒有必要的熔萧√锹浚可以計(jì)算這個(gè)算法的復(fù)雜度是指數(shù)級的。
改進(jìn)的斐波那契遞歸算法
那么計(jì)算斐波那契數(shù)列是否有更好的遞歸算法呢佛致？ 當(dāng)然有贮缕。讓我們來觀察一下斐波那契數(shù)列的前幾項(xiàng)：
11, 1, 2, 3, 5, 8, 13, 21, 34, 55 …
注意到?jīng)]有，如果我們?nèi)サ羟懊嬉豁?xiàng)俺榆，得到的數(shù)列依然滿足f(n) = f(n-1) – f(n-2), (n>2)感昼，而我們得到的數(shù)列是以1，2開頭的罐脊。很容易發(fā)現(xiàn)這個(gè)數(shù)列的第n-1項(xiàng)就是原數(shù)列的第n項(xiàng)定嗓。怎么樣，知道我們該怎么設(shè)計(jì)算法了吧萍桌？我們可以寫這樣的一個(gè)函數(shù)宵溅，它接受三個(gè)參數(shù)，前兩個(gè)是數(shù)列的開頭兩項(xiàng)上炎，第三個(gè)是我們想求的以前兩個(gè)參數(shù)開頭的數(shù)列的第幾項(xiàng)恃逻。
1intfib_i(inta,intb,intn);
在函數(shù)內(nèi)部我們先檢查n的值，如果n為3則我們只需返回a+b即可藕施，這是簡單情境寇损。如果n>3，那么我們就調(diào)用f(b, a+b, n-1)裳食，這樣我們就縮小了問題的規(guī)模（從求第n項(xiàng)變成求第n-1項(xiàng)）矛市。好了，最終代碼如下：
1intfib_i(inta,intb ,intn)
2{
3if(n == 3)
4returna+b;
5else
6returnfib_i(b, a+b, n-1);
7}
這樣得到的算法復(fù)雜度是O(n)的诲祸。已經(jīng)是線性的了浊吏。它的效率已經(jīng)可以與迭代算法的效率相比了，但由于還是要反復(fù)的進(jìn)行函數(shù)調(diào)用烦绳，還是不夠經(jīng)濟(jì)卿捎。
遞歸與迭代的效率比較
我們知道，遞歸調(diào)用實(shí)際上是函數(shù)自己在調(diào)用自己径密，而函數(shù)的調(diào)用開銷是很大的午阵，系統(tǒng)要為每次函數(shù)調(diào)用分配存儲空間，并將調(diào)用點(diǎn)壓棧予以記錄。而在函數(shù)調(diào)用結(jié)束后底桂，還要釋放空間植袍，彈棧恢復(fù)斷點(diǎn)籽懦。所以說于个，函數(shù)調(diào)用不僅浪費(fèi)空間，還浪費(fèi)時(shí)間暮顺。
這樣厅篓，我們發(fā)現(xiàn)，同一個(gè)問題捶码，如果遞歸解決方案的復(fù)雜度不明顯優(yōu)于其它解決方案的話羽氮，那么使用遞歸是不劃算的。因?yàn)樗暮芏鄷r(shí)間浪費(fèi)在對函數(shù)調(diào)用的處理上惫恼。在C++中引入了內(nèi)聯(lián)函數(shù)的概念档押，其實(shí)就是為了避免簡單函數(shù)內(nèi)部語句的執(zhí)行時(shí)間小于函數(shù)調(diào)用的時(shí)間而造成效率降低的情況出現(xiàn)。在這里也是一個(gè)道理祈纯，如果過多的時(shí)間用于了函數(shù)調(diào)用的處理令宿，那么效率顯然高不起來。
舉例來說腕窥，對于求階乘的函數(shù)來說粒没，其迭代算法的時(shí)間復(fù)雜度為O(n)：
01intfact(n)
02{
03inti;
04intr = 1;
05for(i = 1; i < = n; i++)
06{
07r *= i;
08}
09returnr;
10}
而其遞歸函數(shù)的時(shí)間復(fù)雜度也是O(n)：
1intfact_r(n)
2{
3if(n == 0)
4return1;
5else
6returnn * f(n);
7}
但是遞歸算法要進(jìn)行n次函數(shù)調(diào)用，而迭代算法則只需要進(jìn)行n次迭代而已油昂。其效率上的差異是很顯著的革娄。
小結(jié)
由以上分析我們可以看到，遞歸在處理問題時(shí)要反復(fù)調(diào)用函數(shù)冕碟，這增大了它的空間和時(shí)間開銷拦惋，所以在使用迭代可以很容易解決的問題中，使用遞歸雖然可以簡化思維過程安寺，但效率上并不合算厕妖。效率和開銷問題是遞歸最大的缺點(diǎn)。
雖然有這樣的缺點(diǎn)挑庶，但是遞歸的力量仍然是巨大而不可忽視的言秸，因?yàn)橛行﹩栴}使用迭代算法是很難甚至無法解決的（比如漢諾塔問題）。這時(shí)遞歸的作用就顯示出來了迎捺。
