C# recursive yield return not returning anything

Question

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.

Answer 1

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.

Answer 2

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.