c++ - 没有 Y Combinator 的递归 lambda 回调

Question

我希望创建一个回调，它以回调的形式递归返回自身。

建议的递归方法是让函数引用自身:

std::function<void (int)> recursive_function = [&] (int recurse) {
    std::cout << recurse << std::endl;

    if (recurse > 0) {
        recursive_function(recurse - 1);
    }
};

一旦你从一个函数返回它就会失败:

#include <functional>
#include <iostream>

volatile bool no_optimize = true;

std::function<void (int)> get_recursive_function() {
    std::function<void (int)> recursive_function = [&] (int recurse) {
        std::cout << recurse << std::endl;

        if (recurse > 0) {
            recursive_function(recurse - 1);
        }
    };

    if (no_optimize) {
        return recursive_function;
    }

    return [] (int) {};
}

int main(int, char **) {
    get_recursive_function()(10);
}

在输出 10 后给出一个段错误，因为引用变得无效。

我该怎么做？我已经成功地使用了我认为是 Y Combinator 的东西 (我将作为答案发布)，但这非常令人困惑。有没有更好的办法？

---

其他尝试

我尝试过将它包装在另一层回调中的无聊方法:

#include <functional>
#include <iostream>
#include <memory>

volatile bool no_optimize = true;

std::function<void (int)> get_recursive_function() {
    // Closure to allow self-reference
    auto recursive_function = [] (int recurse) {
        // Actual function that does the work.
        std::function<void (int)> function = [&] (int recurse) {
            std::cout << recurse << std::endl;

            if (recurse > 0) {
                function(recurse - 1);
            }
        };

        function(recurse);
    };

    if (no_optimize) {
        return recursive_function;
    }

    return [] (int) {};
}

int main(int, char **) {
    get_recursive_function()(10);
}

但这在实际场景中失败了，函数被延迟并被外循环调用:

#include <functional>
#include <iostream>
#include <memory>
#include <queue>

volatile bool no_optimize = true;

std::queue<std::function<void (void)>> callbacks;

std::function<void (int)> get_recursive_function() {
    // Closure to allow self-reference
    auto recursive_function = [] (int recurse) {
        // Actual function that does the work.
        std::function<void (int)> function = [&] (int recurse) {
            std::cout << recurse << std::endl;

            if (recurse > 0) {
                callbacks.push(std::bind(function, recurse - 1));
            }
        };

        function(recurse);
    };

    if (no_optimize) {
        return recursive_function;
    }

    return [] (int) {};
}

int main(int, char **) {
    callbacks.push(std::bind(get_recursive_function(), 10));

    while (!callbacks.empty()) {
        callbacks.front()();
        callbacks.pop();
    }
}

给出 10，然后是 9，然后是段错误。

Answer 1

正如您正确指出的那样，lambda 捕获中存在无效引用 [&] .

您的返回值是各种类型的仿函数，因此我假设返回值的确切类型并不重要，只要它表现得像一个函数即可，即可调用。

如果recursive_function包裹在 struct 中或 class您可以将调用运营商映射到 recursive_function成员。捕获 this 时出现问题多变的。它将被 this 捕获在创建时，如果对象被复制了一点，原始的 this可能不再有效。所以一个合适的this可以在执行时传递给函数(这个 this 问题可能不是问题，但它在很大程度上取决于您调用函数的时间和方式)。

#include <functional>
#include <iostream>

volatile bool no_optimize = true;

struct recursive {
    std::function<void (recursive*, int)> recursive_function = [] (recursive* me, int recurse) {
        std::cout << recurse << std::endl;

        if (recurse > 0) {
            me->recursive_function(me, recurse - 1);
        }
    };

    void operator()(int n)
    {
        if (no_optimize) {
            recursive_function(this, n);
        }
    }
};

recursive get_recursive_function() {
    return recursive();
}

int main(int, char **) {
    get_recursive_function()(10);
}

或者，如果 recursive_function可以是static然后在原始代码示例中声明它也可以为您解决问题。

我想为上面的答案添加一些通用性，即将其设为模板；

#include <functional>
#include <iostream>

volatile bool no_optimize = true;

template <typename Signature>
struct recursive;

template <typename R, typename... Args>
struct recursive<R (Args...)> {
    std::function<R (recursive const&, Args... args)> recursive_function;

    recursive() = default;

    recursive(decltype(recursive_function) const& func) : recursive_function(func)
    {
    }

    template <typename... T>
    R operator()(T&&... args) const
    {
        return recursive_function(*this, std::forward<Args>(args)...);
    }
};

recursive<void (int)> get_recursive_function()
{
    using result_type = recursive<void (int)>;

    if (!no_optimize) {
        return result_type();
    }

    result_type result ([](result_type const& me, int a) {
        std::cout << a << std::endl;

        if (a > 0) {
            me(a - 1);
        }
    });

    return result;
}

int main(int, char **) {
    get_recursive_function()(10);
}

这是如何运作的？基本上它将递归从函数内部(即调用自身)移动到对象(即对象本身的函数运算符)以实现递归。在get_recursive_function结果类型 recursive<void (int)>用作递归函数的第一个参数。是const&因为我已经实现了 operator()作为const符合大多数标准算法和 lambda 函数的默认值。它确实需要函数实现者的一些“合作”(即使用 me 参数；本身就是 *this )来使递归工作，但是对于这个价格你得到一个递归的 lambda 不是依赖于堆栈引用。