CODEWITHSUNDEEP
scalarecursion
Tom Robinson
Tom Robinson

Reputation: 97

Why does @tailrec not permit this seemingly tail recursive function?

The helper function here:

def zipWith[B]: (MyList[B], (A, B) => B) => MyList[B] = {
  (list, function) => {
    def helper: (MyList[B], MyList[A], MyList[B]) => MyList[B] = {
      (consList, originalList, modList) =>
        val wrapList = if (modList.isEmpty) list else modList
        if (originalList.tail.isEmpty) consList ++ NewList(function(originalList.head, wrapList.head), EmptyList)
        else helper(consList ++ NewList(function(originalList.head, wrapList.head), EmptyList),
          originalList.tail,
          modList.tail)
    }
    helper(EmptyList, this, list)
  }
}

Is not recognised when using the @tailrec annotation.

Is this genuinely not tail-recursive? Could it cause a stack overflow error?

Or is this just a tail recursive function that the compiler is unable to optimise? Why?

Upvotes: 0

Views: 119

Answers (2)

Tim
Tim

Reputation: 27356

The problem is that the recursive code is creating a function value and then calling it, rather than calling a method directly.

If you change to method syntax it will be tail recursive.

@annotation.tailrec
def helper(consList: MyList[B], originalList: MyList[A], modList: MyList[B]): myList[B] = {
    val wrapList = if (modList.isEmpty) list else modList
    if (originalList.tail.isEmpty) consList ++ NewList(function(originalList.head, wrapList.head), EmptyList)
    else helper(consList ++ NewList(function(originalList.head, wrapList.head), EmptyList),
      originalList.tail,
      modList.tail)
}

Upvotes: 1

Jörg W Mittag
Jörg W Mittag

Reputation: 369430

helper doesn't call itself. It returns a function which eventually calls helper, but that's not the same thing.

In other words: helper is not tail-recursive because it is not even (direct-)recursive.

Scala can only optimize direct tail-recursion.

Upvotes: 2

Related Questions