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

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()的对象的对象.

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

你可以使用y组合器更直接地使用lambda递归,但即使在那里你也会传递一个reference-to-self作为参数,除非优化器消除了递归,否则它可能会使用更多的堆栈.(一个经过高度调整的优化器可能会注意到可以消除无状态lambda引用参数,但这似乎很难解决).