为什么@tailrec 不允许这个看似尾递归的函数？

Question

这里的helper函数：

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

使用 @tailrec 注释时无法识别。

这真的不是尾递归吗？会不会导致堆栈溢出错误？

或者这只是编译器无法优化的尾递归函数？为什么？

Answer 1

helper 不会调用自己。它 returns 一个最终调用 helper 的函数，但这不是一回事。

换句话说：helper 不是 tail-recursive 因为它甚至不是（直接）递归的。

Scala 只能直接优化 tail-recursion。

Answer 2

问题是递归代码是创建一个函数值然后调用它，而不是直接调用方法。

如果您更改为方法语法，它将是尾递归的。

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

为什么@tailrec 不允许这个看似尾递归的函数？

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

recursion

scala