Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why should iteration be used instead of tail recursion?

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
like image 748
phil soady Avatar asked Aug 22 '13 23:08

phil soady


People also ask

Why is iteration faster than recursion?

The simplicity of recursion comes at the cost of time and space efficiency. It is much slower than iteration due to the overhead of function calls and control shift from one function to another. It requires extra memory on the stack for each recursive call.

Why should we try to eliminate tail recursion?

Tail call elimination reduces the space complexity of recursion from O(N) to O(1). As function call is eliminated, no new stack frames are created and the function is executed in constant memory space.

Why is recursion better than tail recursion?

The tail recursion is better than non-tail recursion. As there is no task left after the recursive call, it will be easier for the compiler to optimize the code. When one function is called, its address is stored inside the stack. So if it is tail recursion, then storing addresses into stack is not needed.


2 Answers

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

like image 187
ILMTitan Avatar answered Nov 02 '22 05:11

ILMTitan


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.

like image 31
stan0 Avatar answered Nov 02 '22 05:11

stan0