CODEWITHSUNDEEP
c#.netstack-overflowtail-recursion
lozzajp
lozzajp

Reputation: 1006

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

I am wondering why the first way I get a VS/Resharper note that the tail recursion could be replaced with a loop, and I did indeed manage to get something similar to cause a stack overflow so I read up on how tail recursions work and how it grows the stack etc.

This first one generates the tail recursion note. 

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

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

But doing it like this does not:

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

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

So my question is; is the second one not considered tail recursive, ie it cannot create a stack overflow because it does not generate all the stack calls?

Upvotes: 2

Views: 467

Answers (2)

Lucas Trzesniewski
Lucas Trzesniewski

Reputation: 51330

As usr explains in his answer, ReSharper tries to find known patterns in your code it can offer refactorings for.

But let's take a look at the generated code for both cases.

The first function:

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

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

Gives this (x64, Release):

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

You can clearly see it's tail recursive, since the only call instruction is for Console.ReadLine.

The second version:

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

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

Gives this:

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

There's a second call there, so you don't get tail recursion, and the stack will grow, eventaully leading to a stack overflow if it grows large enough.

Well, it looks like the JIT didn't optimize the code into a tail recursive call.

Anyway, beware, since you're at the mercy of the JIT.

Here's GetLineA in x86:

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

See? You can't really depend on it, and the language provides no guarantee.

Upvotes: 4

usr
usr

Reputation: 171178

Resharper just does not detect the second form. It doesn't try hard. Program analysis is hard and impossible in general (see the halting problem). Resharper mostly has a few nice and helpful heuristics.

If you replace ReadLine with null you'll see that a stack overflow is very possible here.

Upvotes: 1

Related Questions