Can an anonymous method in C# call itself?

Question

I have the following code:

class myClass
{
private delegate string myDelegate(Object bj);

protected void method()
   {
   myDelegate build = delegate(Object bj)
                {
                    var letters= string.Empty;
                    if (someCondition)
                        return build(some_obj); //This line seems to choke the compiler
                    else string.Empty;

                };
   ......
   }
}

Is there another way to set up an anonymous method in C# such that it can call itself?

Answer 1

If you're creating a recursive function, I'd recommend avoiding anonymous delegates. Just create a method and have it call itself recursively.

Anonymous methods are meant to be anonymous - you shouldn't be calling them by name (non-anonymously).

Answer 2

You cannot call build inside build itself since the body of the anonymous method is the initialization of the variable itself. You are trying to use a variable before it is defined.

Not that I recommend this (as it would be much simpler to create a real method here that is recursive) but if you are interested you can read Anonymous Recursion in C#:

Recursion is beautiful and lambdas are the ultimate abstraction. But how can they be used together? Lambdas are anonymous functions and recursion requires names.

Answer 3

You can break it down into two statements and use the magic of captured variables to achieve the recursion effect:

myDelegate build = null;
build = delegate(Object bj)
        {
           var letters= string.Empty;
           if (someCondition)
               return build(some_obj);                            
           else string.Empty;
        };

Answer 4

If you're getting to the point of recursive anonymous methods, you may want to promote it to be a normal, private method in your class.

Answer 5

Anonymous Recursion in C# has a terrific discussion on this topic.

Recursion is beautiful and lambdas are the ultimate abstraction. But how can they be used together? Lambdas are anonymous functions and recursion requires names...

Since this popped up again, here's an example of using the Y-combinator:

// This is the combinator
public static Func<A,R> Y<A,R>( Func<Func<A,R>, Func<A,R>> f )
{
    Func<A,R> g = null;
    g = f( a => g(a) );
    return g;
}

Here's a usage of it to call an anonymous, recursive function ...

Func<int,int> exp = Y<int,int>( e => x => ( x <=1 ) ? 1 : x * e( x - 1 ) );
Console.WriteLine( exp(5) );

You will note that if you do not use the Y-combinator and set up the recursion with just the delegate, you do not get correct recursion. For example ...

// This is BAD. Do not do this!
Func<int,int> badRec = null;
badRec = x => ( x <= 1 ) ? 1 : x * badRec( x - 1 );

But everything works fine ...

Console.WriteLine( badRec(5) );

// Output
// 120

But try this ...

Func<int,int> badRec = null;
badRec = x => ( x <= 1 ) ? 1 : x * badRec( x - 1 );

Func<int,int> badRecCopy = badRec;

badRec = x => x + 1;

Console.WriteLine( badRec(4) );
Console.WriteLine( badRecCopy(5) );

// Output
// 5
// 25

What?!?

You see, after the line badRec = x => x + 1;, the delegate you actually have is this ...

badRecCopy = x => ( x <= 1 ) ? 1 : x * ( (x+1)-1 );

So, badRec is incrementing the value by 1 which we expect (4+1=5), but badRecCopy is now actually returning the square of the value (5*( (5+1)-1 ) which we almost certainly did not expect.

If you use the Y-combinator, it will work as expected ...

Func<int,int> goodRec = Y<int,int>( exp => x => ( x <=1 ) ? 1 : x * exp( x - 1 ) );
Func<int,int> goodRecCopy = goodRec;

And you get what you expect.

goodRec = x => x + 1;

Console.WriteLine( goodRec(4) );
Console.WriteLine( goodRecCopy(5) );

// Output
// 5
// 120

You can read more about the Y-combinator (PDF Link).

Answer 6

If you use Y, your function becomes a parameter to the function itself, so that you can call it recursively:

class myClass {
  private delegate string myDelegate(Object bj);
  protected void method() {
    myDelegate build = delegate(Object obj) {
      // f is the function itself, which is passed into the function
      return Functional.Y<Object, string>(f => bj => { 
        var letters = string.Empty;
        if (someCondition)
          return f(some_obj); // use f
        else return string.Empty;

      })(obj);
    };
  }
}

public static class Functional {
  public delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);
  public static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f) {
    Recursive<A, R> rec = r => a => f(r(r))(a);
    return rec(rec);
  }
}