Different stack depth for lambdas and regular functions in C++?

Question

Consider a normal recursive function:

#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;
}

This terminates at 43033.

Now consider a recursive 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;
}

This terminates at a much lower stack depth of 11736.

Why do lambdas have a lower max stack depth?

(Compiling with g++ (GCC) 5.4.0, with -std=c++14 -Wall)

Also note that compiling with -O3 optimization allows for practically infinite recursion depth, but the lambda still terminates at 25k.

---

EDIT: Following @Yakk, here are results with the 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;
}

This terminates at 4781 and 9221 with and without -O3 respectively.

Answer 1

std function does not mean the same thing as lambda. A std function is an object capable of storing some lambdas, or a function pointer, or a pointer to member function, or a pointer to member data, or almost any object that overrides operator() compatibly.

When you store a lambda within a std function, there is some overhead. Not much, but some. Some of this overhead may show up as using the stack more (and the overhead will be larger in unoptimized builds).

You can more directly recurse using a lambda by using the y combinator, but even there you'll be passing a reference-to-self as a parameter, and unless the recursion is eliminated by the optimizer it will probably use more stack. (A highly tweaked optimizer could notice that a stateless lambda reference argument could be eliminated, but that seems tricky to work out).