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.

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.

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