Recursion problem?
- To: mathgroup at christensen.cybernetics.net
- Subject: [mg1566] Recursion problem?
- From: bruck at mtha.usc.edu (Ronald Bruck)
- Date: Sat, 24 Jun 1995 06:49:29 -0400
- Organization: University of Southern California, Los Angeles, CA
Can anyone tell me what in the world Mathematica is doing with the following
program? This is a procedure "weight[m,n,a]" which starts with integers
-1 <= m <= n, and a positive real number "a", and calls itself recursively.
The problem is, on FIRST invocation for a given pair (m,n), it often gives the
wrong answer; on a SECOND invocation, for the same (m,n), it gives a
DIFFERENT VALUE, which I presume is correct, since it's stable under iteration
(and it agrees with the few values I've computed other ways).
Is there something special about 2-D recursion? I've asked it to remember
prior values (otherwise the thing would be horribly slow); must I give that up?
WHY DOESN'T THIS WORK?
The program:
Clear[t, x, z, weight];
x[m_] := x[m] = If[m <= 0,1,Expand[t*z^m + (1-t)*x[m-1]]];
weight[m_, n_, a_] := weight[p, q, a] =
Block[{p = -1, q = n-1, mysum=0},
If[m>n, Print["Null"]; Return[Null]];
If[m==n, Return[0]];
If[m==-1,Return[1]];
(* The interesting case: *)
l = CoefficientList[x[m]-x[n],z];
While [ Length[l] > 2,
If[ ((First[l] + Last[l])/.{t->a}) > 0,
(* Knock off right coefficient *)
mysum -= Last[l]*weight[p,q,a];
q -= 1;
l[[1]] += Last[l];
l = Drop[l,-1],
(* else knock off left coefficient *)
mysum += First[l] * weight[p,q,a];
p += 1;
l[[Length[l]]] += First[l];
l = Drop[l,1]
]; (* End IF *)
]; (* End WHILE *)
mysum -= First[l] * weight[p,q,a];
Return[Expand[mysum]]
] (* End BLOCK *)
Now try the following:
a1 = Table[Table[weight[m,n,1/2],{m,-1,n-1}],{n,1,3}];
a2 = Table[Table[weight[m,n,1/2],{m,-1,n-1}],{n,1,3}];
a3 = Table[Table[weight[m,n,1/2],{m,-1,n-1}],{n,1,3}];
a1-a2
The response is:
2 3
{{0, 0}, {0, 0, 0}, {0, 0, -t + t , 0}}
(?!!!)
When I try a2-a3:
{{0, 0}, {0, 0, 0}, {0, 0, 0, 0}}
Can someone explain what I'm doing wrong? Or is this a genuine
bug?
--Ron Bruck