标量:使函数尾递归

问题描述 投票:1回答:4

我在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);
}

有人可以给我一个建议,让我如何使该函数尾部递归?

scala tail-recursion
4个回答
0
投票

我的建议是

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

5
投票

实际上,您在这里不需要带累加器的辅助方法。只需检查e == x是否返回false,然后使用列表的其余部分调用该方法,否则返回true:


1
投票

您的函数已经是尾递归了。如果将其标记为@annotation.tailrec,则可以正常编译。


0
投票

我不知道为什么用与我的版本相似的帮助方法发布答案的人删除了他的帖子。我只是想分析一下,看看我的错误是什么...

© www.soinside.com 2019 - 2024. All rights reserved.