Posted by: Zeeshan Amjad | March 12, 2014

Mutual recursion with C++ lambda function


We 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 function recursively, because lambda function doesn’t have any name.

Things are bit interesting in case of mutual recursion. In case of mutual recursion there are more than one functions calls each other. It means that now we need not one but two function pointers stored in C++ wrapper.

Let’s start with our first attempt to create a simple even and odd function.

Here is a simple equation of mutual recursion.

Even_Function_Equation

In first step let’s create two wrappers for function.

Code Snippet
std::function<bool(int)> isEven;
std::function<bool(int)> isOdd;

 

Now lets create a function for this.

Code Snippet
isEven = [&isEven](int n) -> bool
{
    if (0 == n)
        return true;

    else
        return isOdd(n – 1);
};

isOdd = [&isOdd](int n) -> bool
{
    if (0 == n)
        return false;

    else
        return isEven(n – 1);
};

 

And we got the following error message.

error C3493: ‘isOdd’ cannot be implicitly captured because no default capture mode has been specified

error C3493: ‘isEven’ cannot be implicitly captured because no default capture mode has been specified

Now we have to specify the other lambda function in the lambda capture. Here is a modified version of the lambda function which implement mutual recursion.

Code Snippet
std::function<bool(int)> isEven;
std::function<bool(int)> isOdd;

isEven = [&isEven, &isOdd](int n) -> bool
{
    if (0 == n)
        return true;

    else
        return isOdd(n – 1);
};

isOdd = [&isOdd, &isEven](int n) -> bool
{
    if (0 == n)
        return false;

    else
        return isEven(n – 1);
};

 

Let’s see another example of mutual recursion. Here is a mutual recursive function for baby and adult rabbit pair in fibonacci sequence.

Mutual_Recursion

Here is a C++ lambda function of this.

Code Snippet
std::function<int(int no)> babyPair;
std::function<int(int no)> adultPair;

babyPair = [&babyPair, &adultPair](int no) -> int
{
    if (no == 1)
        return 1;
    else
        return adultPair(no – 1);
};

adultPair = [&adultPair, &babyPair](int no) -> int
{
    if (no == 1)
        return 0;
    else
        return adultPair(no – 1) + babyPair(no – 1);
};

Advertisements

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: