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

簡而言之，遞歸就是利用調用自身的方法完成多次重複計算的方式。

設計思想：

把問題分解成規模更小，但和原問題有着相同解法的問題（大事化小）

分類：

遞歸函數又可以分為尾遞歸和非尾遞歸函數。

尾遞歸函數是指函數的最後一個動作是調用函數本身的遞歸函數，是遞歸的一種特殊情形。尾遞歸具有兩個主要的特征：

（1）調用自身函數(Self-called)；

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

優點：

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

缺點：

相對于循環（疊代），效率低下，存在棧區限制問題（棧溢出）。

特點：

後進先出，之後回歸先進入的函數再執行下一步。

使用條件：

一個問題能夠分解成規模更小，且與原問題有着相同解的問題；

存在一個能讓遞歸調用退出的簡單出口。

設計條件：

設置遞歸結束的限制條件（盡可能防止棧溢出）；設計思路盡可能遵循在每次調用後不斷逼近限制條件。

内存分區分為五種：棧區、堆區、靜态區、常量區、代碼區。

棧區：

存放函數的 參數值（形參）、局部變量和函數調用申請 等，由編譯器自動分配和釋放，通常在函數執行完後就釋放了，其操作方式類似于數據結構中的棧。棧内存分配運算内置于CPU的指令集，效率很高，但是分配的内存量有限。

堆區：

就是通過new、malloc、realloc和calloc分配的内存塊，可以認為是動态分配的内存塊，編譯器不會負責它們的釋放工作，需要用程序區釋放。分配方式類似于數據結構中的鍊表。“内存洩漏”通常說的就是堆區。

靜态區：

全局變量和靜态變量的存儲位置，初始化的全局變量和靜态變量在一塊區域，未初始化的全局變量和未初始化的靜态變量在相鄰的另一塊區域。程序結束後，由系統釋放。

常量區：常量存儲在這裡，不允許修改。

代碼區：存放編寫的代碼，不調用。

原因：

我們知道，正确的遞歸就是在達到某個限制條件（較小調用次數）之前不斷調用函數來實現目标，而每次調用函數都會向棧區申請内存且不釋放（函數整體還未結束調用），一旦函數調用過多，棧區容量自然不足，棧溢出也就出現了。

棧溢出常見錯誤：

1. 未設置限制條件，函數不斷調用。

2. 限制條件設置不合理，導緻函數調用過多。

3. 設計思路存在問題，函數調用結束不再逼近限制條件，導緻函數過多調用。

概念

疊代是重複反饋過程的活動，其目的通常是為了逼近所需目标或結果。每一次對過程的重複稱為一次“疊代”，而每一次疊代得到的結果會作為下一次疊代的初始值。

目前對于c語言來說，疊代可以簡單認為是循環結構。

遞歸與疊代

遞歸是一種重複遞推與回歸過程的結構，而疊代是一種重複循環與更新狀态的結構，兩者為重複計算服務，實現的方式有所不同。

遞歸效率低下，循環驗證麻煩。

疊代可以轉換為遞歸，但遞歸不一定能轉換為疊代。

轉換方法：

将遞歸算法轉換為非遞歸算法有兩種方法，一種是直接求值（疊代），不需要回溯；另一種是不能直接求值，需要回溯。前者使用一些變量保存中間結果，稱為直接轉換法，後者使用棧保存中間結果，稱為間接轉換法。

直接轉換法

直接轉換法通常用來消除尾遞歸（tail recursion）和單向遞歸，将遞歸結構用疊代結構來替代。（單向遞歸 → 尾遞歸 → 疊代）

間接轉換法

遞歸實際上利用了系統堆棧實現自身調用，我們通過使用棧保存中間結果模拟遞歸過程，将其轉為非遞歸形式。

尾遞歸函數遞歸調用返回時正好是函數的結尾，因此遞歸調用時就不需要保留當前棧幀，可以直接将當前棧幀覆蓋掉。

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

作為一名編程學習者，如果你想更好地提升你的編程能力，好好學習C/C 編程知識以及數據結構，以後努力成為高薪算法/軟件開發工程師的話！

編程學習書籍：

編程學習視頻：

分享（源碼、項目實戰視頻、項目筆記，基礎入門教程）

歡迎轉行和學習編程的夥伴，利用更多的資料學習成長比自己琢磨更快哦！

C語言C 編程學習交流圈子：

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!