does the stackoverflow test case make sense?


  • 0
    Z

    I have two recursion methods here:

    private void recursion(char[][] board, int row, int col) {
        if (row < 0 || row >= board.length || 
                col < 0 || col >= board[0].length) {
            return;
        } else if (board[row][col] != 'O') {
            return;
        }
        
        board[row][col] = 'V';
        recursion(board, row + 1, col);
        recursion(board, row - 1, col);
        recursion(board, row, col + 1);
        recursion(board, row, col - 1);
    }
    
    private void recursion1(char[][] board, int row, int col) {
        board[row][col] = 'V';
        if (row < board.length - 2 && board[row + 1][col] == 'O') {
            recursion1(board, row + 1, col);
        }
        if (row > 1 && board[row - 1][col] == 'O') {
            recursion1(board, row - 1, col);
        }
        if (col < board[0].length - 2 && board[row][col + 1] == 'O') {
            recursion1(board, row, col + 1);
        }
        if (col > 1 && board[row][col - 1] == 'O') {
            recursion1(board, row, col - 1);
        }
    }
    

    They are basically the same except for some extra recursion method call to reach boundaries in first recursion method. But only the second recursion method can pass the stack overflow test case. The first one causes stack overflow because of those extra recursion calls.

    If I am getting this correctly, I think they should both pass because they both traverse 'O's once. So they should not be distinguished by the stack overflow test case and I think that test case does not make sense. Otherwise, could we add another test case that the input is too big so that using recursion will cause stack overflow anyway? It should make sense because we can still use iteration + stack to fake recursion without stack overflow. Or maybe should there be no solution because using iteration + stack will reach time limit?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.