遞歸與迭代在C＃

在最近的一次採訪中，我被問到一個問題，寫一個遞歸函數來反轉一個字符串，迭代版本是否比這個特定算法的遞歸函數更好。我不確定遞歸解決方案比迭代解決方案更糟糕/更好。任何人都可以幫我理解這個嗎？遞歸與迭代在C＃

是不是下面的代碼是一個尾遞歸的？

public static string Reverse(string str) 
{ 
    return (str.Length <= 1 ? str : str[str.Length - 1] 
      + Reverse(str.Substring(0, str.Length - 1))); 
}

來源

2012-01-11 blitzkriegz

請看看[this] [1]是否回答你的問題。 [1]：http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration – AksharRoop 2012-01-11 10:16:14

這不是尾遞歸。對於尾遞歸函數，最後調用的函數必須是函數本身。在這種情況下，所調用的最後一件事實際上是'+'操作。 – porges 2012-01-11 10:17:09

謝謝你指出這一點。 – blitzkriegz 2012-01-11 10:31:45

不能保證任何東西都會使用尾遞歸進行編譯（儘管x64.net似乎更傾向於這樣做）。如果字符串很長，則會用完堆棧。

來源

2012-01-11 10:16:19 spender

我知道我的例子不是尾遞歸，但是我們不能確切地知道尾遞歸函數是否被C＃編譯器轉換爲迭代函數？ – blitzkriegz 2012-01-11 10:30:27

@mkg：這不是C＃編譯器，它是JITer。並沒有保證，有[很多例外]（http://blogs.msdn.com/b/davbr/archive/2007/06/20/tail-call-jit-conditions.aspx）。雖然在技術上可以檢查它是否在您的機器上完成，但您不應該認爲這適用於所有其他機器。這意味着一個黑盒子的實現，而不是你應該以任何方式依賴的東西。 – 2012-01-11 10:40:03

檢查Optimize標誌並用調試器（ida，olly，whatever）查看代碼以查看編譯器對它做了什麼。它可能是肯定的，但我不會打賭，他將遞歸轉換爲迭代算法。

一般而言，您應該儘可能使用迭代算法，因爲它們不太可能導致內存不足/導致堆棧溢出等。如果它確實有助於理解代碼並且沒有機會發生堆棧溢出，那麼您可以使用遞歸

來源

2012-01-11 10:35:59

遞歸與迭代在C＃

回答

相關問題