Optimization for recursive function required

Question

I want to optimize this function so that it can give quick output for input values
(x = 300, y = 120, z = 10).
I thought of storing the values in a 3D array after successive calculation, but was unable to implement that.

Please help. Recursion is too hard to understand!

double P(int x, int y, int z) {

    double final;
    if (x >= 0 && (y <= 0 || z <= 0))
        return  0;

    else if (x <= 0 && (y >= 0 || z >= 0) )
        return 1;

    else {     
        final = 0.1 * (P(x,y-1,z)
                       + P(x-1,y-1,z)
                       +  P(x-2,y-1,z)
                       +  P(x-3,y-1,z)
                       +  P(x-4,y-1,z)
                       +  P(x-5,y-1,z)
                       +  P(x-6,y-1,z)
                       +  P(x-1,y,z)
                       +  P(x-1,y,z)
                       +  P(x,y-1,z-1));
        return final;
    }
}

In order to calculate P (300, 120, 10) the function has to calculate all the possible combinations of x, y, z such that 0 <= x <= 300, 0 <= y <= 120, 0 <= z <= 10. I thought of first creating a 3D array. If the respective arr[x][y][z] is empty I will call the function, otherwise I will just take the value from arr[x][y][z].

Answer 1

You need to build a memoized version of your function. i.e. include a cache:

double P_memoized (int x, int y, int z, double ***cache) {

    if (x >= 0 && (y <= 0 || z <= 0))
        return  0;

    else if (x <= 0 && (y >= 0 || z >= 0) )
        return 1;

    else {
        if (cache[x][y][z] < 0.0) /* Negative => uncached.  */
          cache[x][y][z] = 0.1 * (P_memoized(x,y-1,z, cache)
                                  +  P_memoized(x-1,y-1,z, cache)
                                  +  P_memoized(x-2,y-1,z, cache)
                                  +  P_memoized(x-3,y-1,z, cache)
                                  +  P_memoized(x-4,y-1,z, cache)
                                  +  P_memoized(x-5,y-1,z, cache)
                                  +  P_memoized(x-6,y-1,z, cache)
                                  +  P_memoized(x-1,y,z, cache)
                                  +  P_memoized(x-1,y,z, cache)
                                  +  P_memoized(x,y-1,z-1, cache));
        return cache[x][y][z];
    }
}

But a caller to P_memoized will have to allocate (and later deallocate) the cache. This is an unnecessary headache for the caller, so you wrap the memoized function in a wrapper, and call it P (like you did earlier). The code below does this, but remember it does not check if malloc failed (Read about malloc here):

#include <stdlib.h>
double P(int x, int y, int z) {

    double ***cache, final;
    int i, j, k;

    /* Create a cache.  */
    cache = malloc (sizeof (double **) * (x+1));
    for (i = 0; i <= x; i++)
      {
        cache[i] = malloc (sizeof (double *) * (y+1));
        for (j = 0; j <= y; j++)
          {
            cache[i][j] = malloc (sizeof (double) * (z+1));
            for (k = 0; k <= z; k++)
              cache[i][j][k] = -1.0; /* Negative => uncached.  */
          }
      }

    final = P_memoized (x, y, z, cache);

    /* Delete the cache.  */
    for (i = 0; i < x; i++)
      {
        for (j = 0; j < y; j++)
          free (cache[i][j]);
        free (cache[i]);
      }
    free (cache);
    return final;
}

Then you can just use it as you used to earlier, only this time, its much faster:

#include <stdio.h>
int main (void)
{
  printf ("%f\n", P (10, 5, 3));
  return 0;
}

Fancy caching

If you want to make multiple calls to P, then creating and deleting the cache each time might not be the best idea. Then you should consider doing the following:

1. Make the cache a static variable so that it lives across calls to P
2. Use realloc to dynamically resize the cache when required
3. Don't free the cache at the end of P (because it will be reused)

Why do you need to dynamically resize the cache? Because, say, the first call to P is made with x==10. Then the function will create a cache that has a width of 10. Next time, if P is called with x==20 the old cache is no more wide enough. But the old values contained in it are still useful.

This question and its answer talk about reallocing a 2D array. You should be able to extend this to your 3D version.

Once you do this, you might want to think about a new problem: The cache never gets freed. So it holds on to the memory allocated right until the program exits. Then you might want to have a global cache, instead of a local static one, and provide a separate function to free it in the end.