# a recursive function using memoization

I have looked at a lot of these cases, e.g. Can one identify the design patterns of Mathematica? and the included ones.

My trimmed example, here establishing the 'initial conditions' (where the zp___List symbol has 3 underscores) and utilizes only 2 external global functions, B and K;

wgn[0,0,zp___List]:=0;
wgn[0,1,zp___List]:=0;
wgn[0,2,zp___List]:=B;
wgn[g_Integer/;g<0,npo_Integer,zp___List]:=0;
wgn[g_Integer,npo_Integer/;npo<0,zp___List]:=0;


and then the recursion (I changed a double sum to a Sum @@ Flatten[Table[);

wgn[g_Integer /; g >= 0, npo_Integer?Positive, zp___List] :=
wgn[g, npo, zp] =
(
Sum[
(
Module[{z, tmp1, tmp1b, tmp2, asso, T1},

tmp1 = Rest[Drop[zp, -Length[zp]/2]];

tmp1b = Rest[Drop[zp, Length[zp]/2]];

tmp2 = Subsets[tmp1, {0, npo - 1}];

T1 = Table[{tmp2[[o]], Complement[tmp1, tmp2[[o]]]}, {o, 1,
Length[tmp2]}];

(
wgn[g - 1, npo + 1, Flatten[List[Join[
{z, -z},
Rest[Drop[zp, -Length[zp]/2]],
{j, j},
Rest[Drop[zp, Length[zp]/2]]]
]]]

+

Total[Flatten[Table[

wgn[h, 1 + Length[T1[[wc]][[1]]],
Flatten[
List[Join[{z}, T1[[wc]][[1]], {j},
asso /@ T1[[wc]][[1]]]]]]
*

wgn[g - h, 1 + Length[T1[[wc]][[2]]],
Flatten[
List[Join[{-z}, T1[[wc]][[2]], {j},
asso /@ T1[[wc]][[2]]]]]]
, {h, 0, g}, {wc, 1, Length[T1]}]]]

)
, {z, 0}]
]
)
, {j, 1, 1}]
);


tmp1 & tmp1b split the 3rd argument into variables and numbers and there is an association - asso - between them. So the 2nd variable and 2nd number are correlated. tmp2 calculates all the Subsets of $$z_1,\ldots,z_n$$ and then T1 constructs pairs where one element of tmp2 at a time is paired with its set-complement, i.e. to make $$A \cup B = \{1,\ldots,n\}$$, and then summed over in the double sum.

I call it like,

wgn[2,1,{z01,1}]


and for this case expect

wgn[1,2,{z,-z} + w[0,1,{z,j}]*w[2,1,{-z,j}] + w[1,1,{z,j}]*w[1,1,{-z,j}] + w[2,1,{z,j}]*w[0,1,{-z,j}]


where j would be 1 by the double sum... I mean the Sum @@ Flatten[Table[.... Then the 2 'initial conditions' would fill in the rest, giving (after killing the w[0,1,{...}] terms,

wgn[1,2,{z,-z} + w[1,1,{z,j}]*w[1,1,{-z,j}]


Then the recursion would start again, and the w[1,1,{z01,1}] terms would be replaced by,

~ Res[K*w[0,2,{z,-z,j,j}],{z\$2,0}]


and the wgn[1,2,{z,-z}] term replaced by some other terms.

Problem now is that I have the recursion limit problem but can't figure out why, especially since my initial conditions should take care of any runaway negative valued terms.

(One thing, the 2nd variable, npo is half the length of the list zp.)

Here is the formula if it is at all needed,

$$w_{g,n+1}^{i_0,i_1,\ldots,i_n}(z_0,z_1,\ldots,z_n) \sim \sum_{j=1}^N Res_{z->0} K * \left( w_{g-1,n+2}^{j,j,i_1,\ldots,i_n}(z,-z,z_1,\ldots,z_n) + \sum_{A\cup B=\{1,\ldots,n\}} \sum_{h=0}^g w_{h,1+|A|}^{j,\vec{i_A}}(z,\vec{z_A}) * w_{g-h,1+|B|}^{j,\vec{i_B}}(-z,\vec{z_B}) \right)$$

I define npo := n+1. The function Res is just residue but returning zero isn't too helpful ;)

• It doesn't look like you're handling wnnng[0, 0, ___]. Not sure if you need that, just thought it was pertinent. – b3m2a1 Feb 20 '19 at 1:31
• My guess is this is never bottoming out: wgn[h, 1 + Length[T1[[wc]][[1]]] ...] – b3m2a1 Feb 20 '19 at 1:35
• hhmmm... I added the w[0,0,{...}] but it didn't help. I also assume my function definition, , would at least return an answer with an unevaluated wgn[0,0,{...}] because of npo_Integer /; npo > 0 That term you show... it will quit recursion if it is w[0,1,{}] or w[0,2,{..}] – nate Feb 20 '19 at 1:36
• Also I think by constructing a MWE from this you'd find the error. Try making this the most minimal code you can that still causes the issue. – b3m2a1 Feb 20 '19 at 1:36
• Also instead of Sum@@ you want Total. By Sum@@ you meant Plus@@ which is just Total. – b3m2a1 Feb 20 '19 at 1:39

Here's a more minimal example that shows the error:

tooLong // Clear
tooLong[0, 1, zp___List] := 0;
tooLong[0, 2, zp___List] := 0;
tooLong[g_Integer?(# < 0 &), npo_Integer, zp___List] := 0;
tooLong[g_Integer, npo_Integer?(# < 0 &), zp___List] := 0;
tooLong[g_Integer?(# >= 0 &), npo_Integer?Positive, zp___List] :=

tooLong[g, npo, zp] =
tooLong[g - 1, npo + 1, {}] +
Total@
Flatten[
Table[
tooLong[h, 1]*
tooLong[g - h, 1],
{h, 0, g}
]
]


From here it's clear the issue is the line tooLong[g - h, 1]. That will never bottom out since g-h will always be greater than 0 and 1 will never be less than or equal to 0.

You need to handle that case too.

• Aahhhh I wasn't sure what you meant by getting rid of zp with {}.... I'll have to digest your amazingly succinct result.... – nate Feb 20 '19 at 1:56
• @nate the big thing is that Length will never be non-zero and you’ll always have at least one Subset if you allow the empty set. – b3m2a1 Feb 20 '19 at 1:58
• Yes, I notice that even if tmp and tmp1b are empty, the length of T1 is still 1. I've tried playing around with the 2nd argument of Subsets[] but it is tricky for me. – nate Feb 20 '19 at 2:02
• actually.... if the Table[tooLong[h,1]*tooLong[g-h,1],{h,0,g}] runs from h=0 to h=g, how can it not be zero? – nate Feb 20 '19 at 2:06
• If g is non zero you recurse infinitely. g-0==g. – b3m2a1 Feb 20 '19 at 2:06