MathGroup Archive 2001

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

Search the Archive

idiom for recurrence relations

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 would be to implement it as an imperative program
keeping only the necessary values to compute the next in the sequence

  While[i<=n,temp=f2; f2=f2+f1; f1=temp;i++]

). Again, great, but  the Mathematica docs repeatedly say that list operations
are much faster than imperative ones.

So my solution is to use Nest:

F[n_] := First@Nest[{#[[2]], #[[2]]+#[[1]]} &, {0, 1}, n]];

Is this the best (fastest, simplest, most appropriate, or most memory
efficient, etc.) way to do it? It seems somehow ugly (too many [[, #,
etc.) but it is shorter in number of characters to encode it (not what I
would usually consider highest on my list of things to optimize (but
that's not to say terribly low either))

The whole point is to be able to create recurrence relations easily in a
single function efficiently. I'd also like to create them as lambdda
functions (as above, as Function[pair, {pair[[2]],pair[[2]]+pair[[1]]}]

So, how do the above rate and what are the reasonable alternatives?

Thanks for any help,

Sent via

  • Prev by Date: Re: subprogramas as separate notebooks
  • Next by Date: Re: Q: How change font in legend?
  • Previous by thread: Strange MathLink program behavior??
  • Next by thread: Re: idiom for recurrence relations