Code optimization of recursive function

Question

I am having a recursive function in C as shown below :

float U(int k, int h)
{
    h --;
    int r, s;
    float sum1 = 0, sum2 = 0;

    if (h == -1)
    {
        return (float) ((pow(-1, k)) / factorial(k));
    }

    else
    {
        for (r = 0; r <= k; r++)
        {
            for (s = 0; s <= h; s++)
            {
                sum1 += (r + 1) * (k - r + 1) * U(r + 1, h - s) * U(k - r + 1, s);
            }
        }
        for (r = 0; r <= k; r++)
        {
            for (s = 0; s <= h; s++)
            {
                sum2 += (k - r + 1) * (k - r + 2) * U(r, h - s) * U(k - r + 2, s);
            }
        }
        return (float) ((sum1 + sum2) / (h + 1));
    }
}

I wish to optimize the code as the function takes a lot of time to calculate even not-so-large values like U(10,13). Please give some suggestions along with code snippets(if possible).

pow used this way is really wasteful, use something like sign instead — simonzack
– simonzack, Commented Nov 24, 2015 at 10:55
pow(-1, evenNumber) = 1, and pow(-1, oddNumber) = -1 (I'm considering these numbers as int as they are in your code), so you can remove the pow() call... you can use a two-dimensional array to save the calculated values (u,k)... as Paul said, read about Memoization... you can also memoize factorial(k). — Paulo
– Paulo, Commented Nov 24, 2015 at 11:00
I'm voting to close this question as off-topic because SO is no code-review site. — too honest for this site
– too honest for this site, Commented Nov 24, 2015 at 11:02

jbsu32 · Accepted Answer · 2015-11-25 17:48:22Z

1

you can memorize the values in an array called arr. use better indentation as your code should be easily understandable. memset the array arr with -1 before running the recursion. the code should look like this -

float arr[100][100];

float U(int k,int h)
{    
    h=h-1;
    int r,s;
    //float sum=0,sum1=0,sum2=0;

    if(h==-1)
    {
        float O_O = (float)(k%2!=0 ? -1:1);
        for(int _w=1; _w<=k; _w++)
            O_O/=(float)_w;
        return O_O;
    }

    if(arr[k][h]<-0.5)return arr[k][h];
    arr[k][h]=0;

    for(r=0;r<=k;r++)
    {
        for(s=0;s<=h;s++)
        {
            arr[k][h]+=(r+1)*(k-r+1)*U(r+1,h-s)*U(k-r+1,s);         
        }       
    }

    for(r=0;r<=k;r++)
    {
        for(s=0;s<=h;s++)
        {
            arr[k][h]+=(k-r+1)*(k-r+2)*U(r,h-s)*U(k-r+2,s);
        }
    }

    return (float)(arr[k][h]/(h+1));
}

edited Nov 25, 2015 at 17:48

answered Nov 24, 2015 at 11:04

jbsu32

1,0581 gold badge11 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Paulo Over a year ago

I even sugest changing pow(-1, k) to (k < 0 ? -1 : 1) as k is an integer value. The resulting code would be: return (float) (k < 0 ? -1 : 1)/factorial(k);

jbsu32 Over a year ago

yes showed an easier way. but i think its better to write (k%2!=0 ? -1:1). @Paulo

Paulo Over a year ago

OMG. I didn't mean k < 0. Hehehe. I meant k%2 != 0 as you said.

jit thakore Over a year ago

Thanks @JishnuBanerjee. The code is running much more efficiently. But the output of U(k,h) for k>=13 and h>=11 is -1.#INF00 or +1.#INF00. i tried using double instead of float as well but there is no big difference.

jbsu32 Over a year ago

because factorial(k) overflows! handle it :) @jitthakore

|

Collectives™ on Stack Overflow

Code optimization of recursive function

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related