C語言中：遞歸問題的深入研究

函數的遞歸有兩個限制條件：

1.遞歸存在限制條件，當滿?這個限制條件的時候，遞歸便不再繼續。

2.每次遞歸調?之后越來越接近這個限制條件。

例子：

#include <stdio.h>
int main()
{printf("haha\n");main();//自己調用自己的主函數return 0;
}
//出現死循環的打印

這是為什么呢？

這是遞歸的==常見錯誤：==棧溢出。

• 淺講一下：
• 每次調用函數的時候都會向內存申請空間，在C語言中內存一般劃分為三個區域：棧區，堆區，靜態區，代碼區。
• 在寫代碼的時候要創建變量，局部變量創建申請的內存空間在棧區上面（還有函數的形參）；

堆區里面放的是動態開辟的內存（比如malloc、calloc）;

全局變量的創建放在靜態區里面（包括static修飾的變量）。

函數的調用都需要從棧區里面申請內存空間。

• 我們調用main函數的時候就要從棧區里面分配一塊內存空間，調用printf函數的時候也從棧區分配一塊內存空間，接下來又遇到main函數又要從棧區分配一塊內存空間。然后陷入死循環，不斷從棧區里面申請空間，當空間耗盡的時候，就出現錯誤：（棧溢出）

• 在C語?中每?次函數調?，都要需要為本次函數調?在棧區申請?塊內存空間來保存函數調?期間的各種局部變量的值，這塊空間被稱為運?時堆棧，或者函數棧幀。函數不返回，函數對應的棧幀空間就?直占?。所以如果函數調?中存在遞歸調用的話，每?次遞歸函數調?都會開辟屬于自己的棧幀空間，直到函數遞歸不再繼續，開始回歸，才逐層釋放棧幀空間。所以如果采?函數遞歸的?式完成代碼，遞歸層次太深，就會浪費太多的棧幀空間，也可能引起棧溢出（stack over flow）的問題。

函數棧幀（運行時堆棧）的本質

1.棧幀的作用

• 每個函數調用在棧區分配的內存塊稱為棧幀（Stack Frame），用于存儲：
  • 局部變量：函數內定義的變量（如int a, char b）
  • 形參值：調用函數時傳遞的參數副本。
  • 返回地址：函數執行完畢后，返回調用者的下一條指令地址。
  • 上下文信息：保存函數調用前的寄存器狀態（如ebp、esp，用于恢復調用者的棧幀）。

2.棧幀的生命周期

• 創建：函數調用時，系統從棧頂分配空間（棧向下增長，堆向上增長）。
• 銷毀：函數返回時，系統釋放棧幀空間，棧頂指針回退。

3. 棧幀結構示例（x86 架構）

高地址
┌───────────────┐
│ 調用者棧幀 │
├─────────────── ┤
│ 返回地址 │ <- 調用者的下一條指令地址
├─────────────── ┤
│ 形參值 │ <- 按從右到左順序壓棧（C語言特性）
├───────────────┤
│ 保存的ebp │ <- 調用者的ebp寄存器值
├───────────────┤
│ 局部變量 │ <- 函數內定義的變量
├───────────────┤
│ 臨時變量 │ <- 表達式計算臨時值
└───────────────┘ <- ebp（當前棧幀基址）
低地址

遞歸調用與棧幀的關系

1.遞歸的棧幀特征

• 每層遞歸都是獨立棧幀：每次遞歸調用都會創建新的棧幀，保存當前層的部變量、形參和返回地址。

• 棧幀數量等于遞歸深度：若遞歸深度為n，則棧中存在n個未釋放的棧幀。

2.階乘遞歸的棧幀變化

int factorial(int n)
{if (n == 0) return 1;return n * factorial(n-1); // 遞歸調用
}

當調用factorial(3)時，棧幀變化如下：
第 1 層：n=3，調用factorial(2)，棧幀 1 入棧。
第 2 層：n=2，調用factorial(1)，棧幀 2 入棧。
第 3 層：n=1，調用factorial(0)，棧幀 3 入棧。
終止層：n=0，返回 1，棧幀 3 釋放，返回棧幀 2。
回歸層：棧幀 2 計算2*1，釋放后返回棧幀 1，依此類推。

3. 棧幀的空間占用

每個棧幀的大小由函數內局部變量決定。例如：

void func() {int a[1000]; // 占用4KB（假設int占4字節）char b;      // 占用1字節
}

每次調用func需分配約 4KB 棧空間。

三、棧溢出（Stack Overflow）的成因與風險

1.直接原因

• 遞歸深度過大：如計算factorial(10000)，若每層棧幀占 1KB，總需約 10MB 空間，遠超默認棧大小（通常 8MB 以下）。
• 局部變量過大：函數內定義超大數組（如int arr[1000000]），單個棧幀耗盡棧空間。

2.系統默認棧大小

• Linux：通過ulimit -s查看，默認通常為 8192 KB（8MB）。
• Windows：Visual Studio 默認約 1MB（可通過鏈接器選項調整）。

四、避免棧溢出的策略

1. 限制遞歸深度

• 尾遞歸優化：若遞歸調用是函數最后一步操作（尾遞歸），部分編譯器（如 GCC，需加-O2參數）可復用棧幀，避免棧增長。

• int factorial_tail(int n, int result)
  {if (n == 0) return result;return factorial_tail(n-1, n*result); // 尾遞歸，可優化
  }
  int factorial(int n) {return factorial_tail(n, 1);
  }
  

2. 手動模擬遞歸（迭代法）：

   • 用循環和顯式棧（如數組、鏈表）替代遞歸，避免依賴系統棧。

3. 最佳實踐：
   優先使用迭代，除非遞歸能顯著簡化代碼（如樹 / 圖的遍歷）。
   對遞歸深度可預估且較小的場景（如n < 1000），可直接使用遞歸。
   對深四、使用動態內存（堆）模擬棧
   手動用堆內存實現棧結構，替代函數調用棧（即 “遞歸轉迭代”）。
   示例：用堆模擬棧計算階乘

4. 度可能較大的場景（如未知輸入的遞歸），必須用迭代或尾遞歸優化。

5. 使用動態內存（堆）模擬棧，手動用堆內存實現棧結構，替代函數調用棧（即 “遞歸轉迭代”）。

   #include <stdio.h>
   #include <stdlib.h>typedef struct Stack
   {int* data;int top;int capacity;
   }Stack;Stack* create_stack(int size) 
   {Stack* stack = (Stack*)malloc(sizeof(Stack));stack->data = (int*)malloc(size * sizeof(int));stack->top = -1;stack->capacity = size;return stack;
   }void push(Stack* stack, int val)
   {if (stack->top < stack->capacity - 1){stack->data[++stack->top] = val;}
   }int pop(Stack* stack) 
   {if (stack->top >= 0) {return stack->data[stack->top--];}return -1;  // 錯誤處理
   }int factorial(int n) 
   {if (n == 0) return 1;Stack* stack = create_stack(n);int result = 1;// 入棧：模擬遞歸調用while (n > 1) {push(stack, n);n--;}// 出棧：模擬遞歸回歸while (stack->top >= 0) {result *= pop(stack);}free(stack->data);free(stack);return result;
   }
   

• 棧結構定義與初始化

typedef struct Stack
{int* data;     // 動態數組存儲棧元素int top;       // 棧頂指針（初始為-1表示空棧）int capacity;  // 棧的最大容量
} Stack;Stack* create_stack(int size) 
{Stack* stack = (Stack*)malloc(sizeof(Stack));  // 分配棧結構內存stack->data = (int*)malloc(size * sizeof(int)); // 分配數據存儲區stack->top = -1;      // 初始化棧頂指針stack->capacity = size;  // 設置棧容量return stack;
}

• 關鍵點：

  • 動態內存分配：通過兩次malloc分別分配棧結構和數據區
  • 棧頂指針：top初始為 - 1，表示棧為空；入棧時先自增再賦值

• 棧操作實現

void push(Stack* stack, int val)
{if (stack->top < stack->capacity - 1)  // 檢查棧未滿{stack->data[++stack->top] = val;  // 先移動棧頂指針，再存入數據}
}int pop(Stack* stack) 
{if (stack->top >= 0)  // 檢查棧非空{return stack->data[stack->top--];  // 先返回數據，再移動棧頂指針}return -1;  // 錯誤處理（棧空時返回-1）
}

• 操作邏輯：
  • 入棧（Push）：棧頂指針top先自增，再將值存入data[top]
  • 出棧（Pop）：先返回data[top]的值，再將top自減
    邊界檢查：入棧時檢查top < capacity-1，出棧時檢查top >= 0
• 階乘計算的棧模擬

int factorial(int n) 
{if (n == 0) return 1;  // 基準條件：0! = 1Stack* stack = create_stack(n);  // 創建容量為n的棧int result = 1;// 階段1：入棧過程（模擬遞歸調用）while (n > 1) {push(stack, n);  // 將n壓入棧n--;             // n遞減，模擬遞歸深入}// 階段2：出棧過程（模擬遞歸回歸）while (stack->top >= 0) {result *= pop(stack);  // 彈出棧頂元素并累乘到結果}free(stack->data);  // 釋放數據區內存free(stack);        // 釋放棧結構內存return result;
}