遞歸

程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。 遞歸做為一種算法在程序設(shè)計語言中廣泛應(yīng)用。一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算，大大地減少了程序的代碼。

簡而言之，遞歸就是利用調(diào)用自身的方法完成多次重復(fù)計算的方式。

設(shè)計思想：

把問題分解成規(guī)模更小，但和原問題有著相同解法的問題（大事化?。?/p>

分類：

遞歸函數(shù)又可以分為尾遞歸和非尾遞歸函數(shù)。

尾遞歸函數(shù)是指函數(shù)的最后一個動作是調(diào)用函數(shù)本身的遞歸函數(shù)，是遞歸的一種特殊情形。尾遞歸具有兩個主要的特征：

（1）調(diào)用自身函數(shù)(Self-called)；

（2）計算僅占用常量棧空間(Stack Space)。

優(yōu)點：

代碼簡潔，容易計算驗證。

缺點：

相對于循環(huán)（迭代），效率低下，存在棧區(qū)限制問題（棧溢出）。

特點：

后進(jìn)先出，之后回歸先進(jìn)入的函數(shù)再執(zhí)行下一步。

使用條件：

一個問題能夠分解成規(guī)模更小，且與原問題有著相同解的問題；

存在一個能讓遞歸調(diào)用退出的簡單出口。

設(shè)計條件：

設(shè)置遞歸結(jié)束的限制條件（盡可能防止棧溢出）；設(shè)計思路盡可能遵循在每次調(diào)用后不斷逼近限制條件。

內(nèi)存分區(qū)

內(nèi)存分區(qū)分為五種：棧區(qū)、堆區(qū)、靜態(tài)區(qū)、常量區(qū)、代碼區(qū)。

棧區(qū)：

存放函數(shù)的?參數(shù)值（形參）、局部變量和函數(shù)調(diào)用申請?等，由編譯器自動分配和釋放，通常在函數(shù)執(zhí)行完后就釋放了，其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。棧內(nèi)存分配運算內(nèi)置于CPU的指令集，效率很高，但是分配的內(nèi)存量有限。

堆區(qū)：

就是通過new、malloc、realloc和calloc分配的內(nèi)存塊，可以認(rèn)為是動態(tài)分配的內(nèi)存塊，編譯器不會負(fù)責(zé)它們的釋放工作，需要用程序區(qū)釋放。分配方式類似于數(shù)據(jù)結(jié)構(gòu)中的鏈表?！皟?nèi)存泄漏”通常說的就是堆區(qū)。

靜態(tài)區(qū)：

全局變量和靜態(tài)變量的存儲位置，初始化的全局變量和靜態(tài)變量在一塊區(qū)域，未初始化的全局變量和未初始化的靜態(tài)變量在相鄰的另一塊區(qū)域。程序結(jié)束后，由系統(tǒng)釋放。

常量區(qū)：常量存儲在這里，不允許修改。

代碼區(qū)：存放編寫的代碼，不調(diào)用。

遞歸引起的棧溢出

原因：

我們知道，正確的遞歸就是在達(dá)到某個限制條件（較小調(diào)用次數(shù)）之前不斷調(diào)用函數(shù)來實現(xiàn)目標(biāo)，而每次調(diào)用函數(shù)都會向棧區(qū)申請內(nèi)存且不釋放（函數(shù)整體還未結(jié)束調(diào)用），一旦函數(shù)調(diào)用過多，棧區(qū)容量自然不足，棧溢出也就出現(xiàn)了。

棧溢出常見錯誤：

1. 未設(shè)置限制條件，函數(shù)不斷調(diào)用。

2. 限制條件設(shè)置不合理，導(dǎo)致函數(shù)調(diào)用過多。

3. 設(shè)計思路存在問題，函數(shù)調(diào)用結(jié)束不再逼近限制條件，導(dǎo)致函數(shù)過多調(diào)用。

迭代

概念

迭代是重復(fù)反饋過程的活動，其目的通常是為了逼近所需目標(biāo)或結(jié)果。每一次對過程的重復(fù)稱為一次“迭代”，而每一次迭代得到的結(jié)果會作為下一次迭代的初始值。

目前對于c語言來說，迭代可以簡單認(rèn)為是循環(huán)結(jié)構(gòu)。

遞歸與迭代

遞歸是一種重復(fù)遞推與回歸過程的結(jié)構(gòu)，而迭代是一種重復(fù)循環(huán)與更新狀態(tài)的結(jié)構(gòu)，兩者為重復(fù)計算服務(wù)，實現(xiàn)的方式有所不同。

遞歸效率低下，循環(huán)驗證麻煩。

迭代可以轉(zhuǎn)換為遞歸，但遞歸不一定能轉(zhuǎn)換為迭代。

轉(zhuǎn)換方法：

將遞歸算法轉(zhuǎn)換為非遞歸算法有兩種方法，一種是直接求值（迭代），不需要回溯；另一種是不能直接求值，需要回溯。前者使用一些變量保存中間結(jié)果，稱為直接轉(zhuǎn)換法，后者使用棧保存中間結(jié)果，稱為間接轉(zhuǎn)換法。

直接轉(zhuǎn)換法

直接轉(zhuǎn)換法通常用來消除尾遞歸（tail recursion）和單向遞歸，將遞歸結(jié)構(gòu)用迭代結(jié)構(gòu)來替代。（單向遞歸 → 尾遞歸 → 迭代）

間接轉(zhuǎn)換法

遞歸實際上利用了系統(tǒng)堆棧實現(xiàn)自身調(diào)用，我們通過使用棧保存中間結(jié)果模擬遞歸過程，將其轉(zhuǎn)為非遞歸形式。

尾遞歸函數(shù)遞歸調(diào)用返回時正好是函數(shù)的結(jié)尾，因此遞歸調(diào)用時就不需要保留當(dāng)前棧幀，可以直接將當(dāng)前棧幀覆蓋掉。

好了，今天的文章就到這里，感謝大家的閱讀，喜歡的話給個三連吧~

作為一名編程學(xué)習(xí)者，如果你想更好的提升你的編程能力，好好學(xué)習(xí)C/C++編程知識以及數(shù)據(jù)結(jié)構(gòu)，以后努力成為高薪算法/軟件開發(fā)工程師的話！

UP在主頁上傳了一些學(xué)習(xí)C/C++編程的視頻教程，有興趣或者正在學(xué)習(xí)的小伙伴一定要去看一看哦！會對你有幫助的~

分享（源碼、項目實戰(zhàn)視頻、項目筆記，基礎(chǔ)入門教程）

歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長比自己琢磨更快哦！

編程學(xué)習(xí)書籍：

編程學(xué)習(xí)視頻：