一、什么是遞歸函數(shù)
（1）遞歸函數(shù)即自調(diào)用函數(shù)宇立，在函數(shù)內(nèi)部直接或間接地自己調(diào)用自己踪宠，即函數(shù)的嵌套調(diào)用是函數(shù)本身。
從字面上來看遞歸妈嘹，遞即遞推柳琢，采用循環(huán)的思路來描述復(fù)雜問題的方法。在遞推階段每一個遞歸調(diào)用通過進(jìn)一步調(diào)用自己來記住這次遞歸過程，當(dāng)其中調(diào)用滿足終止條件時染厅，遞推結(jié)束痘绎。歸即回歸，函數(shù)調(diào)用已逆序的方式回歸肖粮，知道最初調(diào)用的函數(shù)返回為止孤页，此時遞歸過程結(jié)束。舉個例子：
（2）遞歸的基本原理
第一：每一級的函數(shù)調(diào)用都有自己的變量涩馆。
第二：每一次函數(shù)調(diào)用都會有一次返回行施。
第三：遞歸函數(shù)中，位于遞歸調(diào)用前的語句和各級被調(diào)用函數(shù)具有相同的執(zhí)行順序魂那。
第四：遞歸函數(shù)中蛾号，位于遞歸調(diào)用后的語句的執(zhí)行順序和各個被調(diào)用函數(shù)的順序相反。
第五：雖然每一級遞歸都有自己的變量涯雅，但是函數(shù)代碼并不會得到復(fù)制鲜结。
最后：遞歸函數(shù)中必須包含可以終止遞歸調(diào)用的語句。
（3）遞歸的優(yōu)缺點
其優(yōu)點在于為某些變成問題提供了最簡單的解決方法活逆，簡化了程序設(shè)計精刷。而缺點是一些遞歸算法會很快耗盡計算機(jī)的內(nèi)存資源。同時蔗候，使用遞歸的程序難于閱讀和維護(hù)怒允。
二、函數(shù)調(diào)用機(jī)制的說明
任何函數(shù)之間不能嵌套定義，調(diào)用函數(shù)與被調(diào)用函數(shù)之間相互獨立遞歸函數(shù)的概念用法與實例（彼此可以調(diào)用）。發(fā)生函數(shù)調(diào)用時刹衫，被調(diào)用函數(shù)中保護(hù)了調(diào)用函數(shù)的運行環(huán)境和返回地址，使得調(diào)用函數(shù)的狀態(tài)可以被調(diào)用函數(shù)運行返回完全恢復(fù)丽惶，而且該狀態(tài)與被調(diào)用函數(shù)無關(guān)。
被調(diào)用函數(shù)運行的代碼雖然是同一個函數(shù)的代碼體爬立，但由于調(diào)用點钾唬，調(diào)用時狀態(tài)，返回點的不同懦尝，可以看作是函數(shù)的一個副本知纷，與調(diào)用函數(shù)的代碼無關(guān)壤圃，所以函數(shù)的代碼是獨立的陵霉。被調(diào)用函數(shù)運行的棧空間獨立于調(diào)用函數(shù)的椢樯空間踊挠，所以與調(diào)用函數(shù)之間的數(shù)據(jù)也是無關(guān)的。函數(shù)之間考參數(shù)傳遞和返回值來聯(lián)系，函數(shù)看作為黑盒效床。
這種機(jī)制決定了 C/C++ 允許函數(shù)遞歸調(diào)用睹酌。
上面這段話的意思可以理解為，遞歸函數(shù)調(diào)用自身函數(shù)的時候剩檀，可以看作調(diào)用的是調(diào)用別的函數(shù)憋沿。
再有，被調(diào)用函數(shù)運行的椈铮空間獨立于調(diào)用函數(shù)的椃模空間 這句話如何理解？
首先运嗜，我們先說一下棧的概念：
參看：遞歸函數(shù)的概念用法與實例
參看：C語言再學(xué)習(xí) -- 內(nèi)存管理
棧是一個后進(jìn)先出(LIFO)的壓入（push）和彈出（pop）式的數(shù)據(jù)結(jié)構(gòu)壶辜。在程序運行時，系統(tǒng)每次向棧中壓入一個對象担租，然后棧指針向下移動一個位置砸民。當(dāng)系統(tǒng)從棧中彈出一個對象時，最近進(jìn)棧的對象將被彈出奋救。然后棧指針向上移動一個位置岭参。程序員經(jīng)常利用棧這種數(shù)據(jù)結(jié)構(gòu)來處理那些最適合用后進(jìn)先出邏輯來描述的編程問題。這里討論的程序中的棧每個程序中都是存在的菠镇，它不需要程序員編寫代碼去維護(hù)冗荸，而是由運行時系統(tǒng)自動處理。所謂系統(tǒng)自動維護(hù)利耍，實際上就是編譯器所產(chǎn)生的程序代碼蚌本。盡管在程序中看不到他們，但是程序員應(yīng)該對此有所了解隘梨。
再看看程序中的棧是如何工作的程癌。當(dāng)一個函數(shù)（調(diào)用者）調(diào)用另一個函數(shù)（被調(diào)用者）時，運行系統(tǒng)將把調(diào)用者的所有實參和返回地址壓入棧中轴猎，棧指針將移到合適的位置來容納這些數(shù)據(jù)嵌莉。最后進(jìn)棧的是調(diào)用者的返回地址。當(dāng)被調(diào)用這開始執(zhí)行時捻脖，系統(tǒng)把被調(diào)用者的自變量壓入棧中锐峭，并把棧指針再向下移，以保證有足夠的空間存儲被調(diào)用這聲明的所有自變量可婶。當(dāng)調(diào)用這把實參壓入棧后沿癞，被調(diào)用者就在棧中以自變量的形式建立形參。被調(diào)用這內(nèi)部的其他自變量也是存放在棧中的矛渴。由于這些進(jìn)棧操作椎扬，棧指針已經(jīng)移動所有這些局部變量之下。但是被調(diào)用者記錄了它剛開始執(zhí)行時的初始棧指針，以它為參考蚕涤，用正或負(fù)的偏移量來訪問棧中的變量筐赔。當(dāng)被調(diào)用者準(zhǔn)備返回時，系統(tǒng)彈出棧中所有的自變量揖铜，這是棧指針移動了被調(diào)用者剛開始執(zhí)行時的位置茴丰。接著被調(diào)用者返回，系統(tǒng)從棧中彈出返回地址天吓，調(diào)用者就可以繼續(xù)執(zhí)行了较沪。當(dāng)調(diào)用者繼續(xù)執(zhí)行時，系統(tǒng)還將從棧中彈出調(diào)用者的實參失仁，于是棧指針回到了調(diào)用發(fā)生前的位置尸曼。
現(xiàn)在接著說遞歸：
上面有提到了函數(shù)調(diào)用機(jī)制。遞歸之所以能實現(xiàn)萄焦，是因為函數(shù)的每個執(zhí)行過程都在棧中有自己的形參和局部變量的拷貝控轿，這些拷貝和函數(shù)的其他執(zhí)行過程毫不相干。這種機(jī)制是當(dāng)代大多數(shù)程序設(shè)計語言實現(xiàn)子程序結(jié)構(gòu)的基礎(chǔ)拂封，是使得遞歸成為可能茬射。假定某個調(diào)用函數(shù)調(diào)用了一個被調(diào)用函數(shù)，再假定被調(diào)用函數(shù)又反過來調(diào)用了調(diào)用函數(shù)冒签。這第二個調(diào)用就被稱為調(diào)用函數(shù)的遞歸在抛，因為它發(fā)生在調(diào)用函數(shù)的當(dāng)前執(zhí)行過程運行完畢之前。而且萧恕，因為這個原先的調(diào)用函數(shù)刚梭、現(xiàn)在的被調(diào)用函數(shù)在棧中較低的位置有它獨立的一組參數(shù)和自變量，原先的參數(shù)和變量將不受影響票唆，所以遞歸能正常工作朴读。程序遍歷執(zhí)行這些函數(shù)的過程就被稱為遞歸下降。
程序員需保證遞歸函數(shù)不會隨意改變靜態(tài)變量和全局變量的值走趋，以避免在遞歸下降過程中的上層函數(shù)出錯衅金。程序員還必須確保有一個終止條件來結(jié)束遞歸下降過程，并且返回到頂層簿煌〉ǎ看下面的例子：
這里有一個問題一定要注意，就是static int sum = 0;
有些人就不明白姨伟，為什么要使用 static 類型修飾符惩琉，為什么不使用 int sum=0;？如果使用 int sum=0; 這樣的語句授滓，在每次調(diào)用函數(shù)add()的時候琳水，sum的值都是賦值為0，也就是第一步雖然加了1上來般堆，可是第二次調(diào)用的時候在孝，sum又回到了0。我們前面說了淮摔，static能保證本次初始化的值是上次執(zhí)行后的值私沮，這樣也就保證了前面想加的結(jié)果不會丟失。如果你修改為int sum=0和橙，最后結(jié)果一定是最后結(jié)果是5而不是15仔燕。
上面的例子就很好的解釋了，被調(diào)用函數(shù)運行的椖д校空間獨立于調(diào)用函數(shù)的椢螅空間 這句話。
三办斑、遞歸調(diào)用的形式
遞歸函數(shù)有直接遞歸調(diào)用和間接調(diào)用兩種形式.
直接遞歸即在函數(shù)出現(xiàn)調(diào)用函數(shù)本身外恕，例如：
間接遞歸調(diào)用指函數(shù)中調(diào)用其他函數(shù)，而該其他函數(shù)卻又調(diào)用了本函數(shù)乡翅。例如：
下面鳞疲，再擴(kuò)展一種遞歸，尾遞歸
當(dāng)遞歸調(diào)用是整個函數(shù)中最后執(zhí)行的語句且它的返回值不屬于表達(dá)式的一部分時蠕蚜，這個遞歸調(diào)用就是尾遞歸的尚洽。
上面的直接遞歸例子的返回值是 return num*func(num-1); 是一個表達(dá)式自然不是尾遞歸了，將其改為尾遞歸：
當(dāng)編譯器檢查到一個函數(shù)是尾遞歸的時候靶累，它就會覆蓋當(dāng)前活躍記錄而不是在棧中去創(chuàng)建一個新的腺毫，這樣就解決了普通遞歸函數(shù)占用棧空間過大的問題挣柬。遺憾的是拴曲，大多數(shù)編程語言沒有針對尾遞歸做優(yōu)化，所以凛忿，即使把函數(shù)改成尾遞歸方式澈灼，也會導(dǎo)致棧溢出。星辰就暫時把遞歸說到這店溢，下一篇的話繼續(xù)接上叁熔，內(nèi)容還是講遞歸吧，基于太多床牧，一下子寫太多的話荣回，各位看了也會累。
