C++ рекурсия segfault. Можете ли вы помочь мне понять, что я делаю неправильно?

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? 

Теперь подумайте об алгоритме. Когда вы ищете слово, сначала выбираете первый символ, затем направлении, а затем тестируете в в этом направлении сколько букв может составлять слово. Алгоритм, который вы реализовали, пытается найти слова не только в строках, но и в любой случайной форме.