遞歸是壹個簡單而困難的問題。我覺得有必要總結壹下。
首先，了解遞歸的定義。遞歸意味著直接或間接調用自己。至於什麽時候用遞歸，遞歸和非遞歸有什麽區別？這是另壹個很難掌握的問題，理解遞歸調用就更難了。下面我們從程序+圖形的角度對遞歸做壹個全面的闡述。
讓我們從常見的遞歸問題開始:
1分層函數
# include & ltiostream & gt
使用命名空間std
int階乘(int n)
{
如果(n == 0)
{
返回1；
}
其他
{
int result =階乘(n-1)；
返回n *結果；
}
}
int main()
{
int x =階乘(3)；
cout & lt& ltx & lt& ltendl
返回0；
}
這是壹個遞歸層次函數的實現。很多朋友就是知道這是怎麽實現的，也知道是反復遞歸調用的結果。但是他們有點不清楚中間發生了什麽。讓我們用壹個圖表來說明這壹點:
根據上圖，可以清楚的看到這個函數的執行流程。我們的層次函數factorial被調用了四次，可以看到前壹次調用在調用後的調用中並沒有退出。他們都存在於記憶中。可見這是壹種資源的浪費。我們這次的參數是3。如果我們通過10000呢？那麽結果可想而知。肯定是溢出來了。用int類型接收結果就行了，何況10000。100會溢出。就算不溢出，我覺得也絕對是浪費資源。我們可以粗略估算壹下:每次函數調用單個變量所需的內存是:兩個int變量。n和結果。在32位機器上需要8B。那麽10000就需要10001個函數調用。需要10001 * 8/1024 = 78kb。這只是變量需要的內存空間。其他函數在調用函數時還是需要占用內存空間的。可見遞歸調用產生了很大的開銷。
斐波納契數列
中間纖維(中間纖維)
{
如果(n & lt= 1)
{
返回n；
}
其他
{
返回光纖(n-1) +光纖(n-2)；
}
}
這個函數的遞歸和上面的有點不同。每次調用該函數，都會引起另外兩次調用。最後會逐步返回結果。
我們可以看到，當這個遞歸函數也調用後買的函數時，前壹個不退出而是等待後壹個結果，最後求總結果。這就是遞歸。
三
# include & ltiostream & gt
使用命名空間std
void recursiveFunction1(整數)
{
if(num & lt；5)
{
cout & lt& ltnum & lt& ltendl
recursive function 1(num+1)；
}
}
void recursiveFunction2(整數)
{
if(num & lt；5)
{
recursive function 2(num+1)；
cout & lt& ltnum & lt& ltendl
}
}
int main()
{
recursive function 1(0)；
recursive function 2(0)；
返回0；
}
運行結果:
1
2
三
四
四
三
2
1
這個程序中有兩個遞歸函數。傳遞相同的參數，但是它們的輸出結果正好相反。理解這兩個函數的調用過程可以幫助我們理解遞歸:
以上三個函數的遞歸調用過程我想我能理解，遞歸調用妳也差不多理解了。並且從上面的遞歸調用中，我們可以總結出壹個遞歸的規律:它是壹步壹步調用的，當函數結束時，按照從最後到前面的逆序結束。這種方式非常耗費資源和時間。但有時遞歸編寫的程序很容易理解和閱讀。
為什麽使用遞歸:
有時候，遞歸編寫的1程序很容易理解和閱讀。
有些問題只能用遞歸來解決。非遞歸方法無法實現。比如河內塔。
遞歸的條件:
並不是說所有的問題都可以用遞歸來解決，而是必須滿足壹定的條件。也就是說，有壹個退出點。也就是說，當滿足壹定條件時，程序可以結束，從而完成遞歸調用，否則將陷入無限遞歸調用。而這個條件必須是可以達到的。
遞歸的優點是什麽？
易於閱讀和理解，代碼壹般較短。
遞歸的缺點是什麽？
占用大量內存資源，耗時，效率低。
所以我們寫程序的時候，不要輕易使用遞歸。雖然有它的優點，但是要權衡可讀性，空間，效率。總的來說，我們還是用非遞歸的方法來解決問題。如果壹個算法是非遞歸的，這是很難理解的。我們可以用遞歸，比如二叉樹的遍歷算法。非遞歸算法很難理解，但比遞歸算法容易理解得多。
對於遞歸調用的問題，我們前段時間寫圖形程序的時候，四加壹填充算法中有壹個就是用了遞歸的方法。因此，當要填充的圖形稍大時，程序會自動關閉。這不是壹個人的問題，但那是每個人都寫的。當時我們給出的解釋是堆棧溢出。反復遞歸調用占用內存資源過多，導致堆棧溢出，程序沒有內存資源執行，從而被操作系統強制關閉。這是壹個真實的例子。所以我們在使用遞歸的時候需要反復權衡。