Never rely on tail recursion elimination

Corollary: Never write a recursively method with an unbounded stack depth.

I previously posted a recursive implementation of Factorial, and asked the readers “not to bother saying it’s inefficient because of recursion, since it will probably be optimized away anyway”. Not true.

I don’t really understand why (just posted a question to StackOverflow), but C# does not generally perform tail recursion elimination (at least as my measly test show).

The following method can be easily optimized, both to work faster, consume less space and not to cause a StackOverflowException … but it is not optimized by the compiler (verified by Reflector and the fact a StackOverflowException was indeed thrown).

private static void Foo(int i)
{
    if (i == 1000000)
        return;
 
    if (i % 100 == 0)
        Console.WriteLine(i);
 
    Foo(i+1);
}

So … if for some reason you prefer writing recursive methods over using loops, do it only where performance is not a consideration and you have a good understanding of the maximal stack depth.

8 Comments

  1. Tomer Gabel:

    Inconclusive: try NGen’ing the compiled assembly and check the generated native code. CSC performs almost no optimizations; nearly everything is done in the JIT.

  2. ripper234:

    I’ve read somewhere that NGen doesn’t help. Will verify. The JIT obviously didn’t optimize it away because it did throw a StackOverflowException.

  3. ripper234:

    NGen does’t help.

    .method private hidebysig static void Foo(int32 i) cil managed
    {
        .maxstack 8
        L_0000: ldarg.0 
        L_0001: ldc.i4 0xf4240
        L_0006: bne.un.s L_0009
        L_0008: ret 
        L_0009: ldarg.0 
        L_000a: ldc.i4.s 100
        L_000c: rem 
        L_000d: brtrue.s L_0015
        L_000f: ldarg.0 
        L_0010: call void [mscorlib]System.Console::WriteLine(int32)
        L_0015: ldarg.0 
        L_0016: ldc.i4.1 
        L_0017: add 
        L_0018: call void StackOverflow.Program::Foo(int32)
        L_001d: ret 
    }
    
  4. Tomer Gabel:

    That’s not an ngen image – I’m talking native code, here. Try C:\Windows\assembly\NativeImages_v2.0.50727_32, I think that’s where ngen’d assemblies go.

  5. ripper234:

    I went to said location, viewed it with reflector, and this is what it shows.
    I don’t really have the will to open IDA now, but running the example proves my point.

  6. Tomer Gabel:

    Can I assume you’ve compiled for RELEASE?

  7. ripper234:

    Yes you can.

  8. Tomer Gabel:

    In that case, I’m (badly) surprised. I’ll try to do some more research on the subject.