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. It’s a bit odd, requiring no little attention to understand, but it works well. 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));
And then you can call it as you expect, e.g., factorial(5) returns 120.
Intuitively, the Y combinator works by calling your function on itself. Its ideas are closely related to self-reproducing code. For details, I recommend either “The Why of Y” or “Fixed Point Combinator.” Though cool, the Y combinator isn’t a panacea for all recursion – as Arvind et al note: “While the existence of the Y combinator is mathematically fascinating, fixed points [like the Y combinator] do not provide a simple encapsulation of recursion. For example, we would like to be able to declare mutually recursive functions and data structures in such a way that their definitions are clear and readable; the need to re-shape such definitions as fixed points plays havoc with such an endeavor.”
Here is an implementation of the Y combinator for Linq that Mads Torgersen and I wrote, for both delegates and expressions. (The expression implementation will be a lot simpler when Linq provides an invocation syntax for expressions.)
Posted
Aug 18 2006, 09:57 PM
by
jeffrey-schlimmer