logo标签列表

Scala尾递归

scalapattern-matchingtail-recursion
3

我有一个Scala函数，想知道是否可能将其转换为尾递归函数。

def get_f(f: Int => Int, x: Int, y: Int): Int = x match {
  case 0 => y
  case _ => f(get_f(f, x - 1, y))
}
@pavel 我没有收到任何错误，但我想避免未来的堆栈溢出，并将普通递归转换为尾递归。 - user6031489
5个回答
7
我看到这个函数将f函数递归地应用于结果，共x次。这与将其应用于y，x次相同。此外，我建议您使用if else而不是模式匹配。
@tailrec
def get_f(f: Int => Int, x: Int, y: Int): Int = 
    if(x == 0) y
    else get_f(f, x - 1, f(y))

加上@tailrec注解以确保它是尾递归的

4

这是可能的，但是你构建的方式意味着你需要使用跳板式来使其工作:

import scala.util.control.TailCalls._

def get_f(f: Int => Int, x: Int, y: Int): TailRec[Int] = x match {
  case 0 => done(y)
  case _ => tailcall(get_f(f, x - 1, y)).map(f)
}

val answer = get_f(_+1, 0, 24).result

您可以在这里阅读有关TailRec的信息，或者进行更高级的研究，查看此篇文章。

2

我可以告诉你使用foldLeft在Range上也可以达到相同的结果，像这样：

def get_f(f: Int => Int, x: Int, y: Int) =
  (0 until x).foldLeft(y)((acc, _) => f(acc))
这不是真的，可以看看这个链接：https://github.com/scala/scala/blob/v2.12.1/src/library/scala/collection/TraversableOnce.scala#L161 但是foldRight在内部创建了一个n元素的列表（因为它在reversed迭代器上调用了foldLeft），所以最好使用foldLeft。 - adamwy
2

让我们从减少非尾递归版本的参数开始，以便清楚地了解它实际上是做什么的：

def get_f(f: Int => Int, x: Int, y: Int) = {
  def get_f_impl(x: Int): Int = x match {
    case 0 => y
    case _ => f(get_f_impl(x - 1))
  }
  get_f_impl(x)
}

这个想法是，你将f函数应用x次于初始值y。因此，很明显你可以这样做以使其成为尾递归：

def get_f(f: Int => Int, x: Int, y: Int) = {
  @tailrec def get_f_impl(acc: Int, x: Int): Int = 
    if (x == 0) acc else get_f_impl(f(acc), x - 1) 
  get_f_impl(y, x)
}

REPL调查：

您的原始实现：

scala> get_f(_ + 1, 4, 0)
res6: Int = 4

您的实现（带参数优化）：
scala> get_f(_ + 1, 4, 0)
res0: Int = 4

Tailrec 实现：

scala> get_f(_ + 1, 4, 0)
res3: Int = 4

附注：对于更复杂的情况，跳板可能更适合：https://espinhogr.github.io/scala/2015/07/12/trampolines-in-scala.html

附注2：您也可以尝试：

它并不是真正的尾递归，因为get_f_impl调用了get_f。 - adamwy
抱歉。我的意思是 get_f_impl。 - dk14
我现在没有Scala REPL，所以我没有检查代码，但是这个函数的想法就是将f应用n次。 - dk14
我认为这是错误的，因为你使用f(x-1)的结果来调用get_f_impl而不是使用x-1。 - adamwy
是的，但在使用 f 进行转换后，您将此计数器转换为一个值。 - adamwy
显示剩余7条评论
0

根据之前的回复

 def get_f2( f: Int => Int, x: Int, y: Int) : Int = {
   def tail(y: Int, x: Int)(f: Int => Int) : Int = {
     x match {
       case 0 => y
       case _ => tail(f(y), x - 1)(f) : Int
     }
   }

   tail(y, x)(f)
 }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接