12/01/2008
Recursive Linq Functions
Posted by
Osvel Legon
You might have tried writing a recursive LINQ function and run into problems. For instance, the following doesn’t work because ‘factorial’ isn't defined when the right-hand side of the assignment is being evaluated:
//Error: Use of unassigned local variable 'factorial'
Func<int, int> factorial = n => n < 2 ? 1 : n * factorial(n - 1);
However, because you’re writing a lambda expression with Linq, you can use the Y combinator, a function that takes your code and returns a recursive version. For instance, using the Y combinator, you can write the following code:
Func<int, int> factorial = Extensions.YCombinator<int, int>(fact => n => n < 2 ? 1 : n * fact(n - 1));
Intuitively, the Y combinator works by calling your function on itself. For details, you can read either The Why of Y or Fixed Point Combinator.
« Back to Blog Main Page
|