Re: idiom for recurrence relations
- To: mathgroup at smc.vnet.net
- Subject: [mg26725] Re: idiom for recurrence relations
- From: "Paul Lutus" <nospam at nosite.com>
- Date: Fri, 19 Jan 2001 02:14:04 -0500 (EST)
- References: <9462ss$gdn@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
<maharrix at my-deja.com> wrote in message news:9462ss$gdn at smc.vnet.net... > I have a problem which is mostly esthetic, but could have efficiency > repercussions. First, the general question: What is the best way to > implement recurrence relations (e.g. Fibonacci[n])? > > The obvious and simplest way is to define base cases and an inductive > case (I'll use Fibonnaci as the generic example: > > F[0]:=0; F[1]:=1; F[n_]:=F[n-1]+F[n-2] > > ). This can be sped up using memoization F[n_]:=F[n]=... Great, but this > fills up internal memory (nothing can get garbage collected since all > the computed values must hang around forever; this can be bad when you > have lots of recurrence relations, graphics and a long session). > > So the next solution ... Well, I know this is not what you are after, but here is a closed-form Fibonacci equation: f[n_] = (((1+Sqrt[5])/2)^n - ((1-Sqrt[5])/2)^n)/Sqrt[5] This has to be faster than computing it iteratively. -- Paul Lutus www.arachnoid.com