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

Question

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

Это первый раз, когда я использовал рекурсию, чтобы сделать что-то другое, кроме поиска факториала числа. Я создаю программу, чтобы найти слова на доске. Ниже приводится функция, которая приводит к segfaults:

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);
}

1

boggle c++gcc recursion segmentation-fault

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вы повторяете во всех направлениях во всех случаях. Рассмотрим эту уменьшенную версию рекурсии:

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?

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

3