c++ - 如何在C++中完成corecursion？

我正在从事一个C++项目，该项目需要与树结构频繁交互，这意味着许多递归函数，并且我正在寻找改进代码的方法。前几天，我碰到了corecursion，对我的应用程序探索这种策略很感兴趣。

但是，我还找不到如何使用C++完成corecursion的任何示例。为了明确我的问题，如何在C++中执行this tree traversal using corecursion？

def bf(tree):
    tree_list = [tree]
    while tree_list:
        new_tree_list = []
        for tree in tree_list:
            if tree is not None:
                yield tree.value
                new_tree_list.append(tree.left)
                new_tree_list.append(tree.right)
        tree_list = new_tree_list

如果这样做不是一个好主意，请告诉我。也就是说，在Internet上对此有一些答案将对将来尝试这样做的人很有用。 SO匹配[c++] corecursion毫无疑问，互联网的其余部分似乎缺乏有关该主题的有用信息。

最佳答案

以下内容与给定的python实现几乎相同，您现在可以在生产中使用它:

Live On Coliru

#include <vector>
#include <iostream>
#include <boost/coroutine/all.hpp>

using namespace std;

struct Node {
    char value;
    Node *left;
    Node *right;
};

using generator =
    boost::coroutines::asymmetric_coroutine<decltype(Node::value)>::pull_type;

generator bf(Node *tree) {                                //def bf(tree):
    return generator([=](auto &yield) {                   //
        vector<Node *> tree_list = {tree};                //    tree_list = [tree]
        while (!tree_list.empty()) {                      //    while tree_list:
            vector<Node *> new_tree_list;                 //        new_tree_list = []
            for (auto tree : tree_list) {                 //        for tree in tree_list:
                if (tree != nullptr) {                    //            if tree is not None:
                    yield(tree->value);                   //                yield tree.value
                    new_tree_list.push_back(tree->left);  //                new_tree_list.append(tree.left)
                    new_tree_list.push_back(tree->right); //                new_tree_list.append(tree.right)
                }                                         //
            }                                             //
            tree_list = move(new_tree_list);              //        tree_list = new_tree_list
        }                                                 //
    });                                                   //
}                                                         //

int main() {
    Node a{'a'}, b{'b'}, c{'c'}, d{'d'}, e{'e'};

    a.left = &b;
    a.right = &c;
    b.right = &d;
    d.left = &e;

    for (auto node_value : bf(&a))
        std::cout << node_value << " ";
}

为了避免分配/取消分配，我可能会这样做:

generator bf(Node *tree) {
    return generator([=](auto &yield) {
        vector<Node *> tree_list = {tree}, new_tree_list;
        while (!tree_list.empty()) {
            for (auto tree : tree_list) {
                if (tree != nullptr) {
                    yield(tree->value);
                    new_tree_list.push_back(tree->left);
                    new_tree_list.push_back(tree->right);
                }
            }
            swap(tree_list, new_tree_list);
            new_tree_list.clear();
        }
    });
}