将普通递归转换为尾递归 [英] Convert normal recursion to tail recursion

问题描述

我想知道是否有某种通用方法可以将"c">作为对尾部递归的最后一次调用来转换正常"递归.

I was wondering if there is some general method to convert a "normal" recursion with foo(...) + foo(...) as the last call to a tail-recursion.

例如(标量):

def pascal(c: Int, r: Int): Int = {
 if (c == 0 || c == r) 1
 else pascal(c - 1, r - 1) + pascal(c, r - 1)
}

---

功能语言将递归函数转换为等效的尾调用的一般解决方案:

---

A general solution for functional languages to convert recursive function to a tail-call equivalent:

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

A simple way is to wrap the non tail-recursive function in the 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是一个尾递归函数，它遍历树状结构并对其进行解释，最后在基本情况下返回该值.

So the pascal function is not a recursive function anymore. However, the Trampoline monad is a nested structure of the computation that need to be done. Finally, run is a tail-recursive function that walks through the tree-like structure, interpreting it, and finally at the base case returns the value.

来自RúnarBjanarson的关于蹦床主题的论文:带有免费Monad的无堆栈Scala

A paper from Rúnar Bjanarson on the subject of Trampolines: Stackless Scala With Free Monads

推荐答案

在对递归调用的值进行简单修改的​​情况下，可以将该操作移到递归函数的前面.经典的例子是 Tail递归模态缺点，其中有一个简单的递归函数，形式如下:

In cases where there is a simple modification to the value of a recursive call, that operation can be moved to the front of the recursive function. The classic example of this is Tail recursion modulo cons, where a simple recursive function in this form:

def recur[A](...):List[A] = {
  ...
  x :: recur(...)
}

不是尾递归的

转换为

which is not tail recursive, is transformed into

def recur[A]{...): List[A] = {
   def consRecur(..., consA: A): List[A] = {
     consA :: ...
     ...
     consrecur(..., ...)
   }
   ...
   consrecur(...,...)
}

Alexlv的示例是这种情况的变体.

Alexlv's example is a variant of this.

这是一个众所周知的情况，一些编译器(我知道Prolog和Scheme的示例，但Scalac不能这样做)可以检测到简单情况并自动执行此优化.

This is such a well known situation that some compilers (I know of Prolog and Scheme examples but Scalac does not do this) can detect simple cases and perform this optimisation automatically.

结合多个对递归函数的调用的问题没有这样简单的解决方案. TMRC optimisatin是无用的，因为您只是将第一个递归调用移动到另一个非尾部位置.达到尾部递归解决方案的唯一方法是除去除一个递归调用外的所有调用；如何做到这一点完全取决于上下文，但是需要找到一种完全不同的方法来解决问题.

Problems combining multiple calls to recursive functions have no such simple solution. TMRC optimisatin is useless, as you are simply moving the first recursive call to another non-tail position. The only way to reach a tail-recursive solution is remove all but one of the recursive calls; how to do this is entirely context dependent but requires finding an entirely different approach to solving the problem.

碰巧，您的示例在某些方面类似于经典的Fibonnaci序列问题；在那种情况下，可以用从第0个数字开始循环的一个简单但优雅的双递归解决方案代替.

As it happens, in some ways your example is similar to the classic Fibonnaci sequence problem; in that case the naive but elegant doubly-recursive solution can be replaced by one which loops forward from the 0th number.

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 有相似之处，但在细节上有很大不同，并且效率远低于原始的双递归解决方案.

For the Fibonnaci sequence, this is the most efficient approach (a streams based solution is just a different expression of this solution that can cache results for subsequent calls). Now, you can also solve your problem by looping forward from c0/r0 (well, c0/r2) and calculating each row in sequence - the difference being that you need to cache the entire previous row. So while this has a similarity to fib, it differs dramatically in the specifics and is also significantly less efficient than your original, doubly-recursive solution.

这是您的pascal三角形示例的一种方法，可以有效地计算pascal(30,60):

Here's an approach for your pascal triangle example which can calculate pascal(30,60) efficiently:

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

这是有效的，但是我认为它显示了当您将它们变形为尾递归时，复杂的递归解决方案会变得多么丑陋.在这一点上，可能有必要完全转向其他模型. 继续或

It's efficient, but I think it shows how ugly complex recursive solutions can become as you deform them to become tail recursive. At this point, it may be worth moving to a different model entirely. Continuations or monadic gymnastics might be better.

您想要一种通用的方法来转换您的功能.没有一个.有很多有用的方法.

You want a generic way to transform your function. There isn't one. There are helpful approaches, that's all.

这篇关于将普通递归转换为尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！