一、产生
在函数调用过程中，反复调用自己的函数称为递归函数。
如下面程序的函数调用过程为
(1) main里调用Hello
(2) Hello输出”Hello”后继续调用Hello函数
(3)一直这样继续
会发生什么？
没完没了一直到“爆栈”，也就是栈溢出，也即stackoverflow。
在windows的DEV-cpp编译下你会看到
我们程序返回0代表程序正常结束，这个返回值代表程序已经爆栈
#include
using namespace std;
void Hello()
{
cout<<"Hello"< Hello(); } int main() { Hello(); return 0; } 我们可以记录下递归的次数 #include using namespace std; void Hello(int tot) { cout<<"Hello"<<" "< Hello(tot+1); } int main() { Hello(0); return 0; } 我们也可以使用全局变量记录下递归的次数 为什么两个值都锁定在了64890呢，多传递几个参数呢，你会发现依旧到了这个神奇的数字，所以递归深度与传递的参数个数是无关的。 那这个64890究竟代表着什么呢，我们再来一个程序玩一下。 #include using namespace std; int tot; void test() { int buffer[1024]; tot++; cout< test(); } int main() { test(); } 这个程序能运行503次，假设每次递归调用的内存开销为x，那么这段程序的栈开销为\(503*(4KB+x)\)，一个int为4B，x为每次递归的开销 他和\(64890x\)是相等的，\(64890x=503(4*1024+x)\)，我们可以解出x的值为32，即每次递归开销为32B，栈内存开销为207360B，为2MB。 局部变量也是使用栈内存的，我们可以验证一下，你可以在主函数内开辟\((1<<20)*1.9\)的数组，\(*2\)就正好超过了这个大小。查阅相关资料你也会知道window下编译出的程序的栈缺省值(默认值)为2MB。 我们知道黑白图像那个题必须要广搜才能过，因为栈空间超过了大小，那么我把这个数据缩小到哪个数依旧可以过呢 假设这个图的大小为N*N，我们每次递归需要32B的开销，如果全是1，那么需要递归\(N*N\)次，我们可以求得N为256。256试一下发现不行，因为我们程序本身也需要一点点栈内存，要不然我们Hello连续递归运行次数应该为65536，但是确没有达到，当然255就可以了。 #include using namespace std; #define N 255 int n=N; char s[1023][10223]; char vis[N][N]; int dir[4][2]={1,0,0,1,-1,0,0,-1}; int tx,ty,i; void dfs(int x,int y) { for(i=0;i<4;i++) { tx=x+dir[i][0]; ty=y+dir[i][1]; if(tx<0||tx>=n||ty<0||ty>=n||vis[tx][ty])continue; vis[tx][ty]=1; dfs(tx,ty); } } int main() { dfs(0,0); return 0; } 二、解决 如何解决呢，使用递归前一定要估计下递归的深度，深度在6e4以上请直接放弃递归，请使用非递归的形式实现。当然你也可以手动扩栈(🐶 当然问题的本质是操作系统和编译器的内存管理让我们程序崩了