gpt4 book ai didi

scala - 进行递归调用,尾递归

转载 作者:行者123 更新时间:2023-12-01 07:50:21 24 4
gpt4 key购买 nike

我有以下递归函数

trait SequenceGenerator[T] {
def program(l: List[T])(implicit rule: ProductionRule[T]): List[T] = {
l.flatMap(rule.generate)
}

def sequenceNumber(seed: List[T], number: Int)(implicit rule: ProductionRule[T]): List[T] = {
number match {
case 1 => program(seed)
case a => program(sequenceNumber(seed, a - 1))
}
}
}

我想不出办法让 sequenceNumber尾递归。

最佳答案

将方法转换为 tailrec 背后的想法是将每个下一个计算步骤放入累加器,然后将此累加器传递回方法,以便在下一步中您可以返回累加器或使用根据您的步骤修改的新累加器再次调用此方法。

所以你会得到这样的东西:

trait SequenceGenerator[T] {

def program(l: List[T])(implicit rule: ProductionRule[T]): List[T] = l.flatMap(rule.generate)

def sequenceNumber(seed: List[T], number: Int)(implicit rule: ProductionRule[T]): List[T] = {

@tailrec
def tailRec(number: Int, acc: List[T]): List[T] = number match {
case 1 => acc
case a => tailRec(a-1,program(acc))
}

tailRec(number,program(seed))

}

}

但仅供引用,还有更先进的技术来构建尾递归,称为 Trampoling .可以使用 scala.util.control.TailCalls 来实现例如。

我不太擅长这种技术,但它看起来像这样:
import TailCalls._

trait SequenceGenerator[T] {

def program(l: TailRec[List[T]])(implicit rule: ProductionRule[T]):TailRec[List[T]] = {
l.map(_.flatMap(rule.generate))
}

def sequenceNumber(seed: TailRec[List[T]], number: TailRec[Int])(implicit rule: ProductionRule[T]): TailRec[List[T]] = {
number flatMap {
case 1 => tailcall(program(seed))
case a => tailcall(program(sequenceNumber(seed, done(a - 1))))
}
}

}
sequenceNumber不能在这里标记为tailrec,但它实际上是“背景”中的tailrec。要获得真实的计算结果,您需要调用 sequenceNumber(done(...),done(...)).result

关于scala - 进行递归调用,尾递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55671713/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com