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

Question

我有兴趣学习以下递归方法如何处理它的return语句.使用调试器,似乎方法参数被推送到堆栈.然后在返回时评估等式.在下面的调用树中,如何生成值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#编译器现在做的事情,但也不是不可能),这意味着没有真正传递参数- 你一遍又一遍地重复使用相同的数据位置,类似于重写递归以使用命令式循环.

调试器尽力使代码易于调试.这也使它与在调试器外部运行的代码不同.例如,调试器中本地的生命周期将扩展到整个块范围,而在调试器之外,一旦您最后一次访问它们,它们就不再保证存在.代码也会重新排序,以保持相同的单线程操作,同时提高性能.

如果要查看实际执行的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保留在堆栈上.通过尾调用优化递归,即使这样也可以避免.