CODEWITHSUNDEEP
scalarecursionbinary-tree
KerenSi
KerenSi

Reputation: 389

Scala @tailrec 'Recursive call not in tail position' with return value

I'm trying to initialize binary tree using recursion.

@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
}

I get the error: "Recursive call not in tail position".

The difference here from other recursion example I saw, is that I need to call the recursive method twice, put the return values as right/left, and then return the node it self.

I tried to add the node a constructor that receive left & right, but I still get the same error. (although this is the last operation in the method)

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("")),)
}

Is it even possible to use the @tailrec annotation for my needs?

Upvotes: 0

Views: 1281

Answers (1)

Arne Claassen
Arne Claassen

Reputation: 14404

For a function to be tail recursive, the statement that produces the return value has to either be the final value or the function itself. The reason for this is that tail recursion sets up a trampoline where it acts as if the function had actually exited, and unwinds the call stack, but captures the values necessary for the recursive call so that it can call the method.

Traditional recursive calls will maintain the call stack as it recurses because it needs the stack when the recursive call returns. This will lead to a stack overflow, based on the size of the stack for each call and the number of recursive calls.

Tail recursive avoids this by being able to discard the call stack since it never has to come back to the original caller's context.

In order for your method to become tail recursive, it would have to maintain position in your tree and walk each branch one at a time (like a depth-first or breadth-first search), passing along the accumulator and position tracking, so that you can determine where to continue once you reach a leaf node. Then the call can become the exit condition of your recursive function.

Upvotes: 7

Related Questions