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?

Berserk

The exact complaint from VS2008 is: Local Variable 'build' may not be initialized before accessing. – Berserk

Answer 1

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;
        };

Flyer

True ;) But the resulting function is not anonymous - in your approach, the recursion trick still is just possible through a name binding. – Hochstetler

Answer 2

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).

Emeritaemeritus

This/self is still anonymous enough. – Quinby

Recursive function is somehow easier to read than named delegate above. Also delegate itself needs to be defined, which is also minus for that solution and plus for this one. – Indraft

Answer 3

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).

Vanzandt

Y-combinator for the win! :-) – Consonantal

I might have misread - but is your example factorial instead of exp? I am pretty bad at maths so I am not entirely sure, would be nice if you can clarify – Kindle

Answer 4

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.

Narrate

+1 for the good description of why the error exists. It's easy to workaround (see Mehrdad's answer), but I don't think its a good idea in the first place. – Emeritaemeritus

Answer 5

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);
  }
}

Tympanum

Answer 6

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.

Thibault