递归与迭代在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＃

回答

相关问题