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

Question

Это первый раз, когда я использовал рекурсию, чтобы сделать что-то другое, кроме поиска факториала числа. Я создаю программу, чтобы найти слова на изумительной доске. Ниже приводится функция, которая приводит к 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);
}

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?

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