0

我最近读到蹦床是一种消除尾声的方法。我想将我的一个功能转换为利用蹦床的功能，但我很难开始（我来自 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)
        }
    }

具体来说，如果我想在“More()”语句中进行两个不同的递归调用，可以吗？

4

1 回答 1

2

您的buildTree方法不会进行任何尾调用，因此无法利用蹦床。当一个方法的返回值是另一个方法调用的结果时，尾调用是一种优化。它允许将堆栈帧替换为被调用函数的堆栈帧。如果没有尾调用优化，递归函数调用会导致栈变大，可能导致栈溢出。您的 buildTree 方法确实会调用自己两次，但必须保留原始堆栈框架，以便可以将两个函数调用的结果结合起来创建新的Node.

JVM 没有内置支持 tail all 优化，但 Scala 对函数调用自身的尾部调用有一个 hack。Scala 将这些递归函数调用替换为跳转到函数的开头，从而有效地将递归转换为迭代。不幸的是，这不适用于协同递归调用（例如，当方法 A 调用 B 而调用 A 时）。Trampolining 可以在这里使用，或者基于特殊的 monad，或者滥用异常处理。没有理由在其他地方使用蹦床。

于 2014-04-02T16:13:10.247 回答