这个尾递归是否会导致堆栈溢出？ C#.网

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

Resharper 只是没有检测到第二种形式。它不努力。程序分析通常是困难且不可能的（参见停机问题）。 Resharper 主要有一些不错且有用的启发式算法。

如果将 ReadLine 替换为 null，您会发现这里很可能发生堆栈溢出。

Answer 2

正如 usr 在中解释的那样，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

那里还有第二个 call，所以你不会得到尾递归，堆栈 会增长 ，如果它变大，最终会导致堆栈溢出够了。

嗯，看起来 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

看到了吗？你不能真的依赖它，语言也没有提供任何保证。

这个尾递归是否会导致堆栈溢出？ C#.网

Is this tail recursive and could it cause a stack overflow? C# .Net

.net

c#

stack-overflow

tail-recursion