       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];
If[m==-1,Return];
(* 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[] += 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

```

• Prev by Date: Re: Recursion problem?
• Next by Date: OS2 Version, Use of Virtual Memory?
• Previous by thread: Re: Recursion problem?
• Next by thread: OS2 Version, Use of Virtual Memory?