在C++中，我们如何编写返回范围的递归函数？

Question

在 C++ 中，我们在编写返回范围的递归函数时面临两个问题

• 基本案例类型与递归案例类型不同
• 范围经常涉及 lambda，因此返回类型为 auto，这可以防止递归

让我用求和分解来说明。这是一个严格（非惰性）的解决方案

std::list<std::list<unsigned int>> SumDecompStrict(unsigned int n)
{
    if (n == 0)
        return { {} }; // the sum of the empty list is 0 by convention
    std::list<std::list<unsigned int>> ret;
    for (unsigned int k = 1; k <= n; k++)
    {
        std::list<std::list<unsigned int>> ll = SumDecompStrict(n - k);
        for (auto& l : ll)
            l.push_front(k);
        ret.splice(ret.end(), std::move(ll));
    }
    return ret;
}

现在我想通过返回一个范围将其转换为总和分解的惰性生成器，它可能看起来像这样

auto SumDecompLazy(unsigned int n)
{
    if (n == 0)
        return std::ranges::single_view<std::list<unsigned int>>({}); // the sum of the empty list is 0 by convention
    return std::views::iota(1, n+1)
        | std::views::transform([n](unsigned int k) {
            return SumDecompLazy(n - k)
                | std::views::transform([k](std::list<unsigned int>& l) { l.push_front(k); return l; });
            }
        | std::views::join;
}

但是

SumDecompLazy

无法编译，因为提到的两个问题：

• std::ranges::single_view<std::list<unsigned int>>({})

  的类型与递归案例的类型不同
• 自动返回类型可防止从自身调用

  SumDecompLazy

这个问题在其他编程语言中已经得到解决，例如 C# 中的

IEnumerable

类型，或者 F# 中的别名

seq

。 C++有解决办法吗？

Answer 1

C++23 有

std::generator

，它允许您将其表达为协程，或者显式循环

std::generator<std::list<unsigned int>> SumDecompLoop(unsigned int n)
{
    if (n == 0)
    {
        co_yield {};
        co_return; // Not strictly necessary, we never enter the loop below
    }

    for (unsigned int k = 1; k <= n; k++)
    {
        for (auto l : SumDecompLoop(n - k))
        {
            l.push_front(k);
            co_yield std::move(l);
        }
    }
}

或使用量程适配器

std::generator<std::list<unsigned int>> SumDecompRange(unsigned int n)
{
    if (n == 0)
        co_yield {}; 
    co_yield std::ranges::elements_of(std::views::iota(1, n+1)
        | std::views::transform([n](unsigned int k) {
            return SumDecompRange(n - k)
                | std::views::transform([k](std::list<unsigned int>& l) { l.push_front(k); return l; });
            }
        | std::views::join);
}