Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1995
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • 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?