## 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?

Published Thursday, April 24, 2008 1:22 AM by Edgar Sánchez

#### # dividing line

Friday, April 25, 2008 3:16 AM by dividing line

Pingback from  dividing line

#### # associative

Saturday, May 03, 2008 1:05 PM by associative

Pingback from  associative

#### # re: Recursive lambdas and sequence aggregations

Friday, July 18, 2008 5:59 AM by Jedrzej

Simpler:

Enumerable.Range(1, 10).Aggregate((x, y) => x * y / gci(x, y)));

Thanks for recursive lambdas your blog is my favourite for LINQ tricks :)

#### # re: Recursive lambdas and sequence aggregations

Thursday, December 04, 2008 10:50 AM by Arnie

<a href= howlongdoesspottinglast.looksaua.info >how long does spo

#### # re: Recursive lambdas and sequence aggregations

Wednesday, April 20, 2011 3:34 AM by weblogs.asp.net

Recursive lambdas and sequence aggregations.. He-he-he :)

#### # re: Recursive lambdas and sequence aggregations

Friday, May 06, 2011 2:34 PM by weblogs.asp.net

Recursive lambdas and sequence aggregations.. Huh, really? :)

#### # re: Recursive lambdas and sequence aggregations

Monday, June 20, 2011 5:11 AM by weblogs.asp.net

Recursive lambdas and sequence aggregations.. Very nice :)

#### # re: Recursive lambdas and sequence aggregations

Saturday, July 02, 2011 5:09 AM by ab8q pon videos w8sw

Recursive lambdas and sequence aggregations.. Great idea :)