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;
}