c# - 这个尾部递归是否会导致堆栈溢出？ C# .Net

Question

我想知道为什么我得到 VS/Resharper 的第一种方式注意到尾递归可以用循环替换，而且我确实设法得到类似的东西导致堆栈溢出，所以我阅读了尾递归如何工作原理以及它如何增长堆栈等。

第一个生成尾递归注释。

    private static string GetLine()
    {
        string s = Console.ReadLine();

        if (s == null)
        {
            return GetLine();
        }
        return s;
    }

但是这样做不会:

    private static string GetLine()
    {
        string s = Console.ReadLine();

        if (s == null)
        {
            s = GetLine();
        }
        return s;
    }

所以我的问题是；第二个是否不被视为尾递归，即它不能创建堆栈溢出，因为它不生成所有堆栈调用？

Answer 1

正如 usr 在 his answer 中所解释的那样，ReSharper 尝试在代码中查找可以提供重构的已知模式。

但是让我们看一下这两种情况生成的代码。

---

第一个函数:

private static string GetLineA()
{
    string s = Console.ReadLine();

    if (s == null)
    {
        return GetLineA();
    }
    return s;
}

给出这个(x64，版本):

00007FFB34AC43EE  add         byte ptr [rax],al  
00007FFB34AC43F0  sub         rsp,28h  
00007FFB34AC43F4  call        00007FFB8E56F530  // <-- Console.ReadLine
00007FFB34AC43F9  test        rax,rax  
00007FFB34AC43FC  jne         00007FFB34AC440F  
00007FFB34AC43FE  mov         rax,7FFB34AC0F60h  
00007FFB34AC4408  add         rsp,28h  
00007FFB34AC440C  jmp         rax  
00007FFB34AC440F  add         rsp,28h  
00007FFB34AC4413  ret  

您可以清楚地看到它的尾递归，因为唯一的call指令是针对Console.ReadLine的。

---

第二个版本:

private static string GetLineB()
{
    string s = Console.ReadLine();

    if (s == null)
    {
        s = GetLineB();
    }
    return s;
}

给出这个:

00007FFB34AC44CE  add         byte ptr [rax],al  
00007FFB34AC44D0  sub         rsp,28h  
00007FFB34AC44D4  call        00007FFB8E56F530  // <-- Console.ReadLine
00007FFB34AC44D9  test        rax,rax  
00007FFB34AC44DC  jne         00007FFB34AC44E3  
00007FFB34AC44DE  call        00007FFB34AC0F68 // <-- Not good.
00007FFB34AC44E3  nop  
00007FFB34AC44E4  add         rsp,28h  
00007FFB34AC44E8  ret  

那里有第二个调用，所以你不会得到尾递归，并且堆栈将会增长，如果它增长得足够大，最终会导致堆栈溢出。

嗯，看来 JIT 没有将代码优化为尾递归调用。

---

无论如何，要小心，因为你受到 JIT 的支配。

这是 x86 中的 GetLineA:

00F32DCA  in          al,dx  
00F32DCB  call        72A209DC  // <-- Console.ReadLine
00F32DD0  test        eax,eax  
00F32DD2  jne         00F32DDC  
00F32DD4  call        dword ptr ds:[12B8E94h]  // <-- Ouch
00F32DDA  pop         ebp  
00F32DDB  ret  
00F32DDC  pop         ebp  
00F32DDD  ret  

看到了吗？您不能真正依赖它，并且该语言不提供任何保证。