c - Optimization for recursive function required -

i want optimize function can give quick output input values
(x = 300, y = 120, z = 10).
thought of storing values in 3d array after successive calculation, unable implement that.

please help. recursion hard 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 calculate p (300, 120, 10) function has calculate possible combinations of x, y, z such 0 <= x <= 300, 0 <= y <= 120, 0 <= z <= 10. thought of first creating 3d array. if respective arr[x][y][z] empty call function, otherwise take value arr[x][y][z].

you need build memoized version of function. i.e. include 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 caller p_memoized have allocate (and later deallocate) cache. unnecessary headache caller, wrap memoized function in wrapper, , call p (like did earlier). code below this, remember not check if malloc failed (read malloc here):

#include <stdlib.h> double p(int x, int y, int z) {      double ***cache, final;     int i, j, k;      /* create cache.  */     cache = malloc (sizeof (double **) * (x+1));     (i = 0; <= x; i++)       {         cache[i] = malloc (sizeof (double *) * (y+1));         (j = 0; j <= y; j++)           {             cache[i][j] = malloc (sizeof (double) * (z+1));             (k = 0; k <= z; k++)               cache[i][j][k] = -1.0; /* negative => uncached.  */           }       }      final = p_memoized (x, y, z, cache);      /* delete cache.  */     (i = 0; < x; i++)       {         (j = 0; j < y; j++)           free (cache[i][j]);         free (cache[i]);       }     free (cache);     return final; } 

then can use used earlier, time, faster:

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

fancy caching

if want make multiple calls p, creating , deleting cache each time might not best idea. should consider doing following:

1. make cache a static variable lives across calls p
2. use realloc dynamically resize cache when required
3. don't free cache @ end of p (because reused)

why need dynamically resize cache? because, say, first call p made x==10. function create cache has width of 10. next time, if p called x==20 old cache no more wide enough. old values contained in still useful.

this question , answer talk reallocing 2d array. should able extend 3d version.

once this, might want think new problem: cache never gets freed. holds on memory allocated right until program exits. might want have global cache, instead of local static one, , provide separate function free in end.