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

Question

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?

You got it backwards, *tail recursion* won't generate stack overflows, but a non-tail recursive call can. — Lucas Trzesniewski, Jun 11 '16 at 22:04
In any case C# does not guarantee that even when tail-call optimization *can* be done, it actually *is* done. So it can create a stack overflow anyway (it will also actually happen, except sometimes on x64) — harold, Jun 11 '16 at 22:21
@LucasTrzesniewski, naive [tail recursion](https://en.wikipedia.org/wiki/Tail_call) *will* generate a stack overflow, unless an operator exists in the system (and is properly used) to optimize for that scenario. The CLR does have such an opcode (`tail`). C# does not have a vehicle for leveraging that opcode reliably. — Kirk Woll, Jun 11 '16 at 22:24
@KirkWoll AFAIK RyuJIT doesn't need the `tail` prefix and generates a loop nonetheless (see my answer), but there's no guarantee, as the x86 version shows. — Lucas Trzesniewski, Jun 11 '16 at 22:28
@Kirk, C# proper (i.e. us) may not have that vehicle, but *the compiler* has it, and can decide to use it depending on the context it's operating on. It's actually better and safer that way. — Frédéric Hamidi, Jun 11 '16 at 22:28
@KirkWoll See this answer: https://stackoverflow.com/a/29571052/2884172 Release/x64 or Release/AnyCPU does use tail recursion. x86 or Debug modes do not. — mwwaters, Jan 18 '18 at 19:23

score 4 · Accepted Answer · edited May 23 '17 at 12:08

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.

score 1 · Answer 2 · answered Jun 11 '16 at 22:10

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.

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

2 Answers2