C# recursive yield return not returning anything

0
votes

The problem may have been asked else where but i cannot find the solution to my problem. The problem is not language specific, the same problem can be asked in python. The task is algorithm to generate a list of strings like Enumerable.Range, but the chars are not only limited to 1, 2, 3... but can be any sequence of characters. The simplest sample is:

TestCase 1:
input:

baseChars: ['a','b'],
required string length: 2

output:

['aa','ab','ba','bb']

TestCase 2:

baseChars: ['a','b']
required string length: 1

output:

['a','b']

The function is working well:

    static IList<string> baseChars = new List<string>() { "0", "1", "2", "3" };
    static void CharsRange1(string prefix, int pos)
    {
        if (pos == 1)
        {
            foreach (string s in baseChars)
            {
                Console.WriteLine(prefix + s);
            }
        }
        else
        {
            foreach (string s in baseChars)
            {
                CharsRange1(prefix + s, pos - 1);
            }
        }
    }

Expected and actual output(newlines replaced with comma to save space):

000, 001, 002, 003, 010, 011, 012, 013, 020, 021, 022, 023, 030, 031, 032, 033, 100, 101, 102, 103, 110, 111, 112, 113, 120, 121, 122, 123, 130, 131, 132, 133, 200, 201, 202, 203, 210, 211, 212, 213, 220, 221, 222, 223, 230, 231, 232, 233, 300, 301, 302, 303, 310, 311, 312, 313, 320, 321, 322, 323, 330, 331, 332, 333

The problem is encapsule this function as a library, so return type should be IEnumerable<string>, so memory won't explode even for large input. but my code cannot return anything:

    static IEnumerable<string> CharsRange2(string prefix, int pos)
    {
        if (pos == 1)
        {
            foreach (string s in baseChars)
            {
                yield return prefix + s;
            }
        }
        else
        {
            foreach (string s in baseChars)
            {
                // here if i yield return then won't compile
                // i thought at the end of recursive loop it will return 
                CharsRange2(prefix + s, pos - 1);
            }
        }
    }

the main:

    static void Main(string[] args)
    {
        //CharsRange1("", 3);//working
        foreach (string s in CharsRange2("", 3))
        {
            Console.WriteLine(s);//nothing
        }
        Console.WriteLine("end");
        Console.ReadKey();
    }

Can anybody help? I've put my code in github. Also appreicated if you can change my implementation to non-recursive but keep the function return type.

2
c#algorithmrecursionpermutationyield
CharsRange2(prefix + s, pos - 1); So you are calling the function recursively and, umm, ignoring the results? I suspect you meant to foreach over that and use yield return. – mjwills
Your problem description isn't great either - since you haven't shown the expected result for a given set of inputs. I think I understand what you are trying to do, but am not 100% sure... – mjwills
The code shown is very confusing compared even to first bing.com/search?q=c%23+recursive+yield+return result stackoverflow.com/questions/2055927/…. Could you please review your code and make sure it makes sense... – Alexei Levenkov
Side note: counting in arbitrary base is indeed very common competition task... which seem to be what you are asking about. You may want to clarify that too with your edit (or clarify what type of sequence you want if it is not counting). – Alexei Levenkov
A (yield) return returns only to the immediate caller, not to whoever did the first call to the recursive chain – Hans Kesting

2 Answers

4
votes

Option 1, yield each value from the recursive call.

    foreach (string s in baseChars)
        foreach (var r in CharsRange2(prefix + s, pos - 1))
            yield return r;

Option 2, reuse existing IEnumerable types built into the framework to avoid yield return completely;

    if (pos == 1)
        return baseChars.Select(s => prefix + s);
    else
        return baseChars.SelectMany(s => CharsRange2(prefix + s, pos - 1));

Option 3, use nested loops instead of a recursive method, left as an exercise for the reader.

2
votes

As pointed out the call CharsRange2(prefix + s, pos - 1); isn't being used. You need to nest the foreach and yield each result.

Here's an alternative that's more based on the idea of Enumerable.Range.

Start with a general purpose base changer:

public static IEnumerable<int> ToBase(this int x, int b)
{
    IEnumerable<int> ToBaseReverse()
    {
        if (x == 0)
        {
            yield return 0;
            yield break;
        }
        int z = x;
        while (z > 0)
        {
            yield return z % b;
            z = z / b;
        }
    }

    return ToBaseReverse().Reverse();
}

Now add a method to convert this to a specific set of digits:

public static string ToBase(this int number, string digits) =>
    String.Concat(number.ToBase(digits.Length).Select(x => digits[x]));

This can be used like this:

string result = 45.ToBase("0X2Y");
Console.WriteLine(result);

Which gives:

2YX

Now it's trivial to write Enumerable.Range(0, 10).Select(n => n.ToBase("0X2Y")).

That gives:

0, X, 2, Y, X0, XX, X2, XY, 20, 2X

This counts properly for all non-zero numbers, without displaying the leading zeros except for zero itself.