将正常递归转换为尾递归

Question

我想知道是否有一些通用方法将foo(...) + foo(...)的“正常”递归转换为最后一次尾递归调用。

例如（阶）：

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函数不再是递归函数。但是，蹦床monad是需要完成的计算的嵌套结构。最后，run是一个尾递归函数，遍历树状结构，解释它，最后在基本情况下返回值。

从RúnarBjanarson上蹦床的问题的文件：Stackless Scala With Free Monads

Answer 1

在存在一个简单的修改来递归调用的值的情况下，该操作可被移动到递归函数的前部。的典型的例子是尾递归模缺点，其中在这种形式的简单的递归函数：

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

这不是尾递归，被变换成

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

Alexlv的例子是变体这个的。

这是这样一个众所周知的情况，一些编译器（我知道的序言和方案的例子，但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(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()) 
    } 
} 

它是有效的，但我认为这显示复杂的递归解决方案如何丑陋成为你使其变形成为尾递归。此时，完全可能需要转向不同的模型。 Continuations或monadic gymnastics可能会更好。

你需要一个通用的方法来改变你的功能。没有一个。有帮助的方法，就是这样。

Answer 2

是的，它是可能的。通常它是通过一些内部定义的函数与累加器模式完成的，它具有一个附加参数，即所谓的累加器逻辑，例如计算列表长度。

例如正常的递归版本是这样的：

def length[A](xs: List[A]): Int = if (xs.isEmpty) 0 else 1 + length(xs.tail) 

，这不是一个尾递归版本，以消除最后的加法运算，我们要累积值，而在某种程度上，例如用蓄电池模式：

def length[A](xs: List[A]) = { 
    def inner(ys: List[A], acc: Int): Int = { 
    if (ys.isEmpty) acc else inner(ys.tail, acc + 1) 
    } 
    inner(xs, 0) 
} 

有点长的代码，但我认为我的想法清晰。因为你可以做到没有内部功能，但在这种情况下，你应该手动提供acc初始值。

Answer 3

我很确定它是而不是可能以您寻找一般情况的简单方式，但这取决于您是否允许进行更改。

尾递归函数必须作为while循环重写，但尝试使用while循环实现例如Fractal Tree。它是可能的，但你需要使用一个数组或集合来存储每个点的状态，这个数据可以存储在调用栈中存储的数据。

也可以使用trampolining。

Answer 4

我不知道这个问题的理论如何，但是递归实现即使在尾递归下也不会有效。例如，尝试运算pascal(30, 60)。我不认为你会得到一个堆栈溢出，但准备采取一个长时间的咖啡休息时间。

相反，可以考虑使用Stream或memoization：

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 5

这确实是可能的。我会这样做的方式是 从List（1）开始，并继续递归，直到你到达想要的 行。 值得注意的是，您可以对其进行优化：如果c == 0或c == r的值为1，并且计算第100行的第3列，您仍然只需计算前几行的前三个元素。 的工作尾递归的解决办法是这样的：

def pascal(c: Int, r: Int): Int = { 
    @tailrec 
    def pascalAcc(c: Int, r: Int, acc: List[Int]): List[Int] = { 
    if (r == 0) acc 
    else pascalAcc(c, r - 1, 
    // from let's say 1 3 3 1 builds 0 1 3 3 1 0 , takes only the 
    // subset that matters (if asking for col c, no cols after c are 
    // used) and uses sliding to build (0 1) (1 3) (3 3) etc. 
     (0 +: acc :+ 0).take(c + 2) 
     .sliding(2, 1).map { x => x.reduce(_ + _) }.toList) 
    } 
    if (c == 0 || c == r) 1 
    else pascalAcc(c, r, List(1))(c) 
} 

注释@tailrec实际上使编译器检查功能 实际上是尾递归。 如果c> r/2，pascal（c，r）== pascal（rc，r）..但留给阅读器，它可能可能会进一步优化，因为给定的行是对称的;）

Answer 6

累加器方法

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

它不会使栈溢出，但在大的行和列，但亚伦提到这还不算快。