Why should iteration be used instead of tail recursion?

Question

What is the design smell, poor practice in recursion ? once I saw resharper suggesting improvements I quickly looked around on google. Saw numerous comments around re-factoring tail recursion to iterations and referring to it as a design smell.

public static void DebugOutput2(Exception ex) {
    if (ex == null) {
        return;
    }
    Debug.WriteLine(ex.Message);
    if (ex.InnerException != null) {
        DebugOutput2(ex.InnerException);
    }
}

// WAS REFACTORED TO

public static void DebugOutput(Exception ex) {
    if (ex == null) {
        return;
    }
    while (true) {
        Debug.WriteLine(ex.Message);
        if (ex.InnerException != null) {
            ex = ex.InnerException;
            continue;
        }
        break;
    }
}

EDIT: BAsed on C# compiler treatment comment. Looks like it is recursive now
Target .net 4.5 . C# 5.0

ILDASM Output for tail recursion version: Shows recursive call and not iteration

.method public hidebysig static void  DebugOutput(class [mscorlib]System.Exception ex) cil managed
{
  // Code size       54 (0x36)
  .maxstack  2
  .locals init ([0] bool CS$4$0000)
  IL_0000:  nop
  IL_0001:  ldarg.0
  IL_0002:  ldnull
  IL_0003:  ceq
  IL_0005:  ldc.i4.0
  IL_0006:  ceq
  IL_0008:  stloc.0
  IL_0009:  ldloc.0
  IL_000a:  brtrue.s   IL_000e
  IL_000c:  br.s       IL_0035
  IL_000e:  ldarg.0
  IL_000f:  callvirt   instance string [mscorlib]System.Exception::get_Message()
  IL_0014:  call       void [System]System.Diagnostics.Debug::WriteLine(string)
  IL_0019:  nop
  IL_001a:  ldarg.0
  IL_001b:  callvirt   instance class [mscorlib]System.Exception [mscorlib]System.Exception::get_InnerException()
  IL_0020:  ldnull
  IL_0021:  ceq
  IL_0023:  stloc.0
  IL_0024:  ldloc.0
  IL_0025:  brtrue.s   IL_0035
  IL_0027:  nop
  IL_0028:  ldarg.0
  IL_0029:  callvirt   instance class [mscorlib]System.Exception [mscorlib]System.Exception::get_InnerException()
  IL_002e:  call       void ca1.Program::DebugOutput(class [mscorlib]System.Exception)
  IL_0033:  nop
  IL_0034:  nop
  IL_0035:  ret

} // end of method Program::DebugOutput

Note that, while the CLR supports tail calls, [the C# compiler doesn't emit them](http://www.thomaslevesque.com/2011/09/02/tail-recursion-in-c/) (last time I checked). In any case, it's unlikely that you'll blow the stack with this particular construct, and performance is not really a problem since you're already dealing with exceptions anyway. — Robert Harvey, Aug 22 '13 at 23:47
I would reject that `while` loop in favor of something closer to `while(ex != null) {Debug.WriteLine(ex.Message);ex = ex.InnerException}`. — Kevin, Aug 22 '13 at 23:47
Consider what happens using tail recursion from a performance perspective. We need to create a stack frame, copy some things in and call then call the function. Depending on the recursion this can lead to a blown stack (although not in this example, likely) and certainly worse performance that non-recursive iteration — rileyberton, Aug 22 '13 at 23:54
I don't think it's relevant here but in general iteration is preferred over recursion because it performs much better. ReSharper likely just suggests using iteration over recursion where ever possible without considering if there are actually performance concerns. — evanmcdonnal, Aug 22 '13 at 23:55
A recommendation like this is far too crude. There are plenty of algorithms where recursion is the natural solution, any tree walking code is much easier to write with it for example. But yes, it has cooties in a 32-bit .NET program, the x86 jitter doesn't optimize a tail call away. If the recursion depth isn't bounded by a practical upper limit or the depth is more than O(log n) then your program is liable to byte the dust with this website's name. — Hans Passant, Aug 27 '13 at 10:19
although not limited to TAIL recursion, this discussion is relevant http://stackoverflow.com/q/478570/1347784 for future reference — phil soady, Aug 27 '13 at 15:59

score 23 · Accepted Answer · answered Aug 23 '13 at 00:51

23

Because people mistakenly care more about micro-optimizations than clear and readable code.

answered Aug 23 '13 at 00:51

ILMTitan

10,751
3
30
46

3

i do prefer DRY recursive solution that is easy to read and maintain than the saving a few nanoseconds. Mind you a very elegant iteration was highlighted by kevin. As always you can write good and bad recursions. But calling recursion a bad smell seems over the top to me. Especially when SOLID design outcomes apply. So +1 now. will wait to see what happens before accepting as answer. Thanks ILMTitan – phil soady Aug 23 '13 at 01:13
You could also remove the redundant null check on InnerException in the recursive solution. – ILMTitan Aug 23 '13 at 01:16

score 9 · Answer 2 · answered Aug 27 '13 at 10:10

9

The recursion makes additional (recursive) function call, which also means a stack allocation, for every level (every object you handle).

Generally the iteration is better because it doesn't make that additional call/allocation.

Of course, the difference would be visible in case there are many objects to handle, which I suppose is not the case in your example. So for you it's not an issue and I guess the intention is to teach you a better practice in general.

answered Aug 27 '13 at 10:10

stan0

11,549
6
42
59

1

I'd have thought any half-decent compiler will optimise away tail recursive calls – ScottishTapWater Mar 26 '19 at 13:22
I know it was already said, but yeah the whole point of making a call tail recursive is so the recursion can be optimized away by the compiler. – 2-bits Sep 23 '19 at 15:50

Why should iteration be used instead of tail recursion?

2 Answers2

Linked

Related