我想知道是否有什么通用方法可以将foo(...) + foo(...)作为对尾递归的最后一次调用来转换“正常”递归。
例如(scala):
def pascal(c: Int, r: Int): Int = {
if (c == 0 || c == r) 1
else pascal(c - 1, r - 1) + pascal(c, r - 1)
}函数语言将递归函数转换为尾调用等价物的通用解决方案:
一种简单的方法是将非尾递归函数封装在Trampoline monad中。
def pascalM(c: Int, r: Int): Trampoline[Int] = {
if (c == 0 || c == r) Trampoline.done(1)
else for {
a <- Trampoline.suspend(pascal(c - 1, r - 1))
b <- Trampoline.suspend(pascal(c, r - 1))
} yield a + b
}
val pascal = pascalM(10, 5).run所以pascal函数不再是递归函数了。然而,蹦床单片是一个嵌套结构的计算,需要做。最后,run是一个尾递归函数,它遍历树状结构,解释它,最后在基本情况下返回值。
Rúnar关于蹦床主题的论文:自由单子无堆栈Scala
发布于 2013-09-23 07:30:49
在对递归调用的值进行简单修改的情况下,可以将该操作移到递归函数的前面。典型的例子是尾递归模函数,其中有一个简单的递归函数:
def recur[A](...):List[A] = {
...
x :: recur(...)
}它不是尾递归,而是被转换为
def recur[A]{...): List[A] = {
def consRecur(..., consA: A): List[A] = {
consA :: ...
...
consrecur(..., ...)
}
...
consrecur(...,...)
}Alexlv的例子就是这方面的一个变体。
这是一种众所周知的情况,以至于一些编译器(我知道Prolog和Scheme示例,但Scalac没有这样做)可以检测简单的情况并自动执行这种优化。
将多个调用组合到递归函数的问题没有这样简单的解决方案。TMRC优化是无用的,因为您只是将第一个递归调用移动到另一个非尾位置。获得尾递归解决方案的唯一方法是删除除一个递归调用之外的所有调用;如何做到这一点完全依赖于上下文,但需要找到一种完全不同的方法来解决问题。
碰巧的是,在某些方面,您的示例类似于经典的Fibonnaci序列问题;在这种情况下,天真但优雅的双递归解决方案可以被从第0位开始循环的解决方案所取代。
def fib (n: Long): Long = n match {
case 0 | 1 => n
case _ => fib( n - 2) + fib( n - 1 )
}
def fib (n: Long): Long = {
def loop(current: Long, next: => Long, iteration: Long): Long = {
if (n == iteration)
current
else
loop(next, current + next, iteration + 1)
}
loop(0, 1, 0)
}对于Fibonnaci序列,这是最有效的方法(基于流的解决方案只是该解决方案的另一个表达式,可以缓存后续调用的结果)。现在,您还可以通过循环从c0/r0 (嗯,c0/r2)来解决您的问题,并按顺序计算每一行-区别在于您需要缓存整个上一行。因此,虽然这与fib有相似之处,但在细节上却有很大的不同,而且与原来的双递归解决方案相比,效率也要低得多。
下面是pascal三角形示例的一种方法,它可以有效地计算pascal(30,60):
def pascal(column: Long, row: Long):Long = {
type Point = (Long, Long)
type Points = List[Point]
type Triangle = Map[Point,Long]
def above(p: Point) = (p._1, p._2 - 1)
def aboveLeft(p: Point) = (p._1 - 1, p._2 - 1)
def find(ps: Points, t: Triangle): Long = ps match {
// Found the ultimate goal
case (p :: Nil) if t contains p => t(p)
// Found an intermediate point: pop the stack and carry on
case (p :: rest) if t contains p => find(rest, t)
// Hit a triangle edge, add it to the triangle
case ((c, r) :: _) if (c == 0) || (c == r) => find(ps, t + ((c,r) -> 1))
// Triangle contains (c - 1, r - 1)...
case (p :: _) if t contains aboveLeft(p) => if (t contains above(p))
// And it contains (c, r - 1)! Add to the triangle
find(ps, t + (p -> (t(aboveLeft(p)) + t(above(p)))))
else
// Does not contain(c, r -1). So find that
find(above(p) :: ps, t)
// If we get here, we don't have (c - 1, r - 1). Find that.
case (p :: _) => find(aboveLeft(p) :: ps, t)
}
require(column >= 0 && row >= 0 && column <= row)
(column, row) match {
case (c, r) if (c == 0) || (c == r) => 1
case p => find(List(p), Map())
}
}它是有效的,但我认为它显示了当您将复杂的递归解决方案变形为尾递归时,它们会变得多么丑陋。在这一点上,可能值得完全转向另一种模式。延续或一元体操可能更好。
您需要一种通用的方法来转换您的函数。根本就没有。有很多有用的方法,仅此而已。
发布于 2013-09-22 21:46:49
我不知道这个问题有多理论性,但是即使使用尾递归,递归实现也不会有效。例如,尝试计算pascal(30, 60)。我不认为你会有堆积如山的溢出,但准备好休息一段时间的咖啡。
相反,请考虑使用Stream或回忆录
val pascal: Stream[Stream[Long]] =
(Stream(1L)
#:: (Stream from 1 map { i =>
// compute row i
(1L
#:: (pascal(i-1) // take the previous row
sliding 2 // and add adjacent values pairwise
collect { case Stream(a,b) => a + b }).toStream
++ Stream(1L))
}))发布于 2015-10-22 00:23:58
累加器法
def pascal(c: Int, r: Int): Int = {
def pascalAcc(acc:Int, leftover: List[(Int, Int)]):Int = {
if (leftover.isEmpty) acc
else {
val (c1, r1) = leftover.head
// Edge.
if (c1 == 0 || c1 == r1) pascalAcc(acc + 1, leftover.tail)
// Safe checks.
else if (c1 < 0 || r1 < 0 || c1 > r1) pascalAcc(acc, leftover.tail)
// Add 2 other points to accumulator.
else pascalAcc(acc, (c1 , r1 - 1) :: ((c1 - 1, r1 - 1) :: leftover.tail ))
}
}
pascalAcc(0, List ((c,r) ))
}它不会溢出堆栈,但是就像在大行和大列上一样,但是Aaron提到它不是很快的。
https://stackoverflow.com/questions/18945141
复制相似问题