C# 递归收益率 return 不是 returning 任何东西

Question

这个问题可能在其他地方被问过，但我找不到我的问题的解决方案。该问题不是特定于语言的，可以在 python 中询问相同的问题。任务是生成字符串列表的算法，如 Enumerable.Range，但字符不仅限于 1、2、3...，还可以是任何字符序列。最简单的示例是：

测试用例 1:
输入：

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

输出：

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

测试用例 2:

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

输出：

['a','b']

功能运行良好：

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

预期和实际输出（换行符替换为逗号以保存 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

问题是把这个函数封装成一个库，所以return类型应该是IEnumerable<string>，所以即使输入大也不会爆内存。但是我的代码 不能 return 任何东西:

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

主要：

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

有人可以帮忙吗？我已将我的代码放在 github 中。如果您可以将我的实现更改为非递归但保留函数 return 类型，也表示赞赏。

Answer 1

选项 1，从递归调用中生成每个值。

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

选项 2，重用框架中内置的现有 IEnumerable 类型以避免 yield return 完全；

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

选项 3，使用嵌套循环而不是递归方法，留作 reader.

的练习

Answer 2

正如所指出的那样，调用 CharsRange2(prefix + s, pos - 1); 未被使用。您需要嵌套 foreach 和 yield 每个结果。

这是一个更基于 Enumerable.Range 想法的替代方案。

从通用基础转换器开始：

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

现在添加一个方法将其转换为一组特定的数字：

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

可以这样使用：

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

给出：

2YX

现在写 Enumerable.Range(0, 10).Select(n => n.ToBase("0X2Y")).

就很简单了

这给出：

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

这对所有非零数字都正确计数，除了零本身之外不显示前导零。

C# 递归收益率 return 不是 returning 任何东西

C# recursive yield return not returning anything

c#

algorithm

recursion

yield

permutation