为什么应该使用迭代而不是尾递归？

Question

什么是设计异味？递归中的不良实践是什么？ 我曾经看到resharper建议改进，然后我迅速在谷歌上搜索。 看到很多评论都在建议将尾递归重构为迭代，并将其称之为设计异味。

public static void DebugOutput2(Exception ex) {
    if (ex == null) {
        return;
    }
    Debug.WriteLine(ex.Message);
    if (ex.InnerException != null) {
        DebugOutput2(ex.InnerException);
    }
}

// WAS REFACTORED TO

public static void DebugOutput(Exception ex) {
    if (ex == null) {
        return;
    }
    while (true) {
        Debug.WriteLine(ex.Message);
        if (ex.InnerException != null) {
            ex = ex.InnerException;
            continue;
        }
        break;
    }
}

编辑：根据C#编译器处理的评论，现在似乎是递归的
目标为.NET 4.5。C# 5.0

tail recursion版本的ILDASM输出：显示递归调用而不是迭代

.method public hidebysig static void  DebugOutput(class [mscorlib]System.Exception ex) cil managed
{
  // Code size       54 (0x36)
  .maxstack  2
  .locals init ([0] bool CS$4$0000)
  IL_0000:  nop
  IL_0001:  ldarg.0
  IL_0002:  ldnull
  IL_0003:  ceq
  IL_0005:  ldc.i4.0
  IL_0006:  ceq
  IL_0008:  stloc.0
  IL_0009:  ldloc.0
  IL_000a:  brtrue.s   IL_000e
  IL_000c:  br.s       IL_0035
  IL_000e:  ldarg.0
  IL_000f:  callvirt   instance string [mscorlib]System.Exception::get_Message()
  IL_0014:  call       void [System]System.Diagnostics.Debug::WriteLine(string)
  IL_0019:  nop
  IL_001a:  ldarg.0
  IL_001b:  callvirt   instance class [mscorlib]System.Exception [mscorlib]System.Exception::get_InnerException()
  IL_0020:  ldnull
  IL_0021:  ceq
  IL_0023:  stloc.0
  IL_0024:  ldloc.0
  IL_0025:  brtrue.s   IL_0035
  IL_0027:  nop
  IL_0028:  ldarg.0
  IL_0029:  callvirt   instance class [mscorlib]System.Exception [mscorlib]System.Exception::get_InnerException()
  IL_002e:  call       void ca1.Program::DebugOutput(class [mscorlib]System.Exception)
  IL_0033:  nop
  IL_0034:  nop
  IL_0035:  ret

} // end of method Program::DebugOutput

- phil soady

---

请注意，虽然CLR支持尾调用，但是C#编译器不会发出它们（据我上次检查）。无论如何，使用这种特定结构很难使堆栈溢出，并且性能并不是真正的问题，因为您已经在处理异常。 - Robert Harvey

我会选择使用类似于 while(ex != null) {Debug.WriteLine(ex.Message);ex = ex.InnerException} 的代码而不是这个 while 循环。 - Kevin

从性能的角度考虑使用尾递归会发生什么。我们需要创建一个堆栈帧，复制一些内容并调用函数。根据递归的深度，这可能会导致堆栈溢出（虽然在此示例中不太可能），而且肯定比非递归迭代的性能更差。 - rileyberton

我认为这里并不相关，但通常情况下，迭代优于递归，因为它的性能更好。ReSharper可能只是建议在可能的情况下使用迭代而不考虑实际的性能问题。 - evanmcdonnal

像这样的建议过于简单粗暴。有很多算法递归是自然解法，例如任何树遍历代码都更容易编写。但是，在32位.NET程序中它有缺陷，x86滞后器无法优化尾递归。如果递归深度没有受实际上限绑定或深度超过O(log n)，那么您的程序可能会因此崩溃。 - Hans Passant

尽管不仅限于TAIL递归，但这个讨论对于将来的参考是相关的。 - phil soady

Answer 1

因为人们错误地更关注微观优化而非清晰易懂的代码。

- ILMTitan

---

我更喜欢DRY的递归解决方案，它易于阅读和维护，而不是为了节省几个纳秒。请注意，Kevin提出了一种非常优雅的迭代方法。像往常一样，你可以写出好的和坏的递归。但是，将递归称为一种不好的味道似乎对我来说有些过分。特别是当SOLID设计原则适用时。因此，我支持这种做法。在接受答案之前我会等待看看会发生什么。谢谢！ - phil soady

在递归解决方案中，您还可以删除对InnerException的冗余null检查。 - ILMTitan

Answer 2

递归会进行额外的（递归）函数调用，这也意味着每个级别（每个处理的对象）都会进行堆栈分配。

通常情况下，迭代更好，因为它不会进行额外的调用/分配。

当然，如果有许多要处理的对象，差异将是明显的，但我想在你的示例中这不是问题。所以对于你来说，这不是一个问题，我猜意图是向你传授一般的最佳实践。

- stan0

---

我认为任何半靠谱的编译器都会优化尾递归调用。 - ScottishTapWater

我知道这已经被说过了，但是将调用变成尾递归的整个目的就是让编译器可以优化掉递归。 - 2-bits