c++ - 在递归 n-queen 程序中获取 C++ Segmentation Fault 错误

Question

基本上，我必须编写一个解决 n 皇后问题的基本程序，我已经完成了，但是如果我输入任何 >=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);
        }
    }
}

我意识到这是一大段代码，但我认为有必要将其全部发布以了解问题所在。

有什么想法吗？ :s

我是 C++ 编程的新手，所以我不知道从哪里开始调试它。

Answer 1

一开始就调试，一直运行到segmentation fault。当故障发生时——查看堆栈。我猜你递归超出了堆栈 - 这是递归程序的主要问题。

你可以扩大你的堆栈，然后错误将不会出现在输入 11 上，而是出现在其他一些数字上，但是递归程序总是会在输入足够大的堆栈问题上崩溃。

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

澄清

虽然在某些系统上您会收到“Stack Overflow”错误，但在其他系统上您会收到“Segmentation Fault”。我猜你在“其他”之一。

为了证明这一点，我刚刚编译并运行了这段代码:

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/