将正常递归转换为尾递归

Question

我想知道是否有一些通用方法来转换"正常"递归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)
}

---

函数式语言的一般解决方案,用于将递归函数转换为尾部调用等效函数:

一种简单的方法是将非尾递归函数包装在Trampolinemonad中.

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的关于蹦床的文章:Stackless Scala with Free Monads

Answer 1

如果对递归调用的值进行简单修改,则可以将该操作移动到递归函数的前面.这个经典的例子是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序列,这是最有效的方法(基于流的解决方案只是此解决方案的一个不同表达,可以缓存后续调用的结果).现在,您也可以通过从c0/r0(井,c0/r2)向前循环并按顺序计算每一行来解决您的问题 - 不同之处在于您需要缓存整个前一行.因此虽然这与fib有相似之处,但它在细节方面有很大差异,并且与原始的双递归解决方案相比效率也大大降低.

这是一个可以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())
  }
}

这是有效的,但我认为它显示了复杂的递归解决方案如何变形,因为你将它们变形成尾递归.在这一点上,完全可能值得转移到另一个模型. 延续或monadic体操可能会更好.

您想要一种通用的方式来转换您的功能.没有一个.有一些有用的方法,就是这些.

Answer 2

我不知道这个问题是如何理论的,但即使使用尾递归,递归实现也不会有效.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))
    }))

Answer 3

累加器方法

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

它不会溢出堆栈，但与大行和列一样，但亚伦提到它并不快。