为什么这个函数不尾递归？

Question

我正在为类似结构的列表编写一个简单的contains方法。我希望针对尾递归进行优化，但无法弄清编译器为何抱怨。

Cons情况是尾递归的，但重复情况不是，即使它们在相同的数据结构上进行相同的调用。也许我不太了解尾递归。如果有人能解决这个问题，我将不胜感激。

  final def contains[B >: A](target: B): Boolean = this match{
    case Empty => false
    case Cons( h, t ) => h == target || t.contains( target )
    case Repeat( _, l ) => l.contains( target )
  } 

Answer 1

尾递归函数定义为其最后一条语句返回一个纯值或调用自身，并且它必须是唯一的递归调用。

首先，您的函数没有递归调用，因为您不会再次调用contains function。但是，您正在调用另一个实例的contains method。可以通过将逻辑移出类来解决。

但是，还有另一个常见问题。这：h == target || t.contains( target )不是尾递归调用，因为最后一个操作不是对contains的调用，而是用其结果执行的（[||）。

这里是重构方法。

def contains[A](list: MyList[A])(target: A): Boolean = {
  @annotation.tailrec
  def loop(remaining: MyList[A]): Boolean = 
    remaining match {
      case Empty => false
      case Cons(h, t) => if (h == target) true else loop(remaining = t)
      case Repeat(_, l) => loop(remaining = l)
    }
  loop(remaining = list)
}

如果您仍希望在类上使用方法，则可以将其转发以调用此辅助函数，并以this作为初始值。