1 
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;

    }

//可能导致异常的主要方法在许多测试用例尝试后的算法总是在有一个真正的解决方案时终止，但可能会或可能不会因错误的解决方案而终止，我猜的原因是递归步骤并没有简化原始问题但实际上扩展了它！为了有机会获得正确的解决方案，问题是在某些肯定应该返回 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 错误并将其视为方法的错误返回不是更好吗？

4

3 回答 3

2

任何递归函数都可以转换为非递归函数。

例如，使用某种队列。将方法的不同参数推isConnected2送到队列中，然后不断地从队列中弹出一组参数，并对它们进行评估。如果该评估导致对该函数的更多调用，则将一组新参数推送到队列中。然后，如果队列太大或经过一定时间后，您可以终止。

这样您就可以使用堆而不是堆栈，并避免堆栈溢出的可能性。

于 2012-05-08T00:00:33.013 回答
1

永远不要在程序中留下堆栈溢出。让它发生并抓住它对 JVM 来说是一个巨大的负担。修复您的递归，使其不会发生。

于 2012-05-08T12:42:31.033 回答
0 
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 是否类似？现在它只检查 2d 数组中的每个方向一次，而不是在所有方向上重复传播

于 2012-05-08T11:51:52.983 回答