CODEWITHSUNDEEP
c#clr
Martijn
Martijn

Reputation: 12091

Are simple tail recursive functions as efficient as loops?

Sometimes I find myself writing tail recursive functions. I have been searching high and low, and I have found there is tail recursion in the .NET framework, but I'm not sure in what cases I can, and in what cases I can't use tail recursion efficiently. For example, I have a simple tree, lets call it

public class Tree
{
  public Tree parent = null;

  public Tree(Tree parent)
  {
    this.parent = parent;
    this.children = new List<Tree>();
  }

  public List<Tree> children {get; private set;}

  public Tree root
  {
    get
    {
      return this.parent == null ? this : parent.root;
    }
  }
}

for the root property, will the compiler emit a loop? will it emit .tail? Will the jitter respect the .tail? will nothing fancy happen, and will the algorithm just run recursively? Most importantly, should I rewrite this to be iterative?

Upvotes: 20

Views: 1410

Answers (2)

ony
ony

Reputation: 13223

There is similar answer other answer.

Regarding speed. Tail recursion optimization isn't really different from loop for small functions. When tail call optimization fired it just replace "call" instruction (on x86) with "jmp". When doing the same through loop you'll have the same "jmp" instruction for entering next cycle. One moment you should remember is that the whole body of function will be the body of cycle and thus you should try to minimize size of recursive functions.

Upvotes: 1

leppie
leppie

Reputation: 117220

The C# compiler will never emit tail prefix.

F# will do so, if the call is in tail position. It depends on the order you traverse the tree whether tail recursion is applicable.

In your code, there is nothing in a tail position. The reason is the usage of a ternary operator. If the code is rewritten to use if statements with each branch returning, then the call to parent.root will be in tail position.

In terms of optimization, the compiler (F# or IronScheme) will normally convert tail recursive calls into while (true) { ... } loops. This is done as it removes both the tail call and the need to call the method again.

So if C# was allowed to emit tail calls (which it is not) it would likely be transformed from:

public Tree root
{
  get
  {
    if (parent == null) return this;
    else return parent.root; // now in tail position
  }
}

to (just a guestimate)

public Tree root
{
  get
  {
    Tree temp = this;
    while (true)
    {
      if (temp.parent == null)
      {
         return temp;
      }
      temp = temp.parent;
    }
  }
}

F# and IronScheme both does the same transformation. This is called tail call elimination (TCE). And yes, it will be marginally faster than the C# version. (I have tested this by microbenchmarking fib on C#, F# and IronScheme)

Upvotes: 9

Related Questions