c语言函数递归调用栈溢出解决方法

写递归函数的时候，是不是有过这种经历？程序跑一会儿就崩了，提示什么 “stack overflow”，你检查半天，递归终止条件也没错啊，可就是解决不了。我之前写一个计算斐波那契数列的递归函数，算到第 50 项就崩了，后来才知道是栈溢出了。今天就跟大家聊聊，递归调用为啥会栈溢出，以及有哪些实用的解决方法，希望能帮到正在犯愁的你。

先弄明白：递归为啥会栈溢出？

递归这东西，写起来是简洁，看着也清楚，但有个不大不小的毛病 —— 容易栈溢出。为啥呢？
咱们得先知道栈是啥。函数调用的时候，系统会在内存里划出一块地方，叫 “栈”，用来存参数啊、局部变量这些临时东西。每递归一次，就相当于多调用一次函数，栈上就得多存一份这些东西。可栈的空间是有限的，一般就几 MB，递归次数太多，栈存不下了，可不就溢出了嘛。
比如你写个递归求阶乘的函数，算 1000 的阶乘可能没事，但算 10000 的阶乘，大概率就栈溢出了。有个网友更夸张，写了个递归遍历深层嵌套的 JSON 数据，结果数据嵌套了几百层，程序直接崩了，就是栈被撑爆了。
那怎么判断是不是栈溢出呢？一般程序会崩溃，报错信息里可能有 “stack overflow” 或者 “段错误”，而且递归深度越大，崩溃得越快，基本就是栈溢出没跑了。

解决方法一：减少递归深度，给递归 “瘦身”

最直接的办法，就是让递归别那么 “深”。怎么瘦呢？
可以优化递归逻辑，去掉不必要的递归调用。比如算斐波那契数列，普通递归是这样的：
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
这玩意儿递归深度特别大，算到第 50 项就可能溢出。但如果你发现，其实很多计算是重复的，比如 fib (5) 要算 fib (4) 和 fib (3)，fib (4) 又要算 fib (3) 和 fib (2)，这里 fib (3) 就重复算了。
那咱们可以用 “记忆化” 的办法，把算过的结果存起来，下次直接用，不用再递归。比如用个数组存已经算好的 fib 值：
int memo [1000]; // 存计算过的结果
int fib (int n) {
if (n <= 1) return n;
if (memo [n] != 0) return memo [n]; // 已经算过，直接返回
memo [n] = fib (n-1) + fib (n-2);
return memo [n];
}
这样一来，递归深度就大大减少了，栈溢出的可能性也小多了。我当初把这个方法用到斐波那契函数里，算到 1000 项也没崩。

解决方法二：用尾递归优化，让编译器帮你 “减负”

尾递归可能有些朋友没听过，它是一种特殊的递归 —— 递归调用是函数的最后一步操作。这种递归，有些编译器能优化成循环，从而不增加栈的深度。
比如求阶乘，普通递归是这样的：
int factorial (int n) {
if (n == 1) return 1;
return n * factorial (n-1); // 递归调用后还有乘法操作，不是尾递归
}
这不是尾递归，因为递归调用后还要做乘法。改成尾递归，得加个参数存中间结果：
int factorial_tail (int n, int result) {
if (n == 1) return result;
return factorial_tail (n-1, n * result); // 最后一步就是递归调用
}
// 调用的时候用 factorial_tail (n, 1)
// 比如算 5 的阶乘，就是 factorial_tail (5, 1)
这样一改，编译器优化后，就不会每次递归都增加栈帧了，相当于循环，自然就不容易栈溢出。但要注意，不是所有编译器都支持尾递归优化，比如 VC 可能就不行，gcc 在开启优化的情况下可以。所以用这个方法，最好先测试一下。

解决方法三：改用循环实现，彻底告别递归

如果递归深度实在太大，不管怎么优化递归都不行，那最保险的办法就是把递归改成循环。循环不用频繁调用函数，也就不会占用太多栈空间。
还是拿阶乘来说，递归改循环很简单：
int factorial(int n) {
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
这样写，不管 n 是 1000 还是 10000，都不会栈溢出，因为循环用的栈空间是固定的。
有朋友可能会说，有些递归逻辑很复杂，改循环很难啊？其实再复杂的递归，理论上都能改成循环，就是麻烦点。可以试试用栈来模拟递归过程，把每次递归需要的参数存到自己定义的栈里（这个栈可以用数组或者 malloc 在堆上分配），然后用循环来处理栈里的元素。
比如二叉树的前序遍历，递归写法很简单，但深度大了会溢出。改成循环，用一个数组模拟栈：
void preorder (TreeNode* root) {
if (root == NULL) return;
TreeNode* stack [1000]; // 自己定义的栈
int top = 0;
stack [top++] = root;
while (top > 0) {
TreeNode* node = stack [--top];
printf ("% d", node->val);
if (node->right != NULL) stack [top++] = node->right;
if (node->left != NULL) stack [top++] = node->left;
}
}
自己管理栈，就不用担心系统栈溢出了，而且堆空间比栈大得多，就算需要大一点的栈，用 malloc 分配也没问题。

解决方法四：增大栈空间，应急用用也可以

如果暂时没法改代码，又急需程序跑起来，可以试试增大系统栈的空间。不同的编译器和操作系统，设置方法不一样。
比如在 Linux 下用 gcc 编译，可以加个参数：
gcc -o test test.c -Wl,--stack=10485760
这里的 10485760 是 10MB，默认可能只有 8MB，改大一点，递归深度就能增加一些。但这个方法是治标不治本，栈空间再大也是有限的，递归太深还是会溢出，只能应急用。

最后说点我的心得

递归栈溢出，说到底还是因为对递归的 “副作用” 了解不够。我当初踩了不少坑才明白，递归虽好，但不能滥用。能不用递归的地方，尽量用循环；必须用递归的，就想办法优化深度。
其实解决栈溢出的核心思路就两个：要么减少栈的使用量（比如尾递归、记忆化），要么不用系统栈（比如改循环、自己用堆模拟栈）。具体用哪种方法，得看你的代码情况。
新手刚开始写递归，别害怕出错，栈溢出了就一步步分析，看看是深度太大，还是逻辑有问题。多试几种解决方法，慢慢就有经验了。希望这些方法能帮你解决递归栈溢出的问题，写出更稳健的代码。

标签： 一次函数 斐波那契