深度遞迴在 Java 中是有問題的

考慮以下使用遞迴新增兩個正數的天真方法：

public static int add(int a, int b) {
    if (a == 0) {
        return b;
    } else {
        return add(a - 1, b + 1);  // TAIL CALL
    }
}

這在演算法上是正確的，但它有一個主要問題。如果你用一個大的 a 呼叫 add，它會在任何版本的 Java（至少）Java 9 上使用 StackOverflowError 崩潰。

在典型的函式程式語言（以及許多其他語言）中，編譯器優化尾遞迴 。編譯器會注意到對 add 的呼叫（在標記行處）是一個尾呼叫 ，並且會有效地將遞迴重寫為迴圈。這種轉換稱為尾呼叫消除。

但是，當前的 Java 編譯器不執行尾部呼叫消除。 （這不是一個簡單的疏忽。這有很多技術原因;見下文。）相反，add 的每次遞迴呼叫都會導致線上程堆疊上分配一個新幀。例如，如果你呼叫 add(1000, 1)，它將需要 1000 遞迴呼叫才能得到答案 1001。

問題是建立執行緒時 Java 執行緒堆疊的大小是固定的。 （這包括單執行緒程式中的主執行緒。）如果分配的堆疊幀太多，則堆疊將溢位。JVM 將檢測到這一點並丟擲一個 StackOverflowError。

解決這個問題的一種方法是簡單地使用更大的堆疊。有 JVM 選項可以控制堆疊的預設大小，你還可以將堆疊大小指定為 Thread 建構函式引數。不幸的是，這隻會推遲堆疊溢位。如果你需要做一個需要更大堆疊的計算，那麼 StackOverflowError 會回來。

真正的解決方案是識別可能進行深度遞迴的遞迴演算法，並在原始碼級別手動執行尾呼叫優化。例如，我們的 add 方法可以重寫如下：

public static int add(int a, int b) {
    while (a != 0) {
       a = a - 1;
       b = b + 1;
    }
    return b;
}

（顯然，有更好的方法可以新增兩個整數。上面只是為了說明手動尾部消除的效果。）

為什麼在 Java 中沒有實現尾呼叫消除（尚未）

將尾呼叫消除新增到 Java 並不容易的原因有很多。例如：

• 一些程式碼可以依賴於 StackOverflowError（例如）對計算問題的大小設定一個界限。
• 在決定是否允許非特權程式碼執行特權操作時，沙盒安全管理器通常依賴於分析呼叫堆疊。

正如 John Rose 在 “VM 中的尾呼叫”中所說 ：

“刪除呼叫者的堆疊幀的效果對於某些 API 是可見的，特別是訪問控制檢查和堆疊跟蹤。就好像呼叫者的呼叫者直接呼叫了被呼叫者。呼叫者擁有的任何特權在控制轉移到呼叫者之後被丟棄。然而，在轉移控制之前計算被呼叫方法的連結和可訪問性，並考慮尾呼叫呼叫者。

換句話說，尾部呼叫消除可能導致訪問控制方法錯誤地認為可信程式碼正在呼叫安全敏感 API。