在递归n-queen程序中获取C++分段错误错误

Question

基本上,我必须编写一个解决n-queen问题的基本程序,我已经完成了,但如果输入任何数字> = 11,它会引发分段错误.

从我在网上看到的,这个错误通常是由处理内存时的错误逻辑引起的,但我似乎无法弄清楚我做错了什么.

void generateBoard(int board[],int column,int length,int count)
{
    if(column == 0 && board[0]<length)  //prevents outputting the results infinitely 
    {
        ++board[0];
        generateBoard(board, ++column, length, count);
    } 
    else 
    {
        bool lineNotFound = true;
        int row = board[column];
        while(lineNotFound && row < length)
        {
            ++row; //temporary value for a column value candidate
            lineNotFound = false;
            for(int i = 0; i < column && !lineNotFound; ++i)
            {
                if(board[i] == row || (board[i]+column-i) == row || (board[i]-column+i) == row) // check diagonal and horizontal
                {
                    lineNotFound = true;
                }
                else
                {
                    board[column] = row;
                }
            }
        }
        if(column == length-1 && !lineNotFound) // at last column and valid board
        {
            output(board,length,++count);
            generateBoard(board,column,length,count);
        }
        else if(!lineNotFound) // not at last column, but valid position found
        {
            generateBoard(board,++column,length,count);
        }
        else if(column != 0) //no valid columns, go back a step
        {
            board[column] = 0;
            generateBoard(board,--column,length,count);
        }
    }
}

我意识到这是一大块代码,但我认为有必要将其全部发布以了解问题.

有任何想法吗？:■

我是编程c ++的新手,所以我不知道从哪里开始调试它.

Answer 1

在开始时开始调试,然后让它运行直到分段错误.发生故障时 - 查看堆栈.我猜你用递归超过你的堆栈 - 这是递归程序的主要问题.

您可以扩大堆栈,然后故障将不会出现输入11但有一些其他数字,但递归程序将始终崩溃堆栈问题输入足够大.

顺便说一下 - 确保你的递归是有界的,即:在某些时候你的函数应该退出而不进一步调用自己.恕我直言,这最好在开始时完成(虽然这是一个风格和方便的问题),因为那时你会清楚地看到递归结束的条件,并且调试无限递归将更容易(这也会导致seg错误因为堆栈耗尽).在你的情况下,并不是立即清楚递归是如何结束的,并且我不会感到惊讶它不适用于某些输入.

澄清

虽然在某些系统上会出现"堆栈溢出"错误,但在其他系统上会出现"分段错误"同样的问题.我猜你是其中一个"其他人".

为了表明这一点,我只是编译并运行了这段代码:

int foo(long a)
{
  return foo(a-1);
}


int main()
{
   return foo(9999999999L);
}

在我的GCC/Ububtu机器上.该程序具有无限递归,最终导致" 分段错误 "崩溃.

您可以将任何递归算法转换为迭代.而不是使用新变量递归调用函数,使用STL std::stack来推送和弹出它们并在循环中运行.详细信息如下:http://www.cplusplus.com/reference/stl/stack/