無法在while循環中實現的遞歸示例

是否存在遞歸是必要的情況，或者甚至強烈希望在JavaScript或C＃中使用while循環（不重要，使用情況似乎相同）。無法在while循環中實現的遞歸示例

有上MSDN階乘例子（I除去不相干的東西）：

function factorial(num) 
{ 
    var tmp = num; 
    while (num-- > 2) { 
     tmp *= num; 
    } 
    return tmp; 
}

function factorial(num) 
{ 
    return (num * factorial(num - 1)); 
}

總之，是那裏的第二個例子是preferrable到第一任何情況性能明智。它能夠完成第一個例子不能做到的事情嗎？如果是這樣，什麼？

來源

2016-08-17 VSO

舉例來說，你有一棵樹有多個分支，不只是樹幹和第一個分支。所以你必須在遞歸派上用場的地方越陷越深。 –

另外，遞歸算法（或實現）並非固有地大於那些迭代慢。實際上，每個遞歸算法可以是，通過等價的迭代實現來實現，代價爲必須自己跟蹤一些中間/臨時值，其中遞歸版本自動跟蹤函數調用堆棧中的那些中間/臨時值。 - Is recursive code slower than non-recursive code

簡而言之，有一種方法可以迭代編寫代替遞歸方法。然後出現諸如java或python之類的開銷問題，而C中存在的快捷方式則是開銷遞歸最終成爲方法中的跳躍。

在Javascript中，遞歸在ES2015之前不是尾端的，因此從長遠來看，遞歸會變得極其成本不足。從Performance: recursion vs. iteration in Javascript採取，但是在這之後，Javascript有TER/TCO，所以投資遞歸的成本更低。在我看來，這是JS在兩者之間個人偏好的混亂。如果您可以使代碼的遞歸功能和外觀變得乾淨而快速，那麼它的性能將大致與迭代版本相當，後續版本可能會變得非常令人討厭，甚至可以進行調試。

在C＃中，遞歸往往比以可讀性爲代價的迭代解決方案慢。然而，它又歸結爲個人偏好。隨着C＃在每個「循環/步驟」上創建開銷和新的堆棧框架，它通常不會像表現一樣。在其他語言中，遞歸與迭代解決方案一樣強大。

對於許多語言中，這是不是這樣的，和遞歸同樣或比迭代版本

查看更多高性能：Recursion preferred?對於爲什麼最好是在某些語言中一些額外的Q/A這不是Java，C＃，開銷不足的語言。

來源

2016-08-17 14:48:32 Adam

如果您可以使用recursion解決任務，則可以使用loops解決，反之亦然。在遞歸中，您的方法的作用域會一次又一次地創建相同的作用域。因此，如果您的方法的大小爲1KB，那麼在10步驟中，您的邏輯將花費10KB空間。在循環中，已用空間將僅爲1KB。

有些任務可以通過遞歸輕鬆解決，但是對於循環來說很難。其中之一是在Hanoi towers

來源

2016-08-17 14:40:57

欣賞榜樣！ – VSO

我完全同意以前的答案：遞歸往往很方便，重點。將問題簡化爲完成檢查是非常好的，如果不完成，還需要一個簡單的處理步驟。讓操作系統處理你的簿記。

我添加註意，有一些函數不是原始的遞歸;最知名的（並且首次發現的）是Ackermann function。實際上，你可能實現它與循環和你自己的堆棧，但你真的，真的不會想。

在更實際的情況下，您不太可能需要實現原始遞歸的函數，即而不是。阿克曼功能具有很大的理論價值，但它並不是我們日常生活中所遇到的東西，即使在深度學習或高性能計算中也是如此。

來源

2016-08-17 18:07:47 Prune

在你的問題中的關鍵點是功能堆棧。 return (num * factorial(num - 1));不在尾部位置，即遞歸調用factorial(num - 1)不是遞歸函數的最後一個動作。最後一個動作是乘以num。所以你的factorial需要堆棧工作。當您使用尾遞歸版本factorial(acc * num, num - 1)消除堆棧時，您需要使用附加參數來模仿堆棧，即acc。

由於缺少堆棧，循環本身不像遞歸那樣富有表現力。這意味着你不能實現等價於你的非尾遞歸實現的循環版本。其實你的while實現相當於factorial的尾遞歸版本。尾遞歸意味着所有的遞歸調用共享一個棧幀，從而被淘汰 - 不再有堆棧。您的tmp只是acc - 它模仿函數堆棧並累計迭代的結果。嘗試使用while循環實現factorial，但沒有其他變量，如tmp。是不可能的。

但是，非尾遞歸解決方案的問題是它們可能炸燬堆棧，而tmp只存儲在堆上。

下面是完整的尾遞歸溶液：

function fact(acc, num) { 
 
    return num > 1 
 
    ? fact(acc * num, num - 1) // tail recursive case 
 
    : acc; // base case 
 
} 
 

 
console.log(fact(1, 5));

結論：

是否有情況下，當遞歸是必要的，或甚至強烈優選一會兒循環

編號尾遞歸和簡單循環是等價的。非尾遞歸和使用它們自己的堆棧的循環幾乎是等價的，只是非尾遞歸函數將其中間結果存儲在函數堆棧中，因此可能發生堆棧溢出。使用自己的堆棧循環將其存儲在堆中，因此不具有此限制。

來源

2016-08-18 05:29:34 ftor

無法在while循環中實現的遞歸示例

回答

相關問題