scala：使函数尾递归

Question

我在 scala 中有以下功能：

def is_in[T](e: T, as: List[T]) : Boolean = as match
{
  case Nil => false;
  case x::xs => e == x || is_in(e, xs);
}

现在我想让这个函数尾递归。我的想法如下：

// tail recursive:

def is_in[T](e: T, as:List[T]) : Boolean =
{
  @tailrec
  def is_in_tailrec[T](e: T, as:List[T], acc: Boolean) : Boolean =
  {
    as match
    {
      case Nil => acc;
      case x::xs => is_in_tailrec(... here I got stuck ...);
    }
  }
  is_in_tailrec(e, as, 1);
}

有人可以给我建议如何使这个函数尾递归吗？

Answer 1

其实这里不需要带累加器的辅助方法。只需检查 e == x returns false，然后用列表的其余部分调用该方法，否则 return true:

  def is_in[T](e: T, as: List[T]): Boolean = as match {
    case Nil => false
    case x :: _ if e == x => true
    case _ :: xs => is_in(e, xs)
  }

Answer 2

我的建议是

{
    case Nil => acc
    case _ if acc => acc
    case x :: xs => is_in_tailrec(e, xs, x == e)
}

或偶数

{
    case x :: xs if !acc => is_in_tailrec(e, xs, x == e)
    case _ => acc
}

Answer 3

I wonder why the one who posted the answer with the helper method which was similar to my version deleted his post. I just wanted to analyse that and see what my mistakes are ...

我猜你的意思是

def is_in[T](e: T, as: List[T]) : Boolean = {
  @tailrec
  def is_in_tailrec[T](e: T, as: List[T], acc: Boolean): Boolean = as match {
    case Nil     => acc
    case x :: xs => is_in_tailrec(e, xs, e == x || acc)
  }

  is_in_tailrec(e, as, false)
}

由于is_in_tailrec中的T和e总是与is_in中的T和e相同，因此可以重写作为

def is_in[T](e: T, as: List[T]) : Boolean = {
  @tailrec
  def is_in_tailrec(as: List[T], acc: Boolean): Boolean = as match {
    case Nil     => acc;
    case x :: xs => is_in_tailrec(xs, e == x || acc)
  }

  is_in_tailrec(as, false)
}

Answer 4

你的函数已经是尾递归了。如果你将它标记为 @annotation.tailrec，它编译得很好。

scala：使函数尾递归

scala: make a function tail recursive

scala

tail-recursion