Recursive lambda functions in C++11

I am new to C++11. I am writing the following recursive lambda function, but it doesn't compile.

sum.cpp

#include <iostream>
#include <functional>

auto term = [](int a)->int {
  return a*a;
};

auto next = [](int a)->int {
  return ++a;
};

auto sum = [term,next,&sum](int a, int b)mutable ->int {
  if(a>b)
    return 0;
  else
    return term(a) + sum(next(a),b);
};

int main(){
  std::cout<<sum(1,10)<<std::endl;
  return 0;
}

compilation error:

vimal@linux-718q:~/Study/09C++/c++0x/lambda> g++ -std=c++0x sum.cpp

sum.cpp: In lambda function: sum.cpp:18:36: error: ‘((<lambda(int, int)>*)this)-><lambda(int, int)>::sum’ cannot be used as a function

gcc version

gcc version 4.5.0 20091231 (experimental) (GCC)

But if I change the declaration of sum() as below, it works:

std::function<int(int,int)> sum = [term,next,&sum](int a, int b)->int {
   if(a>b)
     return 0;
   else
     return term(a) + sum(next(a),b);
};

Could someone please throw light on this?

Think about the difference between the auto version and the fully specified type version. The auto keyword infers its type from whatever it's initialized with, but what you're initializing it with needs to know what its type is (in this case, the lambda closure needs to know the types it's capturing). Something of a chicken-and-egg problem.

On the other hand, a fully specified function object's type doesn't need to "know" anything about what is being assigned to it, and so the lambda's closure can likewise be fully informed about the types its capturing.

Consider this slight modification of your code and it may make more sense:

std::function<int(int,int)> sum;
sum = [term,next,&sum](int a, int b)->int {
if(a>b)
    return 0;
else
    return term(a) + sum(next(a),b);
};

Obviously, this wouldn't work with auto. Recursive lambda functions work perfectly well (at least they do in MSVC, where I have experience with them), it's just that they aren't really compatible with type inference.

The trick is to feed in the lambda implementation to itself as a parameter, not by capture.

const auto sum = [term,next](int a, int b) {
  auto sum_impl=[term,next](int a,int b,auto& sum_ref) mutable {
    if(a>b){
      return 0;
    }
    return term(a) + sum_ref(next(a),b,sum_ref);
  };
  return sum_impl(a,b,sum_impl);
};

All problems in computer science can be solved by another level of indirection. I first found this easy trick at http://pedromelendez.com/blog/2015/07/16/recursive-lambdas-in-c14/

It does require C++14 while the question is on C++11, but perhaps interesting to most.

Going via std::function is also possible but can result in slower code. But not always. Have a look at the answers to https://stackoverflow.com/questions/14677997/stdfunction-vs-template

---

This is not just a peculiarity about C++, it's directly mapping to the mathematics of lambda calculus. From Wikipedia:

> Lambda calculus cannot express this as directly as some other > notations: > all functions are anonymous in lambda calculus, so we can't refer to a > value which is yet to be defined, inside the lambda term defining that > same value. However, recursion can still be achieved by arranging for a > lambda expression to receive itself as its argument value

With C++14, it is now quite easy to make an efficient recursive lambda without having to incur the additional overhead of std::function, in just a few lines of code:

template <class F>
struct y_combinator {
    F f; // the lambda will be stored here
    
    // a forwarding operator():
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        // we pass ourselves to f, then the arguments.
        return f(*this, std::forward<Args>(args)...);
    }
};

// helper function that deduces the type of the lambda:
template <class F>
y_combinator<std::decay_t<F>> make_y_combinator(F&& f) {
    return {std::forward<F>(f)};
}

with which your original sum attempt becomes:

auto sum = make_y_combinator([term,next](auto sum, int a, int b) -> int {
  if (a>b) {
    return 0;
  }
  else {
    return term(a) + sum(next(a),b);
  }
});

---

In C++17, with CTAD, we can add a deduction guide:

template <class F> y_combinator(F) -> y_combinator<F>;

Which obviates the need for the helper function. We can just write y_combinator{[](auto self, ...){...}} directly.

---

In C++20, with CTAD for aggregates, the deduction guide won't be necessary.

---

In C++23, with deducing this, you don't need a Y-combinator at all:

auto sum = [term,next](this auto const& sum, int a, int b) -> int {
  if (a>b) {
    return 0;
  }
  else {
    return term(a) + sum(next(a),b);
  }
}

I have another solution, but work only with stateless lambdas:

void f()
{
	static int (*self)(int) = [](int i)->int { return i>0 ? self(i-1)*i : 1; };
	std::cout<<self(10);
}

Trick here is that lambdas can access static variables and you can convert stateless ones to function pointer.

You can use it with standard lambdas:

void g()
{
	int sum;
	auto rec = [&sum](int i) -> int
	{
		static int (*inner)(int&, int) = [](int& _sum, int i)->int 
		{
			_sum += i;
			return i>0 ? inner(_sum, i-1)*i : 1; 
		};
		return inner(sum, i);
	};
}

