Recursive Lambda in C++14

There is the recursive factorial function with std::function.

( ^ω^)

std::function< int( int ) > f;
f = [&]( int a ){ return a <= 0 ? 1 : a * f( a - 1 ); };
f( 5 ); // 120

This is…

( ^ω^)


( ^ω^)

You MUST NOT USE std::function for declare recursive lambda.

( ^ω^)
⊃ .. ⊂

std::functionは理論上、そして事実上速度が良いとは言えない。関数、関数オブジェクト、関数ポインタ、ラムダを統一的に扱うために、少なからずType Erasureが行われる。同時に再代入を許容するため、コンパイル時に呼び出しが解決できず、インライン展開がされることがないなど、様々な最適化が効かない。もちろん速度のネックが気にならない状況ならその程度は構わないが、関数を参照でキャプチャする必要が有るため、必ずしもstd::functionが同じラムダを指しているとは限らないという問題がある

std::function is not good performance in theory and practically a pretty much environment. It’s done type erasure for implementing polymorphism for such as a function, a function object, a function pointer, and a lambda expression. Moreover, it will not be usually optimized calling. It have allowed reassignment, so compiler cannot be resolved function address at the compile time. Consequently, it will not be expanded inline. Although you might think, “No problem. I don’t mind performance!”. Think twice. It have allowed reassignment. Its instance is modifiable. Do you know what contain in variable? Really? In case of std::function, You must not initialize with lambda expression. The lambda expression need capture the variable for recursively. However, if you use itself in initialize expression, behavior is undefined; therefore, we cannot define it const. Maybe this will be produced a bug. It’s unnecessary risk.



What would you do? If I were you, I use Fixed Point Combinator. Most easy answer is following:

template< typename F >
auto recursive( F f )
    return [ f ]( auto... a ) { return f( f, a... ); };

auto f = recursive(
    []( auto f, int a ) -> int {
        return a <= 0 ? 1 : a * f( f, a - 1 ); } );
f( 5 ); // 120


This recursive function is wrapper for it convert to interface like a normal recursive function. The parameter type is function. That function need a first parameter is itself. It get itself by a first argument. If call it, this is recursive function.


Alternatively, you can use currying.

auto f = []( auto f, int a ) -> int { return a <= 0 ? 1 : a * f( f, a - 1 ); };
auto f2 = curry( f )( f );
f2( 5 ); // 120


recursive function can define also be by currying.

template< typename F >
auto recursive( F f )
    return curry( f )( f );




If you mind performance, you should use tail recursion.

auto f = recursive( []( auto f, int a, int r ) -> int { return a <= 0 ? r : f( f, a - 1, r ); } );


If it implemented Perfect Forwarding for recursive function, there is more a very fast possibility than std::function in theory. Whether it will be optimized is implementation dependent, though. At least, It should be more advantageous than std::function because it can optimize by inline-expansion at compile time.

更に余談だが、この場合、戻り値の推論が出来ない(-> intの部分が省略出来ない)。これは条件演算子と推論ルールの問題である。ifステートメントにすれば問題ない。

Incidentally, In this case, it cannot be done auto deduction for return-value. This is conditional operator and auto deduction rule problem. It’s fix by use if statement.

auto f = recursive( []( auto f, int a, int r ){ if( a <= 0 ){ return r; } else { return f( f, a - 1, r ); } } );



P.S. If you want to the same way in C++11, refer the following link.