在遞歸n皇后程序中獲取C++分割錯誤

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

開始調試，然後讓它運行，直到出現分段錯誤。發生故障時 - 查看堆棧。我猜你會用遞歸來超越你的堆棧 - 這是遞歸程序的主要問題。

您可以放大您的堆棧，然後故障不會發生在輸入11上，而是發生在其他數字上，但遞歸程序總是會在輸入足夠大的堆棧問題上崩潰。順便說一句 - 確保遞歸是有界的，即：在某些時候，你的函數應該退出而不進一步調用它自己。恕我直言，這最好在開始時做（儘管它是一種風格和方便），因爲那樣你會清楚地看到遞歸結束的條件，並且它將更容易調試無限遞歸（這也會導致段錯誤因爲堆棧耗盡）。在你的情況下，遞歸如何結束並不是很清楚，我不會驚訝於它不適用於某些輸入。

澄清

雖然在某些系統上你得到一個「堆棧溢出」錯誤，對別人，你會得到「段錯誤」同樣的事情。我猜你是在「其他人」之一。

要說明的是，我剛剛編譯並運行這段代碼：

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/