Convert this recursive function to iterative

Question

How can I convert this recursive function to an iterative function?

#include <cmath>

int M(int H, int T){
    if (H == 0) return T;
    if (H + 1 >= T) return pow(2, T) - 1;
    return M(H - 1, T - 1) + M(H, T - 1) + 1;
}

Well it's a 3-line code but it's very hard for me to convert this to an iterative function. Because it has 2 variables. And I don't know anything about Stacks so I couldn't convert that.

My purpose for doing this is speed of the function. This function is too slow. I wanted to use map to make this faster but I have 3 variables M, H and T so I couldn't use map

Answer 1

you could use dynamic programming - start from the bottom up when H == 0 and T == 0 calculate M and iterate them. here is a link explaining how to do this for Fibonacci numbers, which are quite similar to your problem.

Answer 2

Check this,recursive and not recursive versions gave equal results for all inputs i gave so far. The idea is to keep intermediate results in matrix, where H is row index, T is col index, and the value is M(H,T). By the way, you can calculate it once and later just obtain the result from the matrix, so you will have performance O(1)

int array[10][10]={{0}};

int MNR(int H, int T)
{
    if(array[H][T])
       return array[H][T]; 

    for(int i =0; i<= H;++i)
    {
        for(int j = 0; j<= T;++j)
        {
            if(i == 0)
                array[i][j] = j;

            else if( i+1 > j)
                array[i][j] = pow(2,j) -1;

            else
                array[i][j] = array[i-1][j-1] + array[i][j-1] + 1;

        }
    }

    return array[H][T];
}

int M(int H, int T)
{
    if (H == 0) return T;
    if (H + 1 >= T) return pow(2, T) - 1;
    return M(H - 1, T - 1) + M(H, T - 1) + 1;
}

int main()
{
    printf("%d\n", M(6,3));
    printf("%d\n", MNR(6,3));
}

Answer 3

Unless you know the formula for n-th (in your case, (m,n)-th) element of the sequence, the easiest way is to simulate the recursion using a stack.

The code should look like the following:

#include <cmath>
#include <stack>

struct Data
{
public:
    Data(int newH, int newT)
        : T(newT), H(newH)
    {

    }

    int H;
    int T;
};

int M(int H, int T)
{
    std::stack<Data> st;

    st.push(Data(H, T));

    int sum = 0;

    while (st.size() > 0)
    {
        Data top = st.top();
        st.pop();

        if (top.H == 0) 
            sum += top.T;
        else if (top.H + 1 >= top.T)
            sum += pow(2, top.T) - 1;
        else
        {
            st.push(Data(top.H - 1, top.T - 1));
            st.push(Data(top.H, top.T - 1));
            sum += 1;
        }
    }

    return sum;
}

Answer 4

The main reason why this function is slow is because it has exponential complexity, and it keeps recalculating the same members again and again. One possible cure is memoize pattern (handily explained with examples in C++ here). The idea is to store every result in a structure with a quick access (e.g. an array) and every time you need it again, retrieve already precomputed result. Of course, this approach is limited by the size of your memory, so it won't work for extremely big numbers...

In your case, we could do something like that (keeping the recursion but memoizing the results):

#include <cmath>
#include <map>
#include <utility>

std::map<std::pair<int,int>,int> MM;

int M(int H, int T){
    std::pair<int,int> key = std::make_pair(H,T);
    std::map<std::pair<int,int>,int>::iterator found = MM.find(key);
    if (found!=MM.end()) return found->second; // skip the calculations if we can
    int result = 0;
    if (H == 0) result = T;
    else if (H + 1 >= T) result = pow(2, T) - 1;
    else result = M(H - 1, T - 1) + M(H, T - 1) + 1;
    MM[key] = result;
    return result;
}

Regarding time complexity, C++ maps are tree maps, so searching there is of the order of N*log(N) where N is the size of the map (number of results which have been already computed). There are also hash maps for C++ which are part of the STL but not part of the standard library, as was already mentioned on SO. Hash map promises constant search time (the value of the constant is not specified though :) ), so you might also give them a try.

Answer 5

You may calculate using one demintional array. Little theory,

Let F(a,b) == M(H,T)
1. F(0,b) = b
2. F(a,b) = 2^b - 1, when a+1 >= b
3. F(a,b) = F(a-1,b-1) + F(a,b-1) + 1

Let G(x,y) = F(y,x)  ,then
1. G(x,0) = x                 // RULE (1)
2. G(x,y) = 2^x - 1, when y+1 >= x  // RULE (2) 
3. G(x,y) = G(x-1,y-1) + G(x-1,y) + 1  // RULE(3) --> this is useful, 
// because for G(x,y) need only G(x-1,?), i.e if G - is two deminsions array, then 
// for calculating G[x][?]   need only  previous row G[x-1][?], 
// so we need only last two rows of array.

// Here some values of G(x,y)  
4. G(0,y)  = 2^0 - 1 = 0  from (2) rule.
5. G(1,0)  = 1  from (1) rule.
6. G(1,y) = 2^1 - 1 = 1,  when y > 0,  from (2) rule.

G(0,0) = 0,  G(0,1) = 0,   G(0,2) = 0,  G(0,3) = 0  ...
G(1,0) = 1,  G(1,1) = 1,   G(1,2) = 1,  G(1,3) = 1  ...

7. G(2,0) = 2  from (1) rule
8. G(2,1) = 2^2 - 1 = 3   from (2) rule
9. G(2,y) = 2^2 - 1 = 3 when y > 0,  from (2) rule.

G(2,0) = 2,  G(2,1) = 3,  G(2,2) = 3, G(2,3) = 3, ....

10. G(3,0) = 3  from (1) rule
11. G(3,1) = G(2,0) + G(2,1) + 1 = 2 + 3 + 1 = 6  from (3) rule
12. G(3,2) = 2^3 - 1 = 7,  from (2) rule

Now, how to calculate this G(x,y)

int M(int H, int T ) { return G(T,H); }

int G(int x, int y)
{   
     const int MAX_Y = 100; // or something else
     int arr[2][MAX_Y] = {0} ; 
     int icurr = 0, inext = 1;

     for(int xi = 0; xi < x; ++xi)
     {
          for( int yi = 0; yi <= y ;++yi) 
          {
            if ( yi == 0 )  
                 arr[inext][yi] = xi; // rule (1);
            else if ( yi + 1 >= xi ) 
                 arr[inext][yi] = (1 << xi) - 1; // rule ( 2 )
            else arr[inext][yi] = 
                arr[icurr][yi-1] + arr[icurr][yi] + 1; // rule (3)

          }
          icurr ^= 1; inext ^= 1;          //swap(i1,i2);
     }
     return arr[icurr][y];
}

// Or some optimizing

int G(int x, int y)
{
    const int MAX_Y = 100;
    int arr[2][MAX_Y] = {0};
    int icurr = 0, inext = 1;

    for(int ix = 0; ix < x; ++ix)
    {
        arr[inext][0] = ix; // rule (1)

        for(int iy = 1; iy < ix - 1; ++ iy) 
            arr[inext][iy] = arr[icurr][iy-1] + arr[icurr][iy] + 1; // rule (3)

        for(int iy = max(0,ix-1); iy <= y; ++iy)
            arr[inext][iy] = (1 << ix ) - 1; // rule(2)

        icurr ^= 1 ; inext ^= 1;
    }

     return arr[icurr][y];
}