CODEWITHSUNDEEP
c#recursion
user718642
user718642

Reputation:

How do I avoid infinite recursion with a custom enumerator?

I made an extension method to find the number of consecutive values in a collection. Because it is generic, I allow the caller to define the "incrementor" which is a Func<> that is supposed to increment the value in order to check for the existence of a "next" value.

However, if the caller passes an improper incrementor (i.e. x => x), it will cause an infinite recursive loop. Any suggestions on a clean way to prevent this?

public static int CountConsecutive<T>(this IEnumerable<T> values, T startValue, Func<T, T> incrementor)
{
    if (values == null)
    {
        throw new ArgumentNullException("values");
    }
    if (incrementor == null)
    {
        throw new ArgumentNullException("incrementor");
    }
    var nextValue = incrementor(startValue);
    return values.Contains(nextValue)
        ? values.CountConsecutive(nextValue, incrementor) + 1
        : 1;
}

Upvotes: 6

Views: 523

Answers (3)

Austin Salonen
Austin Salonen

Reputation: 50225

In the purest sense, this is an attempt at the Halting Problem and is undecidable. For all but the simplest cases, you'll have to trust those calling your method.

Like others have shown, you can do a simple check of equality to show that the next value is different. Storing every visited T will work but you'll have to worry about memory eventually.

As an aside, here's an easily implemented StackOverflowException so you have to be wary of any data set that will have a lot on consecutive values.

var x = Enumerable.Range(1, 100000).CountConsecutive(1, x => x+1);

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726609

To deal with the simplest case, you can do this:

var nextValue = incrementor(startValue);
if (nextValue.Equals(startValue)) {
    throw new ArgumentException("incrementor");
}

For general case, do this:

public static int CountConsecutive<T>(this IEnumerable<T> values, T startValue, Func<T, T> incrementor) {
    if (values == null) {
        throw new ArgumentNullException("values");
    }
    if (incrementor == null) {
        throw new ArgumentNullException("incrementor");
    }
    ISet<T> seen = new HashSet<T>();
    return CountConsecutive(values, startValue, incrementor, seen);
}

private static int CountConsecutive<T>(IEnumerable<T> values, T startValue, Func<T, T> incrementor, ISet<T> seen) {
    if (!seen.Add(startValue)) {
        throw new ArgumentException("incrementor");
    }
    var nextValue = incrementor(startValue);
    return values.Contains(nextValue)
        ? values.CountConsecutive(nextValue, incrementor) + 1
        : 1;
}

Upvotes: 4

zmbq
zmbq

Reputation: 39013

You can compare nextValue to startValue (you'll need T to implement IComparable).

This will solve this bug, it won't solve a nasty incrementor bug that returns a loop - a1, a2, a3, ..., an, a1. I don't think you want to handle this case, though

Upvotes: 1

Related Questions