Функция 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
.
Это действительно не хвостовая рекурсия? Может ли это вызвать ошибку переполнения стека?
Или это просто хвостовая рекурсивная функция, которую компилятор не может оптимизировать? Почему?
helper
не называет себя. Он возвращает функцию, которая в итоге вызывает helper
, но это не одно и то же.
Другими словами: helper
не хвостовая рекурсия, потому что она даже не (прямая) рекурсия.
Scala может оптимизировать только прямую хвостовую рекурсию.
Проблема в том, что рекурсивный код создает значение функции, а затем вызывает его, а не вызывает метод напрямую.
Если вы измените синтаксис метода, он будет рекурсивным.
@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)
}