遞回
程式呼叫自身的編程技巧稱為遞回（ recursion）， 遞回作為一種演算法在程式設計語言中廣泛應用，一個程序或函式在其定義或說明中有直接或間接呼叫自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞回策略只需少量的程式就可描述出解題程序所需要的多次重復計算，大大地減少了程式的代碼，
簡而言之，遞回就是利用呼叫自身的方法完成多次重復計算的方式，
設計思想：
把問題分解成規模更小，但和原問題有著相同解法的問題（大事化小）
分類：
遞回函式又可以分為尾遞回和非尾遞回函式，
尾遞回函式是指函式的最后一個動作是呼叫函式本身的遞回函式，是遞回的一種特殊情形，尾遞回具有兩個主要的特征：
（1）呼叫自身函式(Self-called)；
（2）計算僅占用常量堆疊空間(Stack Space)，
優點：
代碼簡潔，容易計算驗證，
缺點：
相對于回圈（迭代），效率低下，存在堆疊區限制問題（堆疊溢位），
特點：
后進先出，之后回歸先進入的函式再執行下一步，
使用條件：
一個問題能夠分解成規模更小，且與原問題有著相同解的問題；
存在一個能讓遞回呼叫退出的簡單出口，
設計條件：
設定遞回結束的限制條件（盡可能防止堆疊溢位）；設計思路盡可能遵循在每次呼叫后不斷逼近限制條件，
記憶體磁區
記憶體磁區分為五種：堆疊區、堆區、靜態區、常量區、代碼區，
堆疊區：
存放函式的 引數值（形參）、區域變數和函式呼叫申請 等，由編譯器自動分配和釋放，通常在函式執行完后就釋放了，其操作方式類似于資料結構中的堆疊，堆疊記憶體分配運算內置于CPU的指令集，效率很高，但是分配的記憶體量有限，
堆區：
就是通過new、malloc、realloc和calloc分配的記憶體塊，可以認為是動態分配的記憶體塊，編譯器不會負責它們的釋放作業，需要用程式區釋放，分配方式類似于資料結構中的鏈表，“記憶體泄漏”通常說的就是堆區，
靜態區：
全域變數和靜態變數的存盤位置，初始化的全域變數和靜態變數在一塊區域，未初始化的全域變數和未初始化的靜態變數在相鄰的另一塊區域，程式結束后，由系統釋放，
常量區：常量存盤在這里，不允許修改，
代碼區：存放撰寫的代碼，不呼叫，
遞回引起的堆疊溢位
原因：
我們知道，正確的遞回就是在達到某個限制條件（較小呼叫次數）之前不斷呼叫函式來實作目標，而每次呼叫函式都會向堆疊區申請記憶體且不釋放（函式整體還未結束呼叫），一旦函式呼叫過多，堆疊區容量自然不足，堆疊溢位也就出現了，
堆疊溢位常見錯誤：
1. 未設定限制條件，函式不斷呼叫，
2. 限制條件設定不合理，導致函式呼叫過多，
3. 設計思路存在問題，函式呼叫結束不再逼近限制條件，導致函式過多呼叫，
迭代
概念
迭代是重復反饋程序的活動，其目的通常是為了逼近所需目標或結果，每一次對程序的重復稱為一次“迭代”，而每一次迭代得到的結果會作為下一次迭代的初始值，
目前對于c語言來說，迭代可以簡單認為是回圈結構，
遞回與迭代
遞回是一種重復遞推與回歸程序的結構，而迭代是一種重復回圈與更新狀態的結構，兩者為重復計算服務，實作的方式有所不同，
遞回效率低下，回圈驗證麻煩，
迭代可以轉換為遞回，但遞回不一定能轉換為迭代，
轉換方法：
將遞回演算法轉換為非遞回演算法有兩種方法，一種是直接求值（迭代），不需要回溯；另一種是不能直接求值，需要回溯，前者使用一些變數保存中間結果，稱為直接轉換法，后者使用堆疊保存中間結果，稱為間接轉換法，
直接轉換法
直接轉換法通常用來消除尾遞回（tail recursion）和單向遞回，將遞回結構用迭代結構來替代，（單向遞回 → 尾遞回 → 迭代）
間接轉換法
遞回實際上利用了系統堆疊實作自身呼叫，我們通過使用堆疊保存中間結果模擬遞回程序，將其轉為非遞回形式，
尾遞回函式遞回呼叫回傳時正好是函式的結尾，因此遞回呼叫時就不需要保留當前堆疊幀，可以直接將當前堆疊幀覆寫掉，
好了，今天的文章就到這里，感謝大家的閱讀，喜歡的話給個三連吧~
作為一名編程學習者，如果你想更好地提升你的編程能力，好好學習C/C++編程知識以及資料結構，以后努力成為高薪演算法/軟體開發工程師的話！
C語言C++編程學習交流圈子，QQ群464501141【點擊進入】微信公眾號：C語言編程學習基地
分享（原始碼、專案實戰視頻、專案筆記，基礎入門教程）
歡迎轉行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！
編程學習書籍：
編程學習視頻：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/265801.html
標籤：C