當用於理解時遞歸調用不在尾部位置

Question

我不知道我是否做錯了什麼，或者它只是Scala編譯器的一個屬性 - 當我嘗試編譯此代碼時，出現提到的編譯錯誤：

@tailrec 
def shiftDown2(x: Int, bound: Int) { 
    val childOfX = chooseChild(x, bound) 
    for (child <- childOfX) { 
    swap(x, child) 
    shiftDown2(child, bound) 
    } 
} 

而下面的代碼編譯沒有問題：

@tailrec 
def shiftDown(x: Int, bound: Int) { 
    val childOfX = chooseChild(x, bound) 
    if (childOfX.isDefined) { 
    swap(x, childOfX.get) 
    shiftDown(childOfX.get, bound) 
    } 
} 

我相信，上面的代碼片段在語義上是相同且應與尾遞歸工作。

Answer 1

尾遞歸優化不適用於for循環內的遞歸調用，因爲for循環這裏只是調用foreach高階方法的語法糖。所以，你的代碼就相當於：

@tailrec 
def shiftDown2(x: Int, bound: Int) { 
    val childOfX = chooseChild(x, bound) 
    childOfX.foreach { child => 
    swap(x, child) 
    shiftDown2(child, bound) 
    } 
} 

scalac可以優化尾調用只有在遞歸的方法是尾直接調用本身 - 通過將其轉化爲類似字節碼while循環的東西。

不幸的是，在這裏不是這樣 - shiftDown2調用childOfX.foreach傳遞一個匿名函數。然後，foreach（可能）在該匿名函數上調用apply，並且該匿名函數最終再次調用shiftDown2。所以這是一個間接遞歸，不能通過scalac進行優化。這個限制源於JVM，它沒有本地尾部呼叫支持。