Posted by: Zeeshan Amjad | September 22, 2011

## C++ Recursive Lambda functions

I used lambda expression a lot in C#, but never tried it in C++. Lambda is a part of new C++ standard, i.e. C++11. Today I tried to give a try of lambda in C++ and play with it little bit. I used Microsoft Visual C++ 2010 which has a lambda support. To make things even more interesting, I tried to do recursion with lambda function. I already wrote “Recursion Primer using C++” series here, here and here, so getting examples is not a difficult part.

By definition lambda method doesn’t have any name and we need a function name to call it recursively. These are very opposite concepts. But to overcome this situation we can use the function pointer to store the lambda expression and call function recursively using function pointer. C++ TR1 introduced a wrapper class named function “std::tr1::function” define in functional class. Let’s start with our simple and typical factorial program. Here is lambda recursive version of factorial function.

Code Snippet
// factorial
std::function<int(int)> factorial;

factorial = [&factorial](int n) -> int
{
if (n < 1)
return -1;
else if (0 == n)
return 1;
else
return n * factorial(n – 1);
};

We can even call the recursive function twice. Here is an example of binary recursion.

Code Snippet
// fibonacci
std::function<int(int)> fibonacci;

fibonacci = [&fibonacci](int no) -> int
{
if (no < 1)
return -1;
else if (1 == no || 2 == no)
return 1;
else
return fibonacci(no – 1) + fibonacci(no – 2);

};

Calling nested function is also very similar. Here is an example of nested recursion.

Code Snippet
// ackermann
std::function<int(int m, int n)> ackermann;

ackermann = [&ackermann](int m, int n) -> int
{
// error condition
if (m < 0 || n < 0)
return -1;

// termination condition
if (0 == m)
return n + 1;

// linear recursive call
else if (m > 0 && 0 == n)
return ackermann(m – 1, n);

// nested recursive call
else
return ackermann(m – 1, ackermann(m, n – 1));
};

In a same way if we want to pass more than one parameter to the recursive function we can do it easily. Here is a recursive function to reverse the number.

Code Snippet
// reverse number
std::function<int(int no, int r)> reverseNumber;

reverseNumber = [&reverseNumber](int no, int r) -> int
{
if (0 == no)
return r;
else
return reverseNumber(no / 10, (r * 10) + (no % 10));
};

## Responses

1. […] number in the list box. We already saw one example of calling lambda function recursively in C++ here. Now we are going to do something similar in C#. The C# syntax is very similar to C++ one the only […]

2. Hi,

nice, but there is a typo in your factorial function,
if n<1 the following else would not be reached.

kr/Werner

• Hi

Thanks to like it and thanks to point out my mistake.

Regards