java - 递归过程中的第一个过程调用发生堆栈溢出

Question

由于我理解的错误，我收到堆栈溢出错误，但我不明白为什么堆栈溢出发生在递归过程的第一个过程而不是调用递归过程。

在解决数独谜题的方法中，这里是递归部分(粗体文本是递归调用:

    System.out.print(""); <b><= stack overflow occurs here</b>
    int[] move_quality_sorted_keys = Sorting_jsc.RadixSort_unsigned_1( move_quality );
    for( int xPossibleMove = 1; xPossibleMove <= ctPossibleMoves; xPossibleMove++ ){
        int xMove = move_quality_sorted_keys[ctPossibleMoves - xPossibleMove + 1];
        int[][] new_grid = new int[10][10];
        for( int xRow = 1; xRow <= 9; xRow++ )
            for( int xColumn = 1; xColumn <= 9; xColumn++ )
                new_grid[xRow][xColumn] = grid[xRow][xColumn];
        new_grid[move_row[xMove]][move_column[xMove]] = move_value[xMove];
        <b>int[][] solution = solveSudokuGrid( new_grid );</b>
        if( solution != null ) return solution;
    }

堆栈溢出错误如下(注意它发生在 System.out.print() 语句中):

Exception in thread "main" java.lang.StackOverflowError
    at java.io.BufferedWriter.write(BufferedWriter.java:221)
    at java.io.Writer.write(Writer.java:157)
    at java.io.PrintStream.write(PrintStream.java:525)
    at java.io.PrintStream.print(PrintStream.java:669)
    at Euler100.solveSudokuGrid(Euler100.java:2458)
    at Euler100.solveSudokuGrid(Euler100.java:2467)
    at Euler100.solveSudokuGrid(Euler100.java:2467)
    at Euler100.solveSudokuGrid(Euler100.java:2467)
    at Euler100.solveSudokuGrid(Euler100.java:2467)
    at Euler100.solveSudokuGrid(Euler100.java:2467)
    at Euler100.solveSudokuGrid(Euler100.java:2467)
    at Euler100.solveSudokuGrid(Euler100.java:2467)
    at Euler100.solveSudokuGrid(Euler100.java:2467)
    at Euler100.solveSudokuGrid(Euler100.java:2467)

我希望堆栈溢出发生在对 solveSudokuGrid 的调用上，而不是在 print 语句上。这是为什么？

Answer 1

这样看:每次调用 System.out.println 时，都会将 4 个(或更多)额外的堆栈帧推到堆栈顶部，如您在错误中看到的那样。然后在递归调用自己的函数之前将它们从堆栈中弹出。因此堆栈的深度是这样的:

• 你的代码，1级
• println，5 个级别
• 你的代码，2 级
• println，6 级
• 你的代码，3 个级别
• println，7 个级别
• ...
• 你的代码，n 级
• println, n + 4 级
• 你的代码，n + 1 级
• ...

假设每个级别占用相同数量的堆栈内存(这实际上不是真的，但对于这种分析可能足够接近)很明显，对于堆栈大小的任何特定限制，println代码会先突破它。

所有实际需要的是其他过程在堆栈上使用比您的过程更多的内存，这总是会发生。如果它使用较少，它可能仍然会发生(因为对于任何给定的级别，它在您的代码之前被调用)，并且大概因为 println 调用只是为了证明这一点，您在下一行调用的基数排序代码是之前触发的行为。它可能比您自己的方法使用更多的堆栈空间(这似乎很有可能；您只有 6 个局部变量，而且您的大部分表达式都非常简单)。