idiom for recurrence relations

*To*: mathgroup at smc.vnet.net*Subject*: [mg26714] idiom for recurrence relations*From*: maharrix at my-deja.com*Date*: Thu, 18 Jan 2001 00:57:18 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

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 (e.g. 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, Mitch Sent via Deja.com http://www.deja.com/

**Follow-Ups**:**Re: idiom for recurrence relations***From:*Daniel Lichtblau <danl@wolfram.com>