C++遞歸段錯誤。你能幫我看看我做錯了什麼嗎？

Question

這是我第一次使用遞歸做一些事情，而不是找到一個數的階乘。我正在製作一個程序，以便在一塊麻煩的板子裏找到單詞。以下是導致段錯誤的功能：

void findWord(vector<string>& board, set<string>& dictionary, 
      string prefix, int row, int column){ 
    prefix += getTile(board, row, column); 
    if(prefix.length() > biggestWordLength) 
    return; 
    if(isOutOfBounds(row, column)) 
    return; 
    if(isWord(prefix, dictionary) == 1) 
    foundWords.insert(prefix); 
    if(isWord(prefix, dictionary) == 0) 
    return; 
    //Note: this does not prevent using the same tile twice in a word 
    findWord(board, dictionary, prefix, row-1, column-1); 
    findWord(board, dictionary, prefix, row-1, column); 
    findWord(board, dictionary, prefix, row-1, column+1); 
    findWord(board, dictionary, prefix, row, column-1); 
    findWord(board, dictionary, prefix, row, column+1); 
    findWord(board, dictionary, prefix, row+1, column-1); 
    findWord(board, dictionary, prefix, row+1, column); 
    findWord(board, dictionary, prefix, row+1, column+1); 
} 

Answer 1

您正在所有情況下的所有方向遞歸。這考慮減少遞歸版本：

void findword(... int x, int y, ...) { 
    ... 
    findword(... x, y+1, ...); 
    findword(... x, y-1, ...); 
    ... 
} 

現在考慮當它被調用x == 5和y == 5（例如，任何其他位置將是一樣好）。我正在使用下面的縮進表示嵌套調用：

findword(... 5, 5, ...) 
    findword(..., 5, 6, ...) // x, y+1 
     ... 
    findword(..., 5, 5, ...) // x, y-1 
     // ouch! this is just the same as before, so it will eventually: 
     findword(..., 5, 6, ...) 
     findword(..., 5, 5, ...) 
      // ouch!... here again! shall I continue? 

現在，請思考一下算法。當找一個單詞時，首先選擇第一個字符，然後方向，然後測試在那個方向有多少個字母可以組成一個單詞。你實現的算法試圖找到不僅在行中，而且在任何隨機形狀中的單詞。