scala – 将正常递归转换为尾递归
|
我想知道是否有一些通用的方法来转换“正常”递归与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函数不再是递归函数.但是,Trampoline monad是一个需要完成计算的嵌套结构.最后,run是一个尾递归函数,它遍历树状结构,解释它,最后在基本情况下返回值. RúnarBjanarson关于Trampolines主题的论文：Stackless Scala With Free Monads 解决方法
如果对递归调用的值进行简单修改,则可以将该操作移动到递归函数的前面.这个经典的例子是Tail recursion modulo cons,这里有一个简单的递归函数：
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 optimisatin是无用的,因为您只是将第一个递归调用移动到另一个非尾部位置.达到尾递归解决方案的唯一方法是删除除递归调用之外的所有调用;如何做到完全取决于上下文,但需要找到一种完全不同的方法来解决问题. 碰巧,在某些方面,你的例子类似于经典的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序列,这是最有效的方法(基于流的解决方案只是该解决方案的不同表达,可以缓存后续调用的结果).现在, 这是一个可以有效计算pascal(30,60)的pascal三角形示例的方法： 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())
}
}
这是有效的,但我认为它表明了复杂的递归解决方案可能会变形,因为你将它们变形为尾递归.在这一点上,完全可能值得转移到另一个模型. Continuations或monadic gymnastics可能会更好. 您想要一种通用的方式来转换您的功能.没有一个.有一些有用的方法,就是这些. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |