尾遞歸vs頭經典遞歸

Question

聽Scala課程和解釋我經常聽到：「但在真正的代碼中，我們沒有使用遞歸，而是使用尾遞歸」。

這是否意味着，在我真正的代碼，我不應該使用遞歸，但尾遞歸是非常喜歡循環和不需要「爲了瞭解遞歸，你首先需要了解遞歸」那場史詩般的短語。

在現實中，考慮到你的堆棧..你更可能會使用循環式的尾遞歸。

我錯了嗎？這種「經典」遞歸是否僅適用於教育目的，使您的大腦回到大學 - 過去？

或者，對於所有這些，我們可以使用它的位置..遞歸調用的深度小於X（其中X是您的堆棧溢出限制）。或者我們可以從經典遞歸開始編碼，然後，害怕你的堆棧有一天會被吹，使用幾個重構使其成爲尾巴，以便在重構領域使用更強大的功能？

問：，你會使用/一些實際樣品已經於您真正代碼，這是不重構尚未進入尾一個，也許用「經典頭」遞歸？

Answer 1

尾遞歸==循環

您可以採取任何循環，它表示爲尾遞歸調用。

背景：在純FP中，一切都必須產生一定的價值。在scala循環中不會產生任何表達式，只會產生副作用（例如更新某些變量）。它只是爲了支持來自必要背景的程序員而存在。 Scala鼓勵開發人員重新考慮用遞歸來替代while循環，這總會產生一些價值。

所以根據斯卡拉：遞歸是新的迭代。

但是，前面的語句存在一個問題：雖然「Regular」遞歸代碼更容易閱讀，但它帶有性能損失並帶有堆棧溢出的固有風險。另一方面，尾遞歸代碼將永遠不會導致堆棧溢出（至少在Scala *中），並且性能將與循環相同（實際上，我確信Scala會將所有尾遞歸調用轉換爲純舊迭代）。

回過頭來看看這個問題，沒有錯，堅持「常規」遞歸，除非：

1. 您使用在計算大數（堆棧溢出）算法
2. 尾遞歸帶來了顯着性能提升

Answer 2

開發軟件時首先要看的是代碼的可讀性和可維護性。查看性能特徵大多是不成熟的優化。

沒有理由不使用遞歸來幫助編寫高質量的代碼。

尾部遞歸與正常循環相同。看看這個簡單的尾遞歸函數：

def gcd(a: Int, b: Int) = { 
    def loop(a: Int, b: Int): Int = 
    if (b == 0) a else loop(b, a%b) 
    loop(math.abs(a), math.abs(b)) 
} 

它計算兩個數字的最大公約數。一旦你知道這個算法，它很清楚它是如何工作的 - 用while循環寫這個並不會讓它更清晰。相反，您可能會在第一次嘗試時引入錯誤，因爲您忘記將新值存儲到變量a或b之一。

在另一邊看到這兩個函數：

def goRec(i: Int): Unit = { 
    if (i < 5) { 
    println(i) 
    goRec(i+1) 
    } 
} 

def goLoop(i: Int): Unit = { 
    var j = i 
    while (j < 5) { 
    println(j) 
    j += 1 
    } 
} 

哪一個更容易閱讀？它們大致相同 - 由於基於Scalas表達式的性質，您獲得的用於尾遞歸函數的所有語法都消失了。

對於遞歸函數還有另外一件事情要做：懶惰評估。如果您的代碼是懶惰評估它可以遞歸，但不會發生堆棧溢出。看到這個簡單的功能：

def map(f: Int => Int, xs: Stream[Int]): Stream[Int] = f -> xs match { 
    case (_, Stream.Empty) => Stream.Empty 
    case (f, x #:: xs)  => f(x) #:: map(f, xs) 
} 

它會崩潰的大輸入？我不這麼認爲：

scala> map(_+1, Stream.from(0).takeWhile(_<=1000000)).last 
res6: Int = 1000001 

試圖與Scalas List同樣會殺了你的程序。但因爲Stream是懶惰這不是一個問題。在這種情況下，你也可以編寫一個尾遞歸函數，但通常這是不容易的。

有許多算法在迭代編寫時不會清晰 - 一個示例是圖的depth first search。你是否想自己維護一個堆棧來保存你需要返回的值？不，你不會，因爲它容易出錯並且看起來很醜陋（除了遞歸定義之外 - 它也會調用迭代深度優先搜索遞歸，因爲它必須使用堆棧，而「正常」遞歸必須使用堆棧而且它只是隱藏在開發者面前並由編譯器維護）。

---

回來過早優化的點，我聽到一個很好的比喻：當你不能用Int要解決的問題，因爲你的號碼將獲得大，很可能是你溢出則不會切換到Long，因爲它很可能也會在這裏發生溢出。

對於遞歸，這意味着可能會出現堆棧炸燬的情況，但更有可能是當您切換到基於內存的解決方案時，您將會遇到內存不足錯誤。更好的建議是找到一個不能很好地執行的算法。

---

作爲結論，嘗試優先選擇尾遞歸而不是循環或正常遞歸，因爲它肯定不會殺死你的棧。但是當你能做得更好時，不要猶豫，做得更好。

Answer 3

如果你不處理線性序列，那麼試圖編寫一個尾遞歸函數來遍歷整個集合是非常困難的。在這種情況下，爲了可讀性/可維護性，您通常只使用正常遞歸。

一個常見的例子是遍歷一個二叉樹數據結構。對於您可能需要在左側和右側子節點上重複出現的每個節點。如果要試圖遞歸地編寫這樣一個函數，首先訪問左側節點，然後右側，則需要維護某種輔助數據結構以跟蹤所有需要訪問的剩餘右側節點。但是，使用堆棧可以達到同樣的效果，並且可讀性更高。

這方面的一個例子是iterator method from Scala's RedBlack tree：

def iterator: Iterator[(A, B)] = 
    left.iterator ++ Iterator.single(Pair(key, value)) ++ right.iterator 

Answer 4

有兩種基本類型的遞歸：

1. 頭遞歸
2. 尾遞歸

在頭遞歸，一個函數使其重新草書調用，然後執行一些更多的計算，例如可能使用遞歸調用的結果。在一個尾遞歸函數中，所有的計算都是首先發生，而遞歸調用是發生的最後一件事。

這種區別的重要性並不會跳出你，但它是非常重要的！想象一下尾遞歸函數。它運行。它完成了所有的計算。作爲其最後一項行動，它已準備好進行遞歸調用。在這一點上，什麼是堆棧框架的使用？一個都沒有。我們不再需要我們的局部變量，因爲我們完成了所有的計算。我們不需要知道我們所在的功能，因爲我們只是要重新輸入相同的功能。 在尾遞歸的情況下，Scala可以消除創建一個新的堆棧幀並重新使用當前堆棧幀。不管進行多少次遞歸調用，堆棧都不會變得更深。這是使Scala中的尾部遞歸特別的巫術。

讓我們來看看這個例子。

def factorial1(n:Int):Int = 
    if (n == 0) 1 else n * factorial1(n -1) 


def factorial2(n:Int):Int = { 
     def loop(acc:Int,n:Int):Int = 
      if (n == 0) 1 else loop(acc * n,n -1) 

    loop(1,n) 
    } 

順便提一句，某些語言通過將尾遞歸轉換爲迭代而不是通過操作堆棧來實現類似的結果。

這不適用於頭部遞歸。你明白爲什麼？設想一下頭遞歸函數。首先它做了一些工作，然後它進行遞歸調用，然後再做一些工作。當我們進行遞歸調用時，我們不能只重新使用當前的堆棧幀。在遞歸調用完成後，我們需要堆棧幀信息。它有我們的局部變量，包括遞歸調用返回的結果（如果有的話）。

這是一個問題給你。示例函數factorial1頭遞歸還是尾遞歸？那麼，它有什麼作用？ （A）它檢查它的參數是否爲0.（B）如果是，則返回1，因爲0的階乘爲1.（C）如果不是，則返回n乘以遞歸調用的結果。遞歸調用是我們在結束函數前鍵入的最後一件事。這是尾遞歸，對吧？ 錯了。進行遞歸調用，然後THEN乘以結果，並返回此產品。這實際上是頭遞歸（或中間遞歸，如果你喜歡），因爲遞歸調用並不是發生的最後一件事。

For more info please refer the link