瞭解如何將遞歸轉換爲蹦牀

Question

我最近閱讀了有關蹦牀作爲消除尾巴呼叫的方法。我想將我的某個功能轉換爲利用蹦牀的功能，但是我正在經歷艱難的時間（我從OO世界來到這裏）。

def buildTree (X:DenseMatrix[Double], Y:DenseVector[Double], minBucket:Int):Node = { 
     // Get the split variable, split point and data for this data 
     val (splitVar, splitPoint, leftX, leftY, rightX, rightY) = chooseSplit(X, Y, minBucket); 
     // If we couldn't find a split, then we have a leaf 
     if(splitVar == Double.NegativeInfinity){ 
      new Node(Y) 
     }else{ 
      // Otherwise recursively build the children and create yourself as a vertex 
      val left = buildTree(leftX, leftY, minBucket)) 
      val right = buildTree(rightX, rightY, minBucket)) 
      new Node(Y, splitVar, splitPoint, left, right) 
     } 
    } 

具體來說，如果我有兩個不同的遞歸調用我想在「更多（）」語句來使，是好嗎？

Answer 1

你的buildTree方法不會做任何尾巴呼叫，因此不能利用蹦牀。尾調用是當方法的返回值是另一個方法調用的結果時的優化。它允許將棧框架替換爲被調用的功能框架。如果沒有尾部調用優化，遞歸函數調用會導致堆棧的大小增加，可能導致堆棧溢出。您的buildTree方法確實會自行調用兩次，但原始堆棧幀必須保留，這樣兩個函數調用的結果才能組合起來以創建新的Node。

JVM沒有內置的對尾部全部優化的支持，但是Scala對函數調用自己的尾部調用有一些破解。 Scala用這個遞歸函數調用代替這些遞歸函數，並跳轉到函數的開始位置，有效地將遞歸轉換爲迭代。不幸的是，這不適用於共遞歸調用（例如，當方法A調用B調用A時）。蹦牀可以用在這裏，而不是基於特殊monad，或者濫用異常處理。沒有理由在其他地方使用蹦牀。