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: <email@example.com>
- 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; F:=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
f[n_] = (((1+Sqrt)/2)^n - ((1-Sqrt)/2)^n)/Sqrt
This has to be faster than computing it iteratively.
Prev by Date:
Re: Mathematica 3.0, 4.0, 4.1 differences in DSolve
Next by Date:
RE: The value of a partial derivative
Previous by thread:
Re: Re: idiom for recurrence relations
Next by thread: