Member Avatar for Mistro116

If you would be so kind to go to this url, where I have already posted my problem and give me some tips on this forum or on the one already posted:

http://www.linuxquestions.org/questions/showthread.php?s=&threadid=387067

Thanks in advance,

P.S. This is really urgent, and it is probably a small problem.

Some updated code is here:

int RecursiveSearchLeft (char letters
			 [LETTERARRAYROWSIZE][LETTERARRAYCOLUMNSIZE],
			 int row, int column, WORD *words,
			 int wordIndex)
{
   int characterIndex = 0;
   
   if (letters [row][column] ==
       words [wordIndex].word [characterIndex] &&
       characterIndex <= strlen (words [wordIndex].word))
   {
      if (characterIndex == 0)
      {
	 words [wordIndex].startRow = row;
	 words [wordIndex].startCol = column;
      }
      
      characterIndex++;
      
      if (characterIndex == (strlen (words [wordIndex].word) - 1))
      {
	 return 1;
      }
      
      RecursiveSearchLeft (letters, row, column - 1, words,
			   wordIndex);
   }
   else if (column > NOBUFFERSTARTCOLUMN)
   {
      RecursiveSearchLeft (letters, row, column - 1, words,
			   wordIndex);
   }
   else if (column == NOBUFFERSTARTCOLUMN && row < NOBUFFERENDROW)
   {
      RecursiveSearchLeft (letters, row + 1, NOBUFFERSTARTCOLUMN,
			   words, wordIndex);
   }
   
   words [wordIndex].startRow = 0;
   words [wordIndex].startCol = 0;
   
   return 0;
}

Thanks, Mistro116

  • 2 Contributors
  • 3 Replies
  • 224 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Mistro116

Dani AI

Generated

Good summary from — the real problems here are (a) never storing/propagating the recursive call result and (b) the first posted version resetting the character index on every call. A correct recursive contract for this kind of search is simple: return 1 only when the entire word has been matched (base case), return 0 for mismatch or out-of-bounds, and always propagate the child result back to the caller. Common additional pitfalls seen in the thread: indexing into the word before checking bounds (access past the '\0'), calling strlen() on every recursive call, setting startRow/startCol on a partial match and never rolling it back, and returning 1 immediately after a single-character match instead of after a full match.

Practical checklist to avoid the bug:

  • Compute the word length once (in a wrapper) and pass it down; use size_t for the length and position.
  • Check the base case (pos == len) before indexing the word.
  • Check matrix bounds before accessing board[r][c].
  • Capture the recursive call result (int res = recurse(...)); return that result (don’t discard it).
  • Only commit start coordinates when the recursion returns success (commit inside if (res && pos == 0) …). This avoids the need to “clear” them on failure.

Example pattern (wrapper + helper) that follows the checklist:

int search_left(char board[ROWS][COLS], int r, int c,
                const char *word, int *startR, int *startC)
{
    size_t len = strlen(word);
    if (len == 0) return 0;
    return search_left_helper(board, r, c, word, len, 0, startR, startC);
}

int search_left_helper(char board[ROWS][COLS],
                       int r, int c, const char *word,
                       size_t len, size_t pos, int *startR, int *startC)
{
    if (pos == len) return 1;                /* full match */
    if (r < 0 || c < 0 || r >= ROWS || c >= COLS) return 0;
    if (board[r][c] != word[pos]) return 0;
    int matched = search_left_helper(board, r, c - 1, word, len, pos + 1, startR, startC);
    if (matched && pos == 0 && startR && startC) { *startR = r; *startC = c; }
    return matched;
}

Quick debugging tips: print (row,col,pos,board[row][col],word[pos]) during recursion, use a wrapper to compute length once, and run under valgrind/gdb for bounds errors. As later noted, fixing the return propagation resolved the problem.

Recommended Answers

All 3 Replies

Member Avatar for Mistro116

Using some debug lines, I have ALMOST completed the coding:

I'm basically stuck on why the following code will not return 1 when it finds the word. It does everything properly, comparing the letters, but then it gets to a point where a letter in the 2-d array is compared with nothing.. and thus it returns 0, why is this? I checked for null pointer / end line pointer for my word, but it just doesn't seem to work.

Here is some updates:

int RecursiveSearchLeft (char letters
			 [LETTERARRAYROWSIZE][LETTERARRAYCOLUMNSIZE],
			 int row, int column, WORD *words,
			 int wordIndex, int characterIndex)
{
   
   printf ("%c", letters [row][column]); /* Debug Line */
   printf ("%c\n", words [wordIndex].word [characterIndex]); /* Debug Line */
   if (words [wordIndex].word [characterIndex] == letters [row][column])
   {
      if (characterIndex == 0)
      {
	 words [wordIndex].startRow = row;
	 words [wordIndex].startCol = column;
      }
      
      if (characterIndex < strlen (words [wordIndex].word))
      {
	 RecursiveSearchLeft (letters, row, column - 1, words,
			      wordIndex, characterIndex + 1);
      }
      
      return 1;
   }
   else
   {
      characterIndex = 0;
      words [wordIndex].startRow = 0;
      words [wordIndex].startCol = 0;
      
      if (column > NOBUFFERSTARTCOLUMN)
      {
	 RecursiveSearchLeft (letters, row, column - 1, words,
			      wordIndex, characterIndex);
      }
      else if (column == NOBUFFERSTARTCOLUMN && row < NOBUFFERENDROW)
      {
	 RecursiveSearchLeft (letters, row + 1, NOBUFFERENDCOLUMN,
			      words, wordIndex, characterIndex);
      }
      
      return 0;
   }
}

Thanks,

Mistro116

Member Avatar for perniciosus

Hmm, a tricky question (well it took some time to figure out what you are doing anyway)... It looks as thought you dont save the recursive result anywhere so that even if you get a match somewhere in the recursion you will only report a match if you get a match on the first location... Due to the same reason you probably will report match as long as the first character matches since you will do the whole search and totally disregard the result and return 1 anyway...

*hint store result from RecursiveSearch and se if it matched before returning something...

Member Avatar for Mistro116

Thanks,

Yes the return value of the preprocesses was one issue. I've written all the code for this, but thanks for your input. I had to check a thousand things to make sure errors were avoided, but it worked :)

Thanks for the help.

Mistro116

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.