c# - 优先顺序如何影响递归方法？

Question

我有兴趣了解以下递归方法如何处理它的返回语句。使用调试器，方法参数似乎被推送到堆栈。然后在返回时计算方程。在下面的调用树中，值 1、2、6 和 24 是如何生成的？

factorial(5) 
   factorial(4) 
      factorial(3) 
         factorial(2) 
            factorial(1) 
               return 1 
            return 2*1 = 2 
         return 3*2 = 6 
      return 4*6 = 24 
   return 5*24 = 120

  private static int factorial(int x)
    {
        if (x == 1)
            return 1;
        return x * factorial(x - 1);
    }

Answer 1

就 C# 而言，就好像您调用了任何其他方法一样。 C# 中没有针对递归的优化。

操作顺序是在 C# 中定义的，因此您始终知道什么时候计算。然而，在这种情况下，这并不重要——您只是调用一个带参数的函数并返回相乘的值。不涉及魔法。

不要太在意所发生事情的内部细节。大多数时候参数并没有真正通过堆栈传递，尤其是在 64 位上。也有可能执行尾调用优化(不是 C# 编译器现在做的事情，但也不是不可能)，这意味着没有传递参数真的 - 你为数据重用相同的数据位置一遍又一遍，类似于重写递归以改用命令式循环。

调试器尽最大努力使代码易于调试。这也使其与在调试器外部运行的代码不同。例如，局部变量在调试器中的生命周期将扩展到它们的整个 block 范围，而在调试器之外，一旦您最后一次访问它们，它们就不再保证存在。代码也被重新排序以保留相同的单线程操作，同时提高性能。

如果您想查看实际执行的 x86 代码，您可以在调试器外部运行应用程序，并使用 Debugger.Launch/Debugger.Break 调用它 -这将允许您绕过调试器的简化。

在我的特殊情况下，相关代码如下所示:

000007FE956204D0  push        rsi  
000007FE956204D1  sub         rsp,20h  
000007FE956204D5  mov         esi,ecx  ; store x
000007FE956204EA  lea         ecx,[rsi-1]  ; pass x - 1 ...
000007FE956204ED  call        000007FE95620080  ; ... to factorial
000007FE956204F2  imul        eax,esi  ; multiply the return value with stored x
000007FE956204F5  add         rsp,20h  
000007FE956204F9  pop         rsi  
000007FE956204FA  ret  

如您所见，堆栈没有传递任何内容。相反，rsi/esi 的旧值保留在堆栈中。使用尾调用优化递归，甚至可以避免这种情况。