Its work in GCC 4.7

To make lambda recursive without using external classes and functions (like std::function or fixed-point combinator) one can use the following construction in C++14 (live example):

#include <utility>
#include <list>
#include <memory>
#include <iostream>

int main()
{
	struct tree
	{
		int payload;
		std::list< tree > children = {}; // std::list of incomplete type is allowed
	};
	std::size_t indent = 0;
	// indication of result type here is essential
	const auto print = [&] (const auto & self, const tree & node) -> void
	{
		std::cout << std::string(indent, ' ') << node.payload << '\n';
		++indent;
		for (const tree & t : node.children) {
			self(self, t);
		}
		--indent;
	};
	print(print, {1, {{2, {{8}}}, {3, {{5, {{7}}}, {6}}}, {4}}});
}

prints:

1
 2
  8
 3
  5
   7
  6
 4

Note, result type of lambda should be specified explicitly.

You can make a lambda function call itself recursively. The only thing you need to do is to is to reference it through a function wrapper so that the compiler knows it's return and argument type (you can't capture a variable -- the lambda itself -- that hasn't been defined yet).

  function<int (int)> f;

  f = [&f](int x) {
    if (x == 0) return 0;
    return x + f(x-1);
  };

  printf("%d\n", f(10));

Be very careful not to run out of the scope of the wrapper f.

I ran a benchmark comparing a recursive function vs a recursive lambda function using the std::function<> capture method. With full optimizations enabled on clang version 4.1, the lambda version ran significantly slower.

#include <iostream>
#include <functional>
#include <chrono>

uint64_t sum1(int n) {
  return (n <= 1) ? 1 : n + sum1(n - 1);
}

std::function<uint64_t(int)> sum2 = [&] (int n) {
  return (n <= 1) ? 1 : n + sum2(n - 1);
};

auto const ITERATIONS = 10000;
auto const DEPTH = 100000;

template <class Func, class Input>
void benchmark(Func&& func, Input&& input) {
  auto t1 = std::chrono::high_resolution_clock::now();
  for (auto i = 0; i != ITERATIONS; ++i) {
    func(input);
  }
  auto t2 = std::chrono::high_resolution_clock::now();
  auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count();
  std::cout << "Duration: " << duration << std::endl;
}

int main() {
  benchmark(sum1, DEPTH);
  benchmark(sum2, DEPTH);
}

Produces results:

Duration: 0 // regular function
Duration: 4027 // lambda function

(Note: I also confirmed with a version that took the inputs from cin, so as to eliminate compile time evaluation)

Clang also produces a compiler warning:

main.cc:10:29: warning: variable 'sum2' is uninitialized when used within its own initialization [-Wuninitialized]

Which is expected, and safe, but should be noted.

It's great to have a solution in our toolbelts, but I think the language will need a better way to handle this case if performance is to be comparable to current methods.

Note:

As a commenter pointed out, it seems latest version of VC++ has found a way to optimize this to the point of equal performance. Maybe we don't need a better way to handle this, after all (except for syntactic sugar).

Also, as some other SO posts have outlined in recent weeks, the performance of std::function<> itself may be the cause of slowdown vs calling function directly, at least when the lambda capture is too large to fit into some library-optimized space std::function uses for small-functors (I guess kinda like the various short string optimizations?).

Here is a refined version of the Y-combinator solution based on one proposed by @Barry.

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }
  
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };

To use this, one could do the following

auto fib = rec([&](auto&& fib, int i) {
// implementation detail omitted.
});

It is similar to the let rec keyword in OCaml, although not the same.

This is a slightly simpler implementation of the fixpoint operator which makes it a little more obvious exactly what's going on.

#include <iostream>
#include <functional>

using namespace std;

template<typename T, typename... Args>
struct fixpoint
{
    typedef function<T(Args...)> effective_type;
    typedef function<T(const effective_type&, Args...)> function_type;

    function_type f_nonr;

    T operator()(Args... args) const
    {
        return f_nonr(*this, args...);
    }

    fixpoint(const function_type& p_f)
        : f_nonr(p_f)
    {
    }
};


int main()
{
    auto fib_nonr = [](const function<int(int)>& f, int n) -> int
    {
        return n < 2 ? n : f(n-1) + f(n-2);
    };

    auto fib = fixpoint<int,int>(fib_nonr);

    for (int i = 0; i < 6; ++i)
    {
        cout << fib(i) << '\n';
    }
}

C++ 14: Here is a recursive anonymous stateless/no capture generic set of lambdas that outputs all numbers from 1, 20

([](auto f, auto n, auto m) {
	f(f, n, m);
})(
	[](auto f, auto n, auto m) -> void
{
	cout << typeid(n).name() << el;
	cout << n << el;
	if (n<m)
		f(f, ++n, m);
},
	1, 20);

If I understand correctly this is using the Y-combinator solution

And here is the sum(n, m) version

