关于利用递归给二维数组赋值的一个问题
本帖最后由 u011209118 于 2013-06-26 09:53:05 编辑 用递归方法编写了一个给二维数组赋值的程序，但是运行时或提示发生堆栈溢出的错误，程序如下：
如果程序中row和col设置的很小，比如20，程序是可以运行的。请各位高手帮忙看看问题出在那里。

#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;

//如果row和col较小，程序可以运行
int row = 80;
int col = 80;
void regionGrow(int **imgFlag, int x, int y);
int _tmain(int argc, _TCHAR* argv[])
{
int **imgFlag = new int*[row];
for (int i=0; i<row; i++) {
imgFlag[i] = new int[col];
}
for (int i=0; i<row; i++) {
for (int j=0; j<col; j++) {
imgFlag[i][j] = 0;
}
}
regionGrow(imgFlag, col/2, row/2);
return 0;
}

void regionGrow(int **imgFlag, int x, int y)
{
if (imgFlag[y][x]==0)
imgFlag[y][x] = 1;
else
return;

if (x>0 && imgFlag[y][x-1]!=1) regionGrow(imgFlag, x-1, y);
if (y>0 && imgFlag[y-1][x]!=1) regionGrow(imgFlag, x, y-1);
if (x<col-1 && imgFlag[y][x+1]!=1) regionGrow(imgFlag, x+1, y);
if (y<row-1 && imgFlag[y+1][x]!=1) regionGrow(imgFlag, x, y+1);
} 递归 二维数组 C++
[解决办法]
递归次数过多导致堆栈溢出
要么限制递归次数，要么自己保存递归状态
[解决办法]
“给定一个小点的输入，完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门！
递归函数关注以下几个因素
退出条件
参数有哪些
返回值是什么
局部变量有哪些
全局变量有哪些
何时输出
会不会导致堆栈溢出

[解决办法]
把你的代码如下修改后运行：

[code=c]
#include <iostream>
#include <fstream>
#include <cassert>

using namespace std;

int row = 1000;
int col = 1000;
void regionGrow(int **imgFlag, int x, int y, unsigned int level);
int main(int argc, char* argv[])
{
    int **imgFlag = new int*[row];
    for (int i=0; i<row; i++)
    {
        imgFlag[i] = new int[col];
    }
    for (int i=0; i<row; i++)
    {
        for (int j=0; j<col; j++)
        {
            imgFlag[i][j] = 0;
        }
    }
    regionGrow(imgFlag, col/2, row/2, 1); 
 
    return 0;
}

void regionGrow(int **imgFlag, int x, int y, unsigned int level)
{
    assert( x >= 0 && x < col );
    assert( y >= 0 && y < row );
    std::cerr << ++level << '\n';
    
    if (imgFlag[y][x]==0)
        imgFlag[y][x] = 1;
    else
        return;

    if (x>0 && imgFlag[y][x-1]!=1) regionGrow(imgFlag, x-1, y, level);
    if (y>0 && imgFlag[y-1][x]!=1) regionGrow(imgFlag, x, y-1, level);
    if (x<col-1 && imgFlag[y][x+1]!=1) regionGrow(imgFlag, x+1, y, level);
    if (y<row-1 && imgFlag[y+1][x]!=1) regionGrow(imgFlag, x, y+1, level);
}

最后出错时递归了65080层。
改用栈实现吧。选择递归算法时一定要预估一下可能的递归深度，如果太深的话就改用栈结构来模拟。

[解决办法]
改用栈结构实现的代码：

#include <iostream>
#include <fstream>
#include <cassert>
#include <stack>
#include <utility>
#include <algorithm>

using namespace std;

int row = 300;
int col = 300;
void regionGrow(int **imgFlag, int x, int y);
int main(int argc, char* argv[])
{
    int **imgFlag = new int*[row];
    for (int i=0; i<row; i++)
    {
        imgFlag[i] = new int[col];
    }
    for (int i=0; i<row; i++)
    {
        for (int j=0; j<col; j++)
        {
            imgFlag[i][j] = 0;
        }
    }
    regionGrow(imgFlag, col/2, row/2);
    return 0;
}

