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

Question

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[]'

Please add code and data as text ([using code formatting](/editing-help#code)), not images. Images: A) don't allow us to copy-&-paste the code/errors/data for testing; B) don't permit searching based on the code/error/data contents; and [many more reasons](//meta.stackoverflow.com/a/285557). Images should only be used, in addition to text in code format, if having the image adds something significant that is not conveyed by just the text code/error/data. — gunr2171, Nov 27 '22 at 19:35
Please consider using more descriptive method and variable names. "Aa" doesn't convey any meaning towards what the method does, neither does "a" and "k" for what data they are expecting. — gunr2171, Nov 27 '22 at 19:36
Do you understand what an IEnumerable is? Have you experimented with chaining methods after `Skip()`? There are some methods that start with `To..`. — gunr2171, Nov 27 '22 at 19:38
Does this answer your question? [Best way to convert IList or IEnumerable to Array](https://stackoverflow.com/questions/268671/best-way-to-convert-ilist-or-ienumerable-to-array) — gunr2171, Nov 27 '22 at 19:39
Call [`.ToArray()`](https://learn.microsoft.com/en-us/dotnet/api/system.linq.enumerable.toarray?redirectedfrom=MSDN&view=net-7.0#System_Linq_Enumerable_ToArray__1_System_Collections_Generic_IEnumerable___0__) on the `IEnumerable` — trashr0x, Nov 27 '22 at 19:39
You want to pass in an array where you want ot skip first element so you should use: a.Skip(1).ToArray() — Aldert, Nov 27 '22 at 19:41
Please consider writing function `Aa` in such a way that it will accept not just an array of integers, but _any_ kind of enumerable of integers. Not only does it fit LINQ better (thereby fixing the error), it will also be more efficient (`.ToArray()` is pretty poor advice here). BTW, you are discarding the return value of the recursive call. — Ruud Helderman, Nov 27 '22 at 19:58

score 1 · Answer 1 · answered Nov 27 '22 at 19:52

1

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

a.Skip().ToArray();

answered Nov 27 '22 at 19:52

Moatasem La Kremed

121
9

Ruud Helderman · Answer 2 · 2022-11-28T13:14:49.010

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, ToArray would have to be called once for every element of the original array. This will put a lot of strain on the heap. With a big array, you will be seeing a lot of GC.

Make up your mind: either use Skip, or use arrays. Don't do both.

Option 1: Skip, without arrays

Follow the LINQ philosophy and use enumerables all the way. This has the advantage that it will work on any enumerable: arrays, collections, lists, dictionaries...

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));
}

Option 2: arrays, without Skip

Arrays have one big advantage over enumerables: they are fast. OP's for loop is faster than my call to Contains. There is no need to use Skip; just start iterating at a different index.

public static bool Aa(int[] a, int k, int start = 0)
{
    for (int i = start + 1; i < a.Length; i++)
        if (a[start] + a[i] == k)
            return true;
    if (start < a.Length)
        return Aa(a, k, start + 1);
    return false;
}

This is twice as fast as the ToArray solution, and three times as fast as enumerables.

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, but even in .NET 6, it doesn't (although this answer suggests otherwise).

Skip works fine on arrays, it returns an IEnumerable, thats the issue — pm100, Nov 27 '22 at 22:25
@pm100 Exactly my point. After my changes, `Aa` still _accepts_ an array. It just no longer _demands_ an array. — Ruud Helderman, Nov 27 '22 at 22:41
@pm100 Bad idea to let `ToArray` create a new array for every recursive call; I tried and witnessed lots of GC on big arrays. Besides, why `Skip` when you can simply increment an index variable to advance your starting point? I edited my answer to clarify this. — Ruud Helderman, Nov 28 '22 at 13:27

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

2 Answers2

Option 1: Skip, without arrays

Option 2: arrays, without Skip

Note