auto sum = [](auto n, auto m) {
	return ([](auto f, auto n, auto m) {
		int res = f(f, n, m);
		return res;
	})(
		[](auto f, auto n, auto m) -> int
		{
			if (n > m)
				return 0;
			else {
				int sum = n + f(f, n + 1, m);
				return sum;
			}
		},
		n, m); };

auto result = sum(1, 10); //result == 55

You're trying to capture a variable (sum) you're in the middle of defining. That can't be good.

I don't think truely self-recursive C++0x lambdas are possible. You should be able to capture other lambdas, though.

Here is the final answer for the OP. Anyway, Visual Studio 2010 does not support capturing global variables. And you do not need to capture them because global variable is accessable globally by define. The following answer uses local variable instead.

#include <functional>
#include <iostream>

template<typename T>
struct t2t
{
	typedef T t;
};

template<typename R, typename V1, typename V2>
struct fixpoint
{
	typedef std::function<R (V1, V2)> func_t;
	typedef std::function<func_t (func_t)> tfunc_t;
	typedef std::function<func_t (tfunc_t)> yfunc_t;

	class loopfunc_t {
	public:
		func_t operator()(loopfunc_t v)const {
			return func(v);
		}
		template<typename L>
		loopfunc_t(const L &l):func(l){}
		typedef V1 Parameter1_t;
		typedef V2 Parameter2_t;
	private:
		std::function<func_t (loopfunc_t)> func;
	};
	static yfunc_t fix;
};
template<typename R, typename V1, typename V2>
typename fixpoint<R, V1, V2>::yfunc_t fixpoint<R, V1, V2>::fix = [](tfunc_t f) -> func_t {
	return [f](fixpoint<R, V1, V2>::loopfunc_t x){	return f(x(x)); }
	([f](fixpoint<R, V1, V2>::loopfunc_t x) -> fixpoint<R, V1, V2>::func_t{
		auto &ff = f;
		return [ff, x](t2t<decltype(x)>::t::Parameter1_t v1, 
			t2t<decltype(x)>::t::Parameter1_t v2){
			return ff(x(x))(v1, v2);
		}; 
	});
};

int _tmain(int argc, _TCHAR* argv[])
{
	auto term = [](int a)->int {
	  return a*a;
	};

	auto next = [](int a)->int {
	  return ++a;
	};

	auto sum = fixpoint<int, int, int>::fix(
	[term,next](std::function<int (int, int)> sum1) -> std::function<int (int, int)>{
		auto &term1 = term;
		auto &next1 = next;
		return [term1, next1, sum1](int a, int b)mutable ->int {
			if(a>b)
				return 0;
		else
			return term1(a) + sum1(next1(a),b);
		};
	});

	std::cout<<sum(1,10)<<std::endl; //385

	return 0;
}

This answer is inferior to Yankes' one, but still, here it goes:

using dp_type = void (*)();

using fp_type = void (*)(dp_type, unsigned, unsigned);

fp_type fp = [](dp_type dp, unsigned const a, unsigned const b) {
  ::std::cout << a << ::std::endl;
  return reinterpret_cast<fp_type>(dp)(dp, b, a + b);
};

fp(reinterpret_cast<dp_type>(fp), 0, 1);

You need a fixed point combinator. See this.

or look at the following code:

//As decltype(variable)::member_name is invalid currently, 
//the following template is a workaround.
//Usage: t2t<decltype(variable)>::t::member_name
template<typename T>
struct t2t
{
	typedef T t;
};

template<typename R, typename V>
struct fixpoint
{
	typedef std::function<R (V)> func_t;
	typedef std::function<func_t (func_t)> tfunc_t;
	typedef std::function<func_t (tfunc_t)> yfunc_t;

	class loopfunc_t {
	public:
		func_t operator()(loopfunc_t v)const {
			return func(v);
		}
		template<typename L>
		loopfunc_t(const L &l):func(l){}
		typedef V Parameter_t;
	private:
		std::function<func_t (loopfunc_t)> func;
	};
	static yfunc_t fix;
};
template<typename R, typename V>
typename fixpoint<R, V>::yfunc_t fixpoint<R, V>::fix = 
[](fixpoint<R, V>::tfunc_t f) -> fixpoint<R, V>::func_t {
	fixpoint<R, V>::loopfunc_t l = [f](fixpoint<R, V>::loopfunc_t x) ->
		fixpoint<R, V>::func_t{
			//f cannot be captured since it is not a local variable
			//of this scope. We need a new reference to it.
			auto &ff = f;
			//We need struct t2t because template parameter
			//V is not accessable in this level.
			return [ff, x](t2t<decltype(x)>::t::Parameter_t v){
				return ff(x(x))(v); 
			};
		}; 
		return l(l);
	};

int _tmain(int argc, _TCHAR* argv[])
{
	int v = 0;
	std::function<int (int)> fac = 
	fixpoint<int, int>::fix([](std::function<int (int)> f)
		-> std::function<int (int)>{
		return [f](int i) -> int{
			if(i==0) return 1;
			else return i * f(i-1);
		};
	});

	int i = fac(10);
	std::cout << i; //3628800
	return 0;
}