c++ - Recursive lambda callbacks without Y Combinator

Question

I wish to create a callback that recursively returns itself as a callback.

The suggested method to recurse is for the function to have a reference to itself:

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

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

This fails as soon as you return it from a function:

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

which gives a segmentation fault after outputting 10 because the reference becomes invalid.

How do I do this? I have successfully used what I think is a Y Combinator (which I'll post as an answer), but it is hugely confusing. Is there a better way?

---

Other attempts

I have tried the boring approach of wrapping it in another layer of callbacks:

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

but this fails in the actual scenario, where the function is being delayed and called by an outer loop:

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

which gives 10, then 9 and then segmentation faults.

Answer 1

As you rightly pointed out, there is an invalid reference from the lambda capture [&].

Your returns are functors of various sorts, so I assume that the exact type of the return is not important, just that it behaves as a function would i.e. be callable.

If the recursive_function is wrapped in a struct or class you can map the call operator to the recursive_function member. A problem arises with the capture of the this variable. It'll be captured with the this on creation, so if the object is copied around a bit, the original this may no longer be valid. So an appropriate this can be passed in to the function at execution time (this this issue may not be a problem, but it depends heavily on when and how you call the function).

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

Alternatively, if the recursive_function can be static then declaring it as such in the original code sample may also do the trick for you.

I wanted to add some generality to the answer above, i.e. make it a template;

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

How does this work? Basically it moves the recursion from inside the function (i.e. calling itself) to an object (i.e. the function operator on the object itself) to implement the recursion. In the get_recursive_function the result type recursive<void (int)> is used as the first argument to the recursive function. It is const& because I've implemented the operator() as const in line with most standard algorithms and the default for a lambda function. It does require some "co-operation" from the implementer of the function (i.e. the use of the me parameter; itself being *this) to get the recursion working, but for that price you get a recursive lambda that is not dependent on a stack reference.