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

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 方法。
这可以通过将逻辑移到 class.

之外来解决

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

这是重构它的方法。

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

如果您仍然想要方法在您的 class 上，您可以转发它以调用此辅助函数，传递 this 作为初始值。

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

Why is this function not tail recursive?

scala

recursion

tail-recursion