# Evaluating a Recursive Expression

Why does this raise an error

P[0, x_] := 1

P[1, x_] := x

P[n_, x_] := ((2 n - 1)/n)*x*P[n - 1, x] - ((n - 1)/n)*P[n - 2, x]

Simplify[P[n, x]] /. n -> 2

(*$RecursionLimit::reclim: Recursion depth of 256 exceeded. >>*)  But this does not P[0, x_] := 1 P[1, x_] := x P[n_, x_] := ((2 n - 1)/n)*x*P[n - 1, x] - ((n - 1)/n)*P[n - 2, x] Simplify[P[2, x]] 1/2 (-1 + 3 x^2)  More generally how does one generate a list of 1000 polynomials from this recursion? All of the following still seem to raise errors. Unevaluated@P[n, x] /. n -> {2, 3} Simplify[Unevaluated@P[n, x] /. n -> {2, 3}] Simplify[Unevaluated@P[n, x]] /. n -> {2, 3} {Unevaluated@P[n, x] /. n -> z} /. z -> {2, 3}  If my questions indicate that I am not familiar with mathematica, it is because I am not. :-) - without trying (Mathematica is running something at the moment), probably because in trying to Simplify[P[n, x]] Mathematica enter the infinite recursion (ie, before the replacement occurs) – acl Dec 18 '12 at 22:50 Try Simplify[Unevaluated@P[n, x] /. n -> 2] – Artes Dec 18 '12 at 22:54 Making sure than n is an integer makes it a bit safer. Define the function with P[n_Integer, x] := .... But as acl notes, you still can't simplify before you give it a value. – wxffles Dec 18 '12 at 23:01 So, how does one generate a list of 1000 polynomials from this recursion? I try Simplify[Unevaluated@P[n, x] /. n -> 2] and it works, but Simplify[Unevaluated@P[n, x] /. n -> {2,3}] does not work. More importantly, if I use this recursion in more complicated formulas, I have no way of knowing if there will be success. – Bobby Ocean Dec 18 '12 at 23:30 To produce lots of them, with your definitions, do eg Table[P[n, x], {n, 2, 10}]. As for udnerstanding, given the explanation @ssch gave, you should be able to work out why your attempt didn't work. – acl Dec 19 '12 at 0:04 ## 2 Answers A simpler example where I tell Mathematica to print what it's doing. I ClearAll[n] to make sure n has no value set. ClearAll[n]; f[0] = 0 f[n_] := f[n - 1] Block[{$RecursionLimit = 20, $IterationLimit = 20}, TracePrint[f[n]] ]  See that there is a bunch of f[-10+n] etc, but since n is not assigned any value -10+n is not zero, and neither is -12+n or anything else of the sort. This means that f[0] will never get matched, i.e. it will go on forever, this is a bad thing and you don't want that to happen, for that reason there are global variables $RecursionLimit and $IterationLimit that make sure this doesn't happen. If for some reason you don't want a limit you can set them to Infinity in this case that could crash Mathematica and possibly your computer - what do you want to link to? the docs for $RecursionLimit? –  acl Dec 18 '12 at 23:04
@acl yes, exactly! For some reason the \$ messes it up –  ssch Dec 18 '12 at 23:05
strange, the first time I edited it it worked in the preview but not when I submitted it; now it works in both (and I've done it two ways to see if it made a difference) –  acl Dec 18 '12 at 23:10
@acl Thanks! I had similar problem with preview starting of with the right thing but then suddenly changing as I kept typing. –  ssch Dec 18 '12 at 23:11

The pattern on the right hand side P[n_, x_] matches the new expressions created on the left hand side, namely P[n - 1, x] and P[n - 2, x] leading to infinite recursion when n is a symbol. When you use a concrete value, i.e. n = 2, then it actually uses the end cases, eventually, if the initial n > 0.

Therefore, in the expression Simplify[P[n, x]] /. n -> 2, Mathematica first attempts to resolve P[n, x] through the rules you provide, failing into the issue mentioned above.

The second expression Simplify[P[2, x]] does not have this issue as explained.

To address your intention, you need to use a procedure that holds P[n,x] unevaluated. For example, Table just does that so this works

p[0, x_] := 1;
p[1, x_] := x;
p[n_, x_] := ((2 n - 1)/n) x p[n - 1, x] - ((n - 1)/n) p[n - 2, x];
Table[Simplify[p[n, x]], {n, 10}]


I used lowercase p as it is best practice to use lowercase for user defined symbols, and you don't need the explicit * either. Hope this helps.

-