Optimization required for recursive function

Question

I want to optimize this function so that it can provide quick output for input values
(x = 300, y = 120, z = 10).
I was thinking about storing values ​​in a three-dimensional array after successive calculations, but could not implement this.

Please, help. Recursion is too complicated 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; } } 

To calculate P (300, 120, 10) , the function must calculate all possible combinations of x, y, z such that 0 <= x <= 300 , 0 <= y <= 120 , 0 <= z <= 10 . I was thinking about creating a 3D array. If the corresponding 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 create a memoized version of your function. those. enable 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 the caller of P_memoized will have to allocate (and later free) the cache . This is an unnecessary headache for the caller, so you end the memoized function in the wrapper and call it P (as you did before). The code below does this, but remember that it does not check if malloc fails (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 before, only this time, much faster:

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

Unusual caching

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

• Make a static variable cache so that it moves calls to P
• Use realloc to dynamically change the cache if necessary
• Not a free 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 made using x==10 . Then the function will create a cache that is 10 wide. Next time, if P is called with x==20 , the old cache is not wide enough. But the old meanings contained in it are still useful.

This question and its answer talk about realloc about a two-dimensional array. You should be able to extend this to your 3D version.

Once you do this, you may need to think about a new problem: the cache never gets free d. Thus, it is held in allocated memory until the program exits. Then you might want to have a global cache, not a local static one, and provide a separate free function at the end.