Re: Two-Dimensional Recursive JavaScript

<wgarner (AT) ucsd (DOT) edu> wrote

I am trying to implement a two-dimensional recursive formula, g(x,y).
It is sort of like multiplication.

g(x,y) = 0 if either x or y is 0. g(1, y) = y and g(x, 1) = x.

Those are the base cases.

snip


function nim_mult(a,b) {

var g = new Array(a+1);
for(i=0; i<=a;i++) {
g[i] = new Array(b+1);
}
Every time you enter this function it will create the g array and fill it.

And the function is called recursively, so it doesn't meet your objective.
Instead, you want to declare and fill it once. That should thus happen in an
'outer' function. The recursion should than be placed in an inner function.
See later.

for(i=0;i<=a;i++) {
g[i][0] = 0;
if(b>0)
g[i][1] = i;
}
for(j=0;j<=b;j++) {
g[0][j] = 0;
if(a>0)
g[1][j] = j;
}

I'm not sure that it is sensible to fille the elements [0,j] and [i,0]. Will

they ever be accessed ?

if(a=="0" || b=="0") {
return 0;
} else if (a=="1") {
return b;
} else if(b=="1") {
return a;
} else {
NB: why do you compare a and b here to a string, wheras before you compared

them to numbers. The following code will achieve the same:
if (a==0 || b==0) return 0;
if (a==1) return b;
if (b==1) return a;

nim_mult_str="";

for(i=0; i<a; i++) {
for(j=0; j<b; j++) {
nim_mult_str+= "," + nim_mult(i,b) + ",";
}
I don't understand why you loop thru j. Part of the formula is missing ?
}
g[a][b] = h(nim_mult_str);

return g[a][b];
}

I think that your idea of storing results in the 2d array could be
implemented as follows.
function nim_mult(a,b) {
if (a==0 || b==0) return 0;
if (a==1) return b;
if (b==1) return a;
var i,g = []
for (i=0;i<a;i++) {g[i] = []}; // create g and make it available to inner
function
function inner(a,b) {
var i,j,result
if (a==0 || b==0) return 0;
if (a==1) return b;
if (b==1) return a;
result=g[a][b]
if (result) return result;
result="";
for(i=0; i<a; i++) {
for(j=0; j<b; j++) {
result+="," + inner(i,b) + ","+inner(a,j); // ???
}}
g[a][b]=result;
return result
}
return inner(a,b)
}

Tom