4

I'm trying to figure out how to use LINQ to limit a recursive call.

My intention with the following code is to run through a list of numbers (num) and for each number recursively count/print up to a set amount (6).

the sequence in newnum that I'm trying to get is : 3 4 5 1 2 3 4 5 5 2 3 4 5

but naturally I'm running into an infinite loop instead. The .Where predicate isn't stopping the loop as I had thought and it's probable my base case is off. Any insight as to the proper way to set this up? Thank you.

var num = new[] {3, 1, 8, 5, 2};

    Func<int, int> writeString = delegate(int count)
                        {                       
                            Func<int, int> recursiveWrite = null;
                            recursiveWrite = n => 
                                                {
                                                    Console.WriteLine("string " + n); 

                                                    recursiveWrite(n+1);
                                                    return n;
                                                };
                            return recursiveWrite(count);
                        };

    var newnum = num.Where(n => writeString(n) < 6);   // is this possible?
    newnum.ToList().ForEach( w => Console.WriteLine(w));

I noticed that a similar stopping pattern occurs in the following sample code, the .Where will only include factorials less than 7, what am I missing?

var numbers = new[] { 5,1,3,7,2,6,4};

Func<int, int> factorial = delegate(int num) {
        Func<int, int> locFactorial = null;
        locFactorial = n => n == 1 ? 1 : n * locFactorial(n - 1);
        return locFactorial(num);
};

var smallnums = numbers.Where(n => factorial(n) < 7);
AakashM
  • 62,551
  • 17
  • 151
  • 186
user1297102
  • 661
  • 8
  • 14

4 Answers4

4

The answer is that you don't have a base case. Once your recursive function is executed, there is nothing to stop it - LINQ doesn't perform any kind of magic that can modify the internal logic of another function.

In the example you are missing this key bit of code that will stop the recursion - the base case:

locFactorial = n => n == 1 ? 1 : n * locFactorial(n - 1);

The ternary operator checks to see if n==1 - if it is, it returns 1. This is the base case that your function lacks.

There is no way to provide a base-case to your function through LINQ alone. You need to build this into the recursive function.

Additionally, you are returning the wrong type from your recursive function if you want to return a list of numbers from a single number: this is fundamentally a different case from the Factorial function which returns a single number given a single number.

Here is a function that does what you require without using recursion:

void Main()
{
    var numbers = new[] {3, 1, 8, 5, 2};

    numbers.SelectMany(x => GetIncreasing(x).TakeWhile(y => y < 6));
}

IEnumerable<int> GetIncreasing(int x)
{
   while (true)
       yield return x++;
}
Alex
  • 7,639
  • 3
  • 45
  • 58
  • Thanks! that explains it nicely! i see i was wrong to think LINQ could put the kibosh on the recursion – user1297102 Mar 14 '13 at 21:13
  • So GetIncreasing() sets up an infinite sequence, which can be halted by the TakeWhile()? – user1297102 Mar 14 '13 at 21:23
  • 1
    Exactly right - the key is the lazy evaluation of `yield` and the way that enumerators work - [this answer](http://stackoverflow.com/questions/410026/proper-use-of-yield-return/410058#410058) has a good explanation – Alex Mar 15 '13 at 10:18
  • Thanks for the confirmation & link! – user1297102 Mar 15 '13 at 17:59
2

You could just stick with generating sequences that fits your requirements, something like:

var num = new[] { 3, 1, 8, 5, 2 };
var limit = 6;

var query = from n in num
            where n < limit // sanity check
            from pn in Enumerable.Range(n, limit - n)
            select pn;

Decent performance and clean code

Polity
  • 14,734
  • 2
  • 40
  • 40
  • very elegant indeed, i need to look into LINQ Query Operations. Thanks! – user1297102 Mar 14 '13 at 21:14
  • is there anyway write this expression without the "sanity check"? for example in the set of num and within that the set of enumerables in the range of num to limit? – user1297102 Mar 14 '13 at 21:46
  • 1
    Sure, either ensure that a num entry does not exceed limit or limit the 2nd argument of Range to 0. `Enumerable.Range(n, Math.Max(0, limit - n))` – Polity Mar 15 '13 at 02:53
1

The difference with the factorial sample is the placing of the end condition. This is what you should do:

recursiveWrite = n => 
                    {
                        Console.WriteLine("string " + n);
                        if (n < 6)
                            recursiveWrite(n+1);
                        return n;
                    };
Gert Arnold
  • 105,341
  • 31
  • 202
  • 291
1

Not completely sure of what you are trying to achieve but I hope this willl help. You need a stop condition in your recursive lambda (as n==1 in factorial). With nested funcs, you can inject this limit "dynamically".

class Program
{
    static void Main(string[] args)
    {
        var num = new[] { 3, 1, 8, 5, 2 };
        Func<int, Func<int, IEnumerable<int>>> writeString = 
            delegate(int maxcount)
            {
                Func<int, IEnumerable<int>> recursiveWrite = null;
                recursiveWrite = (n) =>
                    {
                        if (n < maxcount)
                        {
                            Console.WriteLine("string " + n);
                            var rec = recursiveWrite(n + 1);
                            return new List<int>(){n}.Concat(rec);
                        }
                        return new List<int>();
                    };
                return recursiveWrite;
            };

        var newnum = num.SelectMany(n => writeString(6)(n));   // is this possible?
        newnum.ToList().ForEach(w => Console.WriteLine(w));
        Console.ReadLine();
    }
}
jbl
  • 15,179
  • 3
  • 34
  • 101