c++ - C++ 中 lambda 和常规函数的不同堆栈深度？

Question

考虑一个普通的递归函数:

#include <iostream>
#include <functional>

void f(unsigned long long int x) {
    std::cout << x << "\n";
    if(x < 1e9)
        f(x+1);
}

int main() {
    f(1);
    return 0;
}

这在 43033 处终止。

现在考虑一个递归的 lambda:

#include <iostream>
#include <functional>

int main() {
    std::function<void(int)> g = [&g](unsigned long long int x) {
        std::cout << x << "\n";
        if(x < 1e9)
            g(x+1);
    };
    g(1);
    return 0;
}

这终止于11736的低得多的堆栈深度。

为什么 lambda 的最大堆栈深度较低？

(使用 g++ (GCC) 5.4.0 编译，使用 -std=c++14 -Wall)

另请注意，使用 -O3 优化进行编译允许几乎无限 递归深度，但 lambda 仍会在 25k 处终止。

---

编辑:在@Yakk 之后，这里是 Y-combinator 的结果:

#include <iostream>
#include <functional>

using namespace std;

template <typename T, typename R>
function<R(T)> Y(function<function<R(T)>(function<R(T)>)> f) {
    // Y f = f (λx.(Y f) x)
    return f([=](T x) { return Y(f)(x); });
}

int main() {
    using fg = function<void(int)>;
    function<fg(fg)> sg = [](fg g) {
        return [g](unsigned long long int x) {
            std::cout << x << "\n";
            if(x < 1e9)
                g(x+1);
        };
    };

    Y(sg)(1);
    return 0;
}

这在 4781 和 9221 处终止，分别有和没有 -O3。

Answer 1

std 函数与 lambda 的含义不同。 std 函数是一个能够存储一些 lambda 表达式的对象，或者函数指针，或者指向成员函数的指针，或者指向成员数据的指针，或者几乎任何可以兼容地覆盖 operator() 的对象。

当您将 lambda 存储在 std 函数中时，会产生一些开销。不多，但有一些。这些开销中的一部分可能会显示为更多地使用堆栈(并且在未优化的构建中开销会更大)。

您可以使用 y combinator 更直接地使用 lambda 进行递归，但即使在那里，您也会将对自身的引用作为参数传递，除非递归被优化器消除，否则它可能会使用更多堆栈。 (高度调整的优化器可能会注意到可以消除无状态的 lambda 引用参数，但这似乎很难解决)。