各種書籍、文章、博客文章表明，將遞回函式重寫為尾遞回函式可以使其更快。毫無疑問，對于諸如生成斐波那契數或計算階乘之類的瑣碎情況，它會更快。在這種情況下，有一種典型的重寫方法 - 通過使用“輔助函式”和中間結果的附加引數。
TAIL RECURSION很好地描述了尾遞回函式和非尾遞回函式之間的區別，以及如何將遞回函式變成尾遞回函式的可能方法。這種重寫的重要之處在于——函式呼叫的數量是相同的（重寫之前/之后），不同之處在于這些呼叫是如何針對尾遞回進行優化的。
然而，并不總是可以通過這樣一個簡單的技巧將函式轉換為尾遞回函式。我會將此類情況分類如下
- 函式仍然可以重寫為尾遞回，但這可能需要額外的資料結構和實作中的更多實質性更改
- 函式不能以任何方式重寫為尾遞回，但仍然可以通過使用回圈和模仿堆疊來避免遞回（我不是 100% 確定在某些情況下尾遞回是不可能的，我無法描述如何識別這種情況，所以如果有是否有關于這個主題的學術研究 - 非常感謝鏈接）
現在讓我考慮可以通過使用附加結構和改變演算法作業方式將函式重寫為尾遞回的具體示例。
示例任務：列印所有長度為 n 且包含 1 和 0 且沒有相鄰 1 的序列。
首先想到的明顯實作如下（在每一步，如果當前值為 0，那么我們生成兩個長度為 n-1 的序列，否則我們只生成長度為 n-1 的序列，從 0 開始）
def gen001(lvl: Int, result: List[Int]):Unit = {
//println("gen001")
if (lvl > 0) {
if (result.headOption.getOrElse(0) == 0) {
gen001(lvl - 1, 0 :: result)
gen001(lvl - 1, 1 :: result)
} else gen001(lvl - 1, 0 :: result)
} else {
println(result.mkString(""))
}
}
gen001(5, List())
當當前元素為 0 時，避免兩個函式呼叫并不是那么簡單，但是如果我們為中間序列中的每個值生成子級（從級別 1 的序列“01”開始），則可以做到這一點。 在級別具有輔助序列的層次結構之后1..n 我們可以printResult從葉節點（或者換句話說，從最后一次迭代開始的序列）重建結果 ( )。
@tailrec
def g001(lvl: Int, current: List[(Int, Int)], result: List[List[(Int, Int)]]):List[List[(Int, Int)]] = {
//println("g001")
if (lvl > 1) {
val tmp = current.map(_._1).zipWithIndex
val next = tmp.flatMap(x => x._1 match {case 0 => List((0, x._2), (1, x._2)) case 1 => List((0, x._2))})
g001(lvl - 1, next, next :: result)
} else result
}
def printResult(p: List[List[(Int, Int)]]) = {
p.head.zipWithIndex.foreach(x =>
println(p.scanLeft((-1, x._2))((r1, r2) => (r2(r1._2)._1, r2(r1._2)._2)).tail.map(_._1).mkString("")))
}
val r = g001(5, List(0,1).zipWithIndex, List(List(0,1).zipWithIndex))
println(r)
printResult(r)
輸出
List(List((0,0), (1,0), (0,1), (0,2), (1,2), (0,3), (1,3), (0,4), (0,5), (1,5), (0,6), (0,7), (1,7)), List((0,0), (1,0), (0,1), (0,2), (1,2), (0,3), (1,3), (0,4)), List((0,0), (1,0), (0,1), (0,2), (1,2)), List((0,0), (1,0), (0,1)), List((0,0), (1,1)))
00000
10000
01000
00100
10100
00010
10010
01010
00001
10001
01001
00101
10101
So now, if we compare two approaches, the first one requires much more recursive calls however on the other hand it's much more efficient in terms of memory because no additional data structures of intermediate results are required.
Finally, the questions are
- Is there a class of recursive functions which cannot be implemented as tail recursive? If so how to identify them?
- Is there a class of recursive functions such as their tail recursive implementation cannot be as efficient as non tail recursive one (for example in terms of memory usage). If so how to identify them. (Function from above example seems to be in this category)
Links to academical research papers are highly appreciated.
PS. Thera are a number of related questions already asked and below links may be quite useful
Rewrite linear recursive function as tail-recursive function
https://cs.stackexchange.com/questions/56867/why-are-loops-faster-than-recursion
uj5u.com熱心網友回復：
1 中的函式類是空的：任何以遞回風格撰寫的可計算函式都有一個尾遞回等價物（在極限情況下，由于存在圖靈機的尾遞回實作，您可以將任何可計算函式轉換為圖靈機定義，然后該函式的尾遞回版本通過圖靈機的尾遞回實作運行該定義）。
同樣，沒有尾遞回本質上比非尾遞回效率低的函式。例如，在您的示例中，“它在記憶體方面效率更高，因為不需要中間結果的額外資料結構”，這是不正確的。中間結果所需的附加結構隱含在呼叫堆疊中（在尾遞回版本中消失）。雖然呼叫堆疊可能是一個陣列（比鏈表更節省空間），但由于其通用性，它也存盤了比所需更多的資料。
uj5u.com熱心網友回復：
我想說一個不能用尾遞回實作的遞回函式的一個明顯例子是一個函式，其中最后一條陳述句呼叫了自己兩次。一個例子是一種常見的遞回演算法，用于尋找二叉樹的最大深度，其中最后一行看起來像max(max_depth(left), max_depth(right)).
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/333547.html
上一篇：為什么我的IntelSkylake/KabyLakeCPU在簡單的哈希表實作中會導致神秘的因子3減速？
下一篇：使用set文字更快地設定包含