C++中编写返回range的递归函数：编译问题与解决方案

在C++中编写返回range的递归函数时，通常会碰到两个棘手问题：

• 基准情况与递归情况的返回类型不一致
• 用auto作为返回类型时，函数内部无法递归调用自身

以整数分拆（sum decompositions）为例，先回顾严格求值的实现：

std::list<std::list<unsigned int>> SumDecompStrict(unsigned int n)
{
    if (n == 0)
        return { {} }; // 约定空列表的和为0
    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;
}

当尝试将其改为返回惰性range的版本时，代码会因上述两个问题无法编译：

auto SumDecompLazy(unsigned int n)
{
    if (n == 0)
        return std::ranges::single_view<std::list<unsigned int>>({}); // 基准情况
    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;
}

针对这些问题，C++有两种主流解决方案：

方案1：用std::ranges::any_view做类型擦除 #

std::ranges::any_view是C++20提供的类型擦除工具，可以容纳任意满足特定range概念的类型，完美解决基准情况与递归情况的类型不匹配问题，同时明确的返回类型允许函数内部递归调用。

修改后的代码如下：

#include <ranges>
#include <list>

std::ranges::any_view<std::list<unsigned int>> SumDecompLazy(unsigned int n)
{
    if (n == 0)
    {
        // 将single_view转换为any_view，统一返回类型
        return std::ranges::single_view<std::list<unsigned int>>({}) | std::views::all;
    }
    // 将递归生成的组合view也转换为any_view
    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
        | std::views::all;
}

注意：any_view带来的类型擦除会有轻微的运行时开销，但对于大多数场景可以忽略。

方案2：用C++20协程生成器std::generator #

C++20的协程特性提供了std::generator（部分编译器需要启用实验性支持，比如GCC需加-fcoroutines），它是专门用于惰性生成序列的工具，返回类型统一，天然支持递归调用，代码更简洁直观。

实现代码如下：

#include <generator>
#include <list>

std::generator<std::list<unsigned int>> SumDecompLazy(unsigned int n)
{
    if (n == 0)
    {
        co_yield {}; // 直接yield基准情况的空列表
        co_return;
    }
    for (unsigned int k = 1; k <= n; ++k)
    {
        // 递归调用并遍历每个子结果
        for (auto sub_list : SumDecompLazy(n - k))
        {
            sub_list.push_front(k);
            co_yield sub_list;
        }
    }
}

这种方式不需要处理复杂的view组合，直接通过co_yield惰性产出每个分拆结果，代码逻辑和严格版本更接近，同时保留了惰性求值的特性。

内容的提问来源于stack exchange，提问作者V. Semeria