C# Recursive algorithm error using a.Skip(1) as input-CodePudding

using System;
using System.Collections.Generic;
using System.Linq;

internal class Program
{
    public static bool Aa(int[] a, int k)
    {
        for (int i = 1; i < a.Length; i  )
            if (a[0]   a[i] == k)
                return true;
        if (a.Length != 1)
            Aa(a.Skip(1), k);
        return false;
    }

    static void Main(string[] args)
    {
        int[] a = { 1, 2, 3, 4, 2, 3, 2, 1 };
        Console.WriteLine(Aa(a, 10));
        Console.ReadLine();
    }
}

The following build error occurs on the recursive method call Aa(a.Skip(1), k);

Argument 1: cannot convert from 'System.Collections.IEnumerable' to 'int[]'

CodePudding user response：

you need to pass an Array obj to Aa Like this :

a.Skip().ToArray();

CodePudding user response：

Like most LINQ methods, Skip is designed to work with enumerables, not arrays.

public static System.Collections.Generic.IEnumerable<TSource> Skip<TSource> (this System.Collections.Generic.IEnumerable<TSource> source, int count);

It is OK to pass in an array, but it will implicitly be upcast to the more generalized type IEnumerable, and that is also the type that will be returned by Skip.

int[] whatGoesIn = {1, 2, 3};
IEnumerable<int> whatComesOut = whatGoesIn.Skip(1);

You cannot safely downcast the return value to int[]. As proposed by others, LINQ has a convenient method ToArray, but think twice before using it. The method will create a completely new array object, which is often a total waste of memory as well as CPU time. Only use this method when you really need an array.

In your case, I strongly recommend against arrays; every little bit of speed advantage offered by arrays would be undone tenfold by the use of ToArray. Skip shines when used on IEnumerable, as it will simply step from one element to the next, rather than copy an entire array.

So instead of declaring parameter a as an array:

public static bool Aa(int[] a, int k)

declare a as an enumerable:

public static bool Aa(IEnumerable<int> a, int k)

Notice this will immediately eliminate your error. It will introduce a few new ones though. Like in the for loop; IEnumerable<int> has no property Length.

for (int i = 1; i < a.Length; i  )
    if (a[0]   a[i] == k)
        return true;

Upon close inspection, you are basically looking for an array element that equals k - a[0]. Just use Contains:

bool found = a.Skip(1).Contains(k - a.First());
if (found) return true;

Another reference to Length:

if (a.Length != 1)
    Aa(a.Skip(1), k);
return false;

That's weird; you call Aa but don't do anything with its return value. You probably meant this:

if (a.Length != 1)
    return Aa(a.Skip(1), k);
return false;

I will not use Count, as it is potentially expensive on long enumerables. I am not actually interested in the exact length; we can stop counting after the second element.

return a.Skip(1).Any() && Aa(a.Skip(1), k);

After refactoring, the whole function becomes a one-liner:

public static bool Aa(IEnumerable<int> a, int k)
{
    return a.Skip(1).Contains(k - a.First()) || (a.Skip(1).Any() && Aa(a.Skip(1), k));
}

I'd recommend to make the function robust against zero-length arrays by moving the 'Any' check to the front.

public static bool Aa(IEnumerable<int> a, int k)
{
    return a.Any() && (a.Skip(1).Contains(k - a.First()) || Aa(a.Skip(1), k));
}

Note: I'm not too thrilled about the use of recursion here, because nesting depth is proportional to array length. For long arrays, this may cause a stack overflow. In theory, the compiler could optimize away the tail recursion (this answer suggests it may even do so), but I'd feel safer with a loop.