特殊なケースを修正するか、この場合stackoverflowエラーをキャッチしてください。

Question

public boolean isConnected(int row, int col) { //helper Method 
     int i; 
     int j; 

     if (BOARD[row][col].isEmpty()) 
      return false; 
     for (i = row; i > 0; i--) 
      if (hasRed(i, col)) 
       return true; 
      else if (isEmpty(i, col)) 
       break; 
     for (i = row; i < ROWS; i++) 
      if (hasRed(i, col)) 
       return true; 
      else if (isEmpty(i, col)) 
       break; 
     for (i = col; i < COLS; i++) 
      if (hasRed(row, i)) 
       return true; 
      else if (isEmpty(row, i)) 
       break; 
     for (i = col; i > 0; i--) 
      if (hasRed(row, i)) 
       return true; 
      else if (isEmpty(row, i)) 
       break; 
     for (i = row, j = col; i > 0 && j < COLS; i--, j++) 
      if (hasRed(i, j)) 
       return true; 
      else if (isEmpty(i, j)) 
       break; 
     for (i = row, j = col; i < ROWS && j > 0; i++, j--) 
      if (hasRed(i, j)) 
       return true; 
      else if (isEmpty(i, j)) 
       break; 
     for (i = row, j = col; i > 0 && j > 0; i--, j--) 
      if (hasRed(i, j)) 
       return true; 
      else if (isEmpty(i, j)) 
       break; 
     for (i = row, j = col; i < ROWS && j < COLS; i++, j++) 
      if (hasRed(i, j)) 
       return true; 
      else if (isEmpty(i, j)) 
       break; 

     return false; 

    }  

//真の解がある場合、多くのテストケースの後にアルゴリズムを終了しようとすると、例外が発生する可能性がありますが、再帰のステップが行うと思われる理由があります元の問題を単純化するのではなく、実際に問題を拡大します。正しい解決策を得るチャンスを得るために、問題は、確かに偽を返すべき特定の条件において、アルゴリズムが以前に解決されたサブ問題をチェックし続けるなどして終了できないということである。

public boolean isConnected2(int rowCurr, int colCurr) { 

      if (rowCurr >= ROWS || rowCurr < 0 || colCurr < 0 || colCurr >= COLS) 
       return false;     //Base case 1 reached bounds of the 2d array 
      if (isEmpty(rowCurr, colCurr)) 
       return false; 
      if (isConnected(rowCurr, colCurr)) // base case 2 current piece is connected according to the method above 
       return true; 

      else { 
       return  isConnected2(rowCurr + 1, colCurr + 1)           
         || isConnected2(rowCurr - 1, colCurr - 1) 
         || isConnected2(rowCurr + 1, colCurr - 1) 
         || isConnected2(rowCurr - 1, colCurr + 1) 
         || isConnected2(rowCurr - 1, colCurr - 1) 
         || isConnected2(rowCurr + 1, colCurr) 
         || isConnected2(rowCurr - 1, colCurr) 
         || isConnected2(rowCurr, colCurr + 1) 
         || isConnected2(rowCurr, colCurr - 1); 
// if any of the above calls returns true we are done 


      } 

     } 

事は、私は、アルゴリズムが無限に再帰を引き起こす特殊なケースを処理する方法がわからない、と私は真の解決策がある場合は、その原因（||）演算子の性質のために確信していますそれは終了します。この場合、単にStackOverFlowエラーを処理し、それをメソッドの偽の戻り値として扱うほうがよいでしょうか？

Answer 1

プログラムにスタックオーバーフローを残さないでください。それを起こしてそれをキャッチすることは、JVMに大きな負担です。再帰が起こらないように修正してください。

Answer 2

任意の再帰関数を非再帰関数に変換することができます。

たとえば、何らかの種類のキューを使用します。 メソッドのさまざまなパラメータをキューにプッシュし、キューから一連のパラメータを連続してポップして評価します。その評価の結果、関数の呼び出し回数が増える場合は、新しいパラメータセットをキューにプッシュします。キューが大きすぎる場合や一定の時間が経過した場合は、終了できます。

この方法では、スタックの代わりにヒープを使用し、スタックオーバーフローの可能性を回避します。

Answer 3

public boolean isConnected2(int row, int col) { 
     int i; int j; 
     if (OutOfBounds(row, col)) 
      return false; 
     if (isEmpty(row, col)) 
      return false; 
     if (isConnected(row, col)) 
      return true; 

     else { 

      for (i = row; i > 0; i--) 
       if(isConnected(i,col)) 
        return true; 
       else if(isEmpty(i, col)) 
        break; 

      for (i = row; i < ROWS; i++) 
       if(isConnected(i,col)) 
        return true; 
       else if(isEmpty(i,col)) 
        break; 
      for (i = col; i < COLS; i++) 
       if(isConnected(row,i)) 
        return true; 
       else if(isEmpty(row,i)) 
        break; 
      for (i = col; i > 0; i--) 
       if(isConnected(row,i)) 
        return true; 
       else if(isEmpty(row,i)) 
        break; 
      for (i = row, j = col; i > 0 && j < COLS; i--, j++) 
       if(isConnected(i,j)) 
        return true; 
       else if(isEmpty(i,j)) 
        break; 
      for (i = row, j = col; i < ROWS && j > 0; i++, j--) 
       if(isConnected(i,j)) 
        return true; 
       else if(isEmpty(i,j)) 
        break; 
      for (i = row, j = col; i > 0 && j > 0; i--, j--) 
       if(isConnected(i,j)) 
        return true; 
       else if(isEmpty(i,j)) 
        break; 
      for (i = row, j = col; i < ROWS && j < COLS; i++, j++) 
       if(isConnected(i,j)) 
        return true; 
       else if(isEmpty(i,j)) 
        break; 

     } 
     return false; 

    } 

これはisConnected2と同じ方法ですが、これは同じですか？すべての方向に繰り返し伝搬するのではなく、2次元配列の各方向を1回だけチェックします。