將正常遞歸轉換爲尾遞歸

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

它不會使棧溢出，但在大的行和列，但亞倫提到這還不算快。