递归函数的内存有关问题

递归函数的内存问题
在函数调用时，系统会为被调用函数如何分配内存？分多大的内存？
 比如说下面的代码（递归遍历图某点的8个方向）

暴力型的：

C/C++ code

#include<cstdio>#include<cstring>#include<cstdlib>#define M 751using namespace std;int T,W,H;char G[M][M];const int NEG=-1,POS=1;void dfs(int x,int y){        if(x<0||x>=H||y<0||y>=W||G[x][y]=='*')return;             /*T++;             G[x][y]='*';*/             dfs(x,POS+y);//right             dfs(x,NEG+y);//left             //upward             dfs(NEG+x,y);             dfs(NEG+x,NEG+y);             dfs(NEG+x,POS+y);             //downward             dfs(POS+x,y);             dfs(POS+x,NEG+y);             dfs(POS+x,POS+y);}

和这段和谐点的：

C/C++ code

#include<cstdio>//当用暴力代替dfs中的for循环时为什么会爆掉？#include<cstring>#include<cstdlib>#define M 751using namespace std;int T;char G[M][M];int W, H,    dx[8]={1,-1,0,0,1,-1,1,-1},    dy[8]={0,0,1,-1,1,1,-1,-1};void dfs(int x,int y){        if(x<0||x>=H||y<0||y>=W||G[x][y]=='*')return ;        /*G[x][y]='*';        T++;*/        for(int i=0;i<8;i++)            dfs(x+dx[i],y+dy[i]);}

请问大侠们在处理同样的数据时，系统为这两段代码分配的内存有什么不一样？感激！

[解决办法]
“给定一个小点的输入，完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门！
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出

[解决办法]
都差不多
在递归的层数很深的时候，就不建议使用递归了，递归太耗资源。。。
[解决办法]
第一个总共递归 8 次。
第二个是递归次数不好说啊！！！！ 一旦进 到dfs的函数里，如if条件不满足，就又多好多次递归，你按照函数逻辑，在纸上画画就知道了。
[解决办法]
递归函数对栈内存是个考验
层次太深，就会发生雪崩的

查看更多 下一篇