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.

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
– mjwills, Commented Jun 16, 2020 at 5:07
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
– mjwills, Commented Jun 16, 2020 at 5:11
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
– Alexei Levenkov, Commented Jun 16, 2020 at 5:15
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
– Alexei Levenkov, Commented Jun 16, 2020 at 5:17
A (yield) return returns only to the immediate caller, not to whoever did the first call to the recursive chain — Hans Keﬆing
– Hans Keﬆing, Commented Jun 16, 2020 at 5:26

Jeremy Lakeman · Accepted Answer · 2020-06-16 05:21:29Z

4

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.

answered Jun 16, 2020 at 5:21

Jeremy Lakeman

11.6k30 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Lei Yang Over a year ago

thanks! exactly what i want. just amazed by the powerful linq.

Enigmativity · Accepted Answer · 2020-06-16 06:29:52Z

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.

answered Jun 16, 2020 at 6:29

Enigmativity

117k12 gold badges101 silver badges184 bronze badges

9 Comments

Lei Yang Over a year ago

i'm sorry to mention that your answer seems to be converting input dec number to other base? my question is only about generating continous sequence(just like 000, 001, ... 002, 010... 111). so if the steps contain some calculations(devide and mod) the performance might be bad, i guess.

Enigmativity Over a year ago

@LeiYang - Probably not. Divide and mod are exceedingly fast. Those operations get very close to the CPU core. Also string appending operations like prefix + s are incredibly slow. The only way to tell is to run both sets of code and compare the performance.

Enigmativity Over a year ago

@LeiYang - Which I did. It turns out that mine is about 4x slower. I suspect, from my experience, that's nothing to do with the divide and mod, but more the IEnumerable<int> and the Reverse(). So, time to try to make a faster version. :-)

Lei Yang Over a year ago

thanks for clarifying this. i ended up with @Jeremy Lakeman's solution but changed the function like this public IEnumerable<string> Permutate(char[] strchars, int pos) where init strchars[pos] is updated in each loop. and returning new string(strchars). do you think this is faster than old version of string + ?

Enigmativity Over a year ago

@LeiYang - I'd need to see the code, but the only real way to know is to time it.

|

Collectives™ on Stack Overflow

C# recursive yield return not returning anything

2 Answers 2

1 Comment

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related