Scala @tailrec'递归调用不在尾部位置'，带有返回值

Question

我正在尝试使用递归初始化二叉树。

@tailrec
def expressionToTreeNodeConversion(expression:String): TreeNode = {

    var chars = expression.toCharArray

    var operatorIndex = findIndexOfMiddleOperator(chars)
    var isOperator = true
    while(operatorIndex==(-1) & isOperator) {

      if (!(chars.contains(OPEN_BRACKET_CHAR) | chars.contains(CLOSE_BRACKET_CHAR)))
        isOperator = false
      else {
        chars = chars.slice(1, chars.length-1)
        operatorIndex = findIndexOfMiddleOperator(chars)
      }
    }

    //If this is an operand
    if (!isOperator)
      return new OperandNode(chars.mkString(""))

    //If this is an operator, recursively call for sub nodes
    val  node = chars(operatorIndex).toString match {
      case AND => new AndNode()
      case OR => new OrNode()
    }

    node.left = expressionToTreeNodeConversion(chars.slice(0, operatorIndex).mkString(""))
    node.right = expressionToTreeNodeConversion(chars.slice(operatorIndex + 1, chars.length).mkString(""))

    node
}

我收到错误：“递归调用不在尾部位置”。

这里与我看到的其他递归示例的不同之处在于，我需要调用两次递归方法，将返回值设置为右/左，然后自行返回节点。

我试图向节点添加一个接收左右的构造函数，但我仍然遇到相同的错误。（虽然这是方法中的最后一个操作）

val  node = chars(operatorIndex).toString match {
  case AND => new AndNode(expressionToTreeNodeConversion(chars.slice(0, operatorIndex).mkString("")),expressionToTreeNodeConversion(chars.slice(operatorIndex + 1, chars.length).mkString("")))
  case OR => new OrNode(expressionToTreeNodeConversion(chars.slice(0, operatorIndex).mkString("")),)
}

甚至可以根据我的需要使用 @tailrec 注释吗？

Answer 1

对于尾递归的函数，产生返回值的语句必须是最终值或函数本身。这样做的原因是尾递归设置了一个蹦床，它就像函数实际退出一样，并展开调用堆栈，但捕获递归调用所需的值，以便它可以调用该方法。

传统的递归调用会在递归时维护调用堆栈，因为在递归调用返回时它需要堆栈。这将导致堆栈溢出，具体取决于每次调用的堆栈大小和递归调用的数量。

尾递归通过能够丢弃调用堆栈来避免这种情况，因为它永远不必回到原始调用者的上下文。

为了使您的方法成为尾递归，它必须保持树中的位置并一次遍历每个分支（如深度优先或广度优先搜索），传递累加器和位置跟踪，以便您可以确定到达叶节点后继续的位置。然后调用可以成为递归函数的退出条件。