Searching a sequence for a pattern I have written the following tiny extension method to help me when I'm working with sequences in which I have to find a pattern.

public static IEnumerable&lt;T[]&gt; SearchPattern&lt;T&gt;(this IEnumerable&lt;T&gt; seq, params Func&lt;T[], T, bool&gt;[] matches)
{
      Contract.Requires(seq != null);
      Contract.Requires(matches != null);
      Contract.Requires(matches.Length &gt; 0);

      var matchedItems = new List&lt;T&gt;(matches.Length);
      int itemIndex = 0;

      foreach (T item in seq)
      {
          if (matches[matchedItems.Count](matchedItems.ToArray(), item))
          {
              matchedItems.Add(item);

              if (matchedItems.Count == matches.Length)
              {
                  yield return matchedItems.ToArray();

                  matchedItems.Clear();
              }
          }
          else
          {
              if (matchedItems.Any())
              {
                  foreach (T[] results in seq.Skip(itemIndex - matchedItems.Count + 1).SearchPattern(matches)) // is this a tail call? can it be optimized?
                  {
                      yield return results;
                  }
                  break;
              }
          }
          itemIndex++;
      }
}


It appears to be working fine, but I'm wondering if there's a better way to do it.
Primarily I'm concerned with the recursive call (at the nested foreach), which makes the method very inefficient, not to mention potential stack-overflows when working with very large collections.

I know about tail-calls, and that they can be optimized into a loop (like in F#). I also recall having seen something about tail-calls on an IL level. What confuses me is that I'm already using the iterator pattern (yield return) - so is it a tail call at all? If it is, is it one I can eliminate?

Any input would be much appreciated!

Edit: usage sample:

var results = (new int[] { 0, 1, 2, 3, 3, 4, 4, 5, 7, 9 }).SearchPattern(
    (prevs, curr) =&gt; true,
    (prevs, curr) =&gt; prevs[0] == curr,
    (prevs, curr) =&gt; curr % 2 != 0
); // =&gt; { [ 4, 4, 5 ] }
Personally, here is how I would do it. I think this is pretty straight-forward. I think it is also no less efficient than the other (longer, more complex) answer. The method Subarray is something I wrote before, I didn’t write it just for this.

/// &lt;summary&gt;Similar to &lt;see cref="string.Substring(int,int)"/&gt;, only for arrays. Returns a new
/// array containing &lt;paramref name="length"/&gt; items from the specified
/// &lt;paramref name="startIndex"/&gt; onwards.&lt;/summary&gt;
public static T[] Subarray&lt;T&gt;(this T[] array, int startIndex, int length)
{
    if (array == null)
        throw new ArgumentNullException("array");
    if (startIndex &lt; 0)
        throw new ArgumentOutOfRangeException("startIndex", "startIndex cannot be negative.");
    if (length &lt; 0 || startIndex + length &gt; array.Length)
        throw new ArgumentOutOfRangeException("length", "length cannot be negative or extend beyond the end of the array.");
    T[] result = new T[length];
    Array.Copy(array, startIndex, result, 0, length);
    return result;
}

public static IEnumerable&lt;T[]&gt; SearchPattern&lt;T&gt;(this IEnumerable&lt;T&gt; seq, params Func&lt;T[], T, bool&gt;[] matches)
{
    Contract.Requires(seq != null);
    Contract.Requires(matches != null);
    Contract.Requires(matches.Length &gt; 0);

    // No need to create a new array if seq is already one
    var seqArray = seq as T[] ?? seq.ToArray();

    // Check every applicable position for the matching pattern
    for (int j = 0; j &lt;= seqArray.Length - matches.Length; j++)
    {
        // If this position matches...
        if (Enumerable.Range(0, matches.Length).All(i =&gt;
            matches[i](seqArray.Subarray(j, i), seqArray[i + j])))
        {
            // ... yield it
            yield return seqArray.Subarray(j, matches.Length);

            // and jump to the item after the match so we don’t get overlapping matches
            j += matches.Length - 1;
        }
    }
}