Re: Differences between recursions and limit

*To*: mathgroup at smc.vnet.net*Subject*: [mg60535] Re: [mg60509] Differences between recursions and limit*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Tue, 20 Sep 2005 05:18:50 -0400 (EDT)*References*: <200509190845.EAA23449@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

On 19 Sep 2005, at 17:45, anbra1 wrote: > Please, > I want to know > why these two recursions,doing the same thing, > are the first one much more slow than the second > > ------------------------- > > x[0]=0; > x[k_] := .25 *(1 + x[k-1] + (x[k-1])^2 + (x[k-1])^3); > > For[k=1,k<12,Print[k," ",SetPrecision[x[k],30]];k++] > > ------------------------- > > a=0; > > For[k=1,k<12,k++, > > b= .25 (1 + a + a^2 + a^3);a:=b;Print[k," ",SetPrecision[b,30]]] Your first code evaluates x[k] recursively every time a step in the For loop is executed; hence the slowness. You can speed up the first code by using dynamic programming: x[0]=0; x[k_] :=x[k]= .25 *(1 + x[k-1] + (x[k-1])^2 + (x[k-1])^3); For[k=1,k<12,Print[k," ",SetPrecision[x[k],30]];k++] > > ------------------------- > Another question > How can I calculate > the limit of this recursion for k->Infinite ? > Thank you all > Using Mathematica you can get the approximate fixed point of the recursion by using FixedPoint: FixedPoint[0.25*(1+#+#^2+#^3)&,0] 0.414214 But it is better to solve it exactly: x /. Solve[x == (1/4)*(1 + x + x^2 + x^3), x] {1, -1 - Sqrt[2], -1 + Sqrt[2]} N[%] {1., -2.414213562373095, 0.41421356237309515} The limit, if it exists (it is easy to show it does) must be one of these roots, and clearly it is the third one. Andrzej Kozlowski

**References**:**Differences between recursions and limit***From:*"anbra1" <xyxanbra1@tiscalixxxyxxx.it>