MathGroup Archive 2001

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

Search the Archive

Re: idiom for recurrence relations

  • To: mathgroup at
  • Subject: [mg26725] Re: idiom for recurrence relations
  • From: "Paul Lutus" <nospam at>
  • Date: Fri, 19 Jan 2001 02:14:04 -0500 (EST)
  • References: <9462ss$>
  • Sender: owner-wri-mathgroup at

<maharrix at> wrote in message news:9462ss$gdn at
> 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

  • 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: task