void regionGrow(int **imgFlag, int x, int y)
{
    std::stack<std::pair<int, int> > point_stack;
    if( imgFlag[y][x] == 0)
    {
        point_stack.push( pair<int, int>( x, y ));
    }
    
    unsigned int level = 0; //这行代码将来要删掉
    while( !point_stack.empty())
    {
        level = std::max( level, point_stack.size());//这行代码将来要删掉
        std::cerr << '\r' << level << "                ";//这行代码将来要删掉
         
 
        int x = point_stack.top().first;
        int y = point_stack.top().second;
        point_stack.pop();
        
        assert( x >= 0 && x < col );
        assert( y >= 0 && y < row );
        
        imgFlag[y][x] = 1;
        
        //为了让数据处理数据和原来的代码相同，我这里把判断顺序倒过来了
        //因为处理时后入栈的先处理。
        if (y<row-1 && imgFlag[y+1][x]!=1) point_stack.push( std::pair<int,int>(x, y+1));
        if (x<col-1 && imgFlag[y][x+1]!=1) point_stack.push(std::pair<int,int>( x+1, y));
        if (y>0 && imgFlag[y-1][x]!=1) point_stack.push(std::pair<int,int>( x, y-1));
        if (x>0 && imgFlag[y][x-1]!=1) point_stack.push(std::pair<int,int>( x-1, y));
    }
    
}

point_stack.size的最大值是89402，也就是需要递归89402层。

你这个递归设计得严重不平衡，如果把代码中递归的过程组织成一棵树，你会发现棵树几乎始化成了一个链表，所有节点最聚集在最左边的那个链上。

因此，如果用递归实现“全矩阵置1”，最好给每一层递归设置上方向限制：

#include <iostream>
#include <fstream>
#include <cassert>
#include <algorithm>
using namespace std;
int row = 1000;
int col = 1000;
const int dir_left = 1;
const int dir_right = 2;
const int dir_up = 3;
const int dir_down = 4;
const int dir_all = dir_left 
[解决办法]
 dir_right 
[解决办法]
 dir_up 
[解决办法]
 dir_down;
unsigned int max_level = 0;
void regionGrow(int **imgFlag, int x, int y, int dir, unsigned int level);

bool check_result(int **imgFlag)
{
   bool ok = true;
   int x = 0;
   while( ok && x < col )
   {
        int y = 0;
        while( ok && y < row )
        {
            ok = ( imgFlag[y][x] == 1);
            ++ y;
        }
        ++ x;
   }
   return ok;
}

int main(int argc, char* argv[])
{
    int **imgFlag = new int*[row]; 
 
    for (int i=0; i<row; i++)
    {
        imgFlag[i] = new int[col];
    }
    for (int i=0; i<row; i++)
    {
        for (int j=0; j<col; j++)
        {
            imgFlag[i][j] = 0;
        }
    }
    regionGrow(imgFlag, col/2, row/2, dir_all, 1);
    assert(check_result(imgFlag));
    std::cout << "Max level:" << max_level << '\n';
    
    return 0;
}


void regionGrow(int **imgFlag, int x, int y, int dir, unsigned int level)
{
    assert( x >= 0 && x < col );
    assert( y >= 0 && y < row );
    max_level = std::max(level ++, max_level);
    if (imgFlag[y][x]==0)
        imgFlag[y][x] = 1;
    else
        return;
    if ( (dir & dir_left) && (x>0) && (imgFlag[y][x-1]!=1) )
        //允许向左，并且未到左边界，并且左边需要处理
    {
        regionGrow(imgFlag, x-1, y, dir & ~dir_right, level );//下一步不允许向右
    }
    if ( (dir & dir_up) && (y>0) && (imgFlag[y-1][x]!=1) )
        //允许向上，并且未到上边界，并且上边需要处理
    {
        regionGrow(imgFlag, x, y-1, dir & ~dir_down, level);//下一步不允许向下
    }
    if ( (dir & dir_right) && (x<col-1) && (imgFlag[y][x+1]!=1) )
        //允许向右，并且未到右边界，并且右边需要处理
    {
        regionGrow(imgFlag, x+1, y, dir & ~dir_left, level);//下一步不允许向左
    }
    if ( (dir & dir_down) && (y<row-1) && (imgFlag[y+1][x]!=1) ) 
        //允许向规划，并且未到下边界，并且下边需要处理
    {
        regionGrow(imgFlag, x, y+1, dir & ~dir_up, level);//下一步不允许向上
    }
}

这样最大递归深度为1001。
[解决办法]
没注意到上面的代码中行列数不一样。

用MinGW4.7.1编译，在递归65080层时栈溢出，改为300*300行后用栈结构模拟判断最大递归深度为89402。

设置方向限制之后，1000*1000最大递归层数是1001，300*300最大递归导数是301,1000*100时最大递归层数是551