定義
遞歸是指一個函數在其定義中直接或間接地調用自身的方法。通過這種方式，函數可以將一個復雜的問題分解為規模更小的、與原問題相似的子問題，然后通過不斷地解決這些子問題來最終解決整個問題。
組成部分
遞歸主體
這是函數中遞歸調用自身的部分，它通過將問題分解為更小的子問題來逐步解決整個問題。
遞歸終止條件
也稱為基本情況，是遞歸函數停止調用自身的條件。當滿足這個條件時，函數不再進行遞歸調用，而是直接返回一個已知的結果。如果沒有正確的終止條件，遞歸函數將無限循環，導致棧溢出等錯誤。
遞歸的層層展開和回溯過程
層層展開過程
層層展開指的是遞歸函數不斷調用自身，問題規模逐步縮小，直至達到遞歸終止條件的過程。
逐步回溯過程
逐步回溯是指遞歸函數在達到終止條件后，依次返回上一層調用函數，繼續執行后續代碼的過程。最終回溯到初始調用。
遞歸函數中多次遞歸調用
遞歸函數中多次遞歸調用是依次進行的，每次調用都會創建新的棧幀壓入調用棧，直到遇到遞歸終止條件后開始逐步返回，棧幀也依次彈出，返回到上一層調用函數中繼續執行后續代碼。這樣就實現了遞歸的層層展開和逐步回溯的過程。
總結
遞歸的層層展開過程是不斷將原問題分解為規模更小的子問題，直到達到遞歸終止條件；而逐步回溯過程則是在子問題解決后，依次返回上一層，利用子問題的結果解決更大規模的問題，最終得到原問題的解。整個過程通過調用棧來管理函數的調用和返回順序，確保程序的正確執行。
生動理解
當你收到一份快遞的時候，你打開快遞包裝，發現還有包裝，再打開包裝，發現還有包裝，再打開包裝，......…終于，你收到了一張字條，上面寫著“我好餓啊，你干嘛要吃牛排意大利面?cnm”。此時，你感到很慚愧，不該在這么晚發表美食，于是，你寫了一張抱歉信，然后你將快遞重新包裝回去，包裝一層，再包裝一層，........…，終于你包裝完了，將快遞按原地址發送回去。
（該解釋來自acwing中的房智玄）
舉例
以漢諾塔問題的遞歸函數為例：
void dfs(int n, char x, char y, char z)
{if(n==0) return; // 基本情況：沒有盤子需要移動dfs(n-1, x, z, y); // 遞歸步驟1：將n-1個盤子從x移動到y，使用z作為輔助printf("%c->%d->%c\n", x, n, z); // 打印當前步驟：將第n個盤子從x移動到zdfs(n-1, y, x, z); // 遞歸步驟2：將n-1個盤子從y移動到z，使用x作為輔助
}假設我們調用 ?dfs(3, 'A', 'B', 'C')?，下面詳細闡述其層層展開和逐步回溯的過程。
層層展開過程
初始調用
我們調用 ?dfs(3, 'A', 'B', 'C')?，系統為該函數創建一個棧幀并壓入調用棧。棧幀包含參數 ?n = 3?，?x = 'A'?，?y = 'B'?，?z = 'C'??以及返回地址等信息。此時函數要解決的問題是把 3 個盤子從柱子 ?A??借助柱子 ?B??移動到柱子 ?C?。
第一次遞歸展開
在 ?dfs(3, 'A', 'B', 'C')??中，由于 ?n != 0?，執行 ?dfs(n - 1, x, z, y)?，也就是 ?dfs(2, 'A', 'C', 'B')?。
?
系統為 ?dfs(2, 'A', 'C', 'B')??創建新的棧幀并壓入調用棧。此時問題變為把 2 個盤子從柱子 ?A??借助柱子 ?C??移動到柱子 ?B?。
第二次遞歸展開
?在 ?dfs(2, 'A', 'C', 'B')??中，因為 ?n != 0?，執行 ?dfs(n - 1, x, z, y)?，即 ?dfs(1, 'A', 'B', 'C')?。
?
系統為 ?dfs(1, 'A', 'B', 'C')??創建新的棧幀并壓入調用棧。現在問題是把 1 個盤子從柱子 ?A??借助柱子 ?B??移動到柱子 ?C?。
第三次遞歸展開
在 ?dfs(1, 'A', 'B', 'C')??中，由于 ?n != 0?，執行 ?dfs(n - 1, x, z, y)?，也就是 ?dfs(0, 'A', 'C', 'B')?。
?
系統為 ?dfs(0, 'A', 'C', 'B')??創建新的棧幀并壓入調用棧。此時問題規模縮小到 0 個盤子的移動。
達到終止條件
在 dfs(0, 'A', 'C', 'B') ?中，因為 n == 0 ，滿足遞歸終止條件，函數不再進行遞歸調用，準備開始回溯。
逐步回溯過程
第一次回溯
dfs(0, 'A', 'C', 'B')??執行 ?return??語句，其棧幀從調用棧中彈出。
?
程序控制流回到 ?dfs(1, 'A', 'B', 'C')??中調用 ?dfs(0, 'A', 'C', 'B')??的下一行代碼，即 ?printf("%c->%d->%c\n", x, n, z);?，輸出 ?A->1->C?，表示將編號為 1 的盤子從柱子 ?A??移動到柱子 ?C?。
?
第二次遞歸調用（在 ?dfs(1, 'A', 'B', 'C')??中）
?
接著執行 ?dfs(n - 1, y, x, z)?，即 ?dfs(0, 'B', 'A', 'C')?。
?
系統為 ?dfs(0, 'B', 'A', 'C')??創建新的棧幀并壓入調用棧。
再次達到終止條件并回溯
在 ?dfs(0, 'B', 'A', 'C')??中，因為 ?n == 0?，執行 ?return??語句，其棧幀從調用棧中彈出。
?
回到 ?dfs(1, 'A', 'B', 'C')??中調用 ?dfs(0, 'B', 'A', 'C')??的下一行代碼，此時 ?dfs(1, 'A', 'B', 'C')??函數執行完畢，其棧幀從調用棧中彈出。
繼續回溯到 dfs(2, 'A', 'C', 'B')
?回到 ?dfs(2, 'A', 'C', 'B')??中調用 ?dfs(1, 'A', 'B', 'C')??的下一行代碼，即 ?printf("%c->%d->%c\n", x, n, z);?，輸出 ?A->2->B?，表示將編號為 2 的盤子從柱子 ?A??移動到柱子 ?B?。
?
接著執行 ?dfs(n - 1, y, x, z)?，即 ?dfs(1, 'C', 'A', 'B')?，重復上述遞歸展開和回溯的過程。
最終回溯到初始調用
?經過多次遞歸展開和回溯，最終回到 ?dfs(3, 'A', 'B', 'C')??中調用 ?dfs(2, 'A', 'C', 'B')??的下一行代碼，輸出 ?A->3->C?，表示將編號為 3 的盤子從柱子 ?A??移動到柱子 ?C?。
?
再執行 ?dfs(n - 1, y, x, z)?，完成所有盤子的移動操作，?dfs(3, 'A', 'B', 'C')??函數執行完畢，調用棧為空。
)
