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

Advertisements

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.
    Leading to negativ factorials.

    kr/Werner

    • Hi

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

      Regards
      Zeeshan Amjad

  3. […] already saw an example of doing recursion with C++ lambda function here. Here we saw that how can we use std::function to store the function pointer to call lambda […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: