曾經有一個段子：上大學時，我們的c語言老師說：學c時，如果有50%的同學死在了循環上面，那么就有90%的同學死在了遞歸上面。接下來，就來看看遞歸是怎么個事？
一.遞歸的介紹
遞歸是指一個函數直接或間接調用自身的過程。在編程中，遞歸通常用于解決可以被分解為相似子問題的任務。
-
基本原理：遞歸函數通過反復調用自身來解決問題，每次調用都會解決一個規模較小的子問題，直到達到遞歸的終止條件。
-
遞歸函數的結構：
- 基本情況（終止條件）：遞歸函數需要定義一個或多個基本情況，這些情況下遞歸調用不再發生，避免無限循環。
- 遞歸情況：在遞歸情況下，函數調用自身來解決同一問題的子問題。
-
遞歸與循環：遞歸和迭代循環（for、while循環）都可以實現相同的算法，但遞歸通常更簡潔，易于理解，有時更符合問題的自然表達方式。
-
遞歸的應用：遞歸廣泛用于數據結構==（如樹、圖等）的遍歷和搜索==，例如深度優先搜索（DFS）和快速排序算法。
-
性能考慮：遞歸可能會消耗大量的棧空間，因為每次函數調用都會在棧上分配一個新的棧幀。這在處理大規模問題時需要注意，可以通過優化算法或者尾遞歸優化來減少內存消耗。
-
遞歸的優缺點：
- 優點：簡潔、清晰表達某些問題的解決方式。
- 缺點：可能會因為調用層次過深導致棧溢出，性能上可能不如迭代循環。
二.什么是棧幀
棧幀（Stack Frame），也稱為活動記錄（Activation Record）或者幀（Frame），是在函數調用過程中在程序運行時棧上的一個特定區域，用于存儲與當前函數調用相關的信息和數據。每當一個函數被調用時，系統就會為該函數在棧上分配一個新的棧幀，用于管理函數的局部變量、參數、返回地址以及其他執行上下文信息。
棧幀通常包括以下主要部分：
-
局部變量：函數內部聲明的局部變量會被存儲在棧幀中。這些變量的生命周期與函數的調用周期相關聯，在函數調用結束時，這些變量的存儲空間也會自動釋放。
-
參數：調用函數時傳遞的參數值被存儲在棧幀中，供函數體內部使用。
-
返回地址：函數調用完成后，程序需要返回到調用該函數的下一條指令的地址。返回地址存儲在棧幀中，使得程序可以正確地返回到調用點繼續執行。
-
其他管理信息：棧幀還可能包括調試信息、異常處理信息等，這些信息有助于程序的正確執行和調試。
棧幀的創建和銷毀遵循后進先出（LIFO）原則，即最后進入棧的棧幀最先被釋放。這種機制保證了函數調用的嵌套順序正確，同時也控制了函數調用過程中的內存管理。
理解和正確使用棧幀是編寫函數式程序的關鍵，尤其是在處理遞歸函數或者多層函數調用時，對棧幀的合理利用可以提高程序的效率和可靠性。
舉例說明
有 5 個學生坐在一起, 問第 5 個學生多少歲？他說比第 4 個學生大 2歲,問第 4 個學生歲數，他說比第 3 個學生大 2 歲,問第 3 個學生，又說比第 2個學生大 2 歲,問第 2 個學生，說比第 1 個學生大 2 歲,最后問第 1 個學生，他說是 10 歲,請問第 5 個學生多大。
該問題如果使用非遞歸,代碼如下:
//非遞歸求年齡
int Age1(int n)
{int tmp = 10; //第一個人年齡for(int i=1;i<n;i++){tmp += 2;//后面的人比前一個多 2 歲}return tmp;
}
那么遞歸該如何處理呢?我們先分析一下:
如果 Age 函數是用來求年齡的,那么
Age(1)表示第一個人的年齡;
Age(2)表示第二個人的年齡;
…
Age(n-1)表示第 n-1 個人的年齡;
Age(n)表示第 n 個人的年齡。
上面的這些能理解,下面的程序就好理解了
//遞歸求年齡
int Age(int n)
{int tmp;//保存年齡if (n == 1)tmp = 10;elsetmp = Age(n - 1) + 2;//當前第 n 個比第 n-1 個年齡多 2return tmp;
}
上圖中的紅色表示函數的調用過程,在這個過程中每個函數都還沒有執行完成,那么每個函數占用的內存空間都不能釋放,函數的調用都需要占用一定的棧空間(一個棧幀),而棧的空間是非常小的(在動態內存章節講過棧 1M),當遞歸次數非常多時有可能出現棧空間不足
// 遞歸求年齡
int Age(int n)
{int tmp;//保存年齡if (n == 1)tmp = 10;elsetmp = Age(n - 1) + 2;//當前第 n 個比第 n-1 個多 2return tmp;//return n == 1 ? 10 : Age(n - 1) + 2;//等同上面的代碼
}//遞歸調用次數太多, 程序崩潰
int main()
{printf("%d\n", Age1(5000));//可以.利用循環求解//printf("%d\n",Age(5000));//崩潰,棧溢出,遞歸次數太多,超過棧容量return 0;
}
例2.求階乘
利用遞歸求階乘 n!
算法分析:可以利用下面公式求階乘
long long Fac(int n)
{if (n == 0 || n == 1)return 1;return n * Fac(n - 1);
}
事務)
