递归过程中第一个过程调用出现堆栈溢出

Question

我遇到一个堆栈溢出错误，我知道这是由于一个bug引起的，但我不明白为什么第一个递归过程中会发生堆栈溢出，而不是在调用递归过程时发生。

在解决数独谜题的方法中，以下是递归代码段（黑体字是递归调用）：

    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语句上。这是为什么呢？

- Tyler Durden

---

你到底在打印什么？ - AndyFaizan

@AndyFaizan 没有什么，打印语句只是为了演示堆栈溢出发生在递归过程的第一次调用上，而不是在递归过程本身的调用上。 - Tyler Durden

当堆栈溢出时，它有多深？当堆栈变得太大而无法进一步扩展时，就会报告错误。如果您的例程中的第一个语句是打印调用（这将进一步扩展堆栈），那么错误将在那里被检测到。 - Hot Licks

Answer 1

这样想吧：每次调用System.out.println时，您会将4（或更多）个附加堆栈帧推到堆栈顶部，就像错误中所示。在递归调用自己的函数之前，这些堆栈帧将被弹出堆栈。因此，堆栈的深度如下所示：

• 您的代码，1级
• println，5级
• 您的代码，2级
• println，6级
• 您的代码，3级
• println，7级
• ...
• 您的代码，n级
• println，n + 4级
• 您的代码，n + 1级
• ...

假设每个级别占用相同的堆栈内存（实际上不是真的，但对于这种分析来说可能足够接近），那么对于堆栈大小的任何特定限制，println代码都应首先突破它。

实际上，只需要其他过程在堆栈上使用比您的过程更多的内存即可，这总是会发生。如果它使用较少的内存，它仍然可能发生（因为对于任何给定级别，它都是在调用您的代码之前调用的）。也许，由于println调用仅用于证明这一点，您在下一行中调用的基数排序代码以前曾触发了这种行为。它可能比您自己的方法使用更多的堆栈空间（这似乎很可能；您只有6个本地变量，大多数表达式都非常简单）。

- Jules

---

是的，除非solveSudokuGrid一帧所需的堆栈量大于由print调用的4（或更多）方法所需的堆栈，否则失败将始终在print调用中被检测到。 - Hot Licks

Answer 2

因为您在那个点超出了堆栈边界。这里的维基百科

似乎System.out.println最终会调用BufferedWriter.write，这也是一个递归函数，最终会导致堆栈溢出。

- PbxMan