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

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