Recursive lambdas and sequence aggregations
The fifth problem at Project Euler proposes this nostalgic primary school exercise: find the smallest quantity that is evenly divisible by some numbers, the least common multiple of 1, 2, 3, ..., 20 to be precise. To begin with, let's remember the old arithmetic formula:
Where gcd is the greatest common divisor of a and b. It's also useful to remember that the lcm is associative, that is lcm(1,2,3) is the same as lcm(lcm(1,2), 3), in other words, we can calculate the lcm of 1 and 2, then the lcm of this result and 3, then the lcm of this result and 4, and so on. In functional C#, these ideas can be expressed like so:
1 Func<int, int, int> gcd = null;
2 gcd = (x, y) => x % y == 0 ? y : gcd(y, x % y);
3
4 return Enumerable.Range(1, 20).Aggregate(1, (x,y) => x * (y / gcd(x, y)));
Line 2 finds the gcd of x and y like this: if the remainder of dividing x by y is zero, then y is the gcd, if not, we must find the gcd of y and such remainder. Note that gcd is defined recursively. The only interesting point here is that in order to define a recursive lambda expression, it is mandatory to first declare the expression variable (which we do in line 1), and only after this the compiler allows us to define a lambda expression in terms of itself. Odd, granted, but easy to get used to.
Line 4 takes the sequence 1, 2, ..., 20 and accumulates the lcm as the sequence is traversed, that is: it starts calculating lcm(1, 1) (let's call this accum1), then it calculates lcm(accum1, 2) (let's call this accum2), then it calculates lcm(accum2, 3), ..., and finishes with lcm(accum19, 20) which is precisely lcm(1, 2, ..., 20). The Aggregate() function is frequently used for chores like adding each term of a sequence, or multiplying them all, in our case we are using Aggregate() to get the succesive lcm's, which answers the question of Project Euler in two and a half lines of code, cool, eh?