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

Time:03-18

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?

CodePudding user response:

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.

  • Related