Optimizing the computation of a recursive sequence

Question

What is the fastest way in R to compute a recursive sequence defined as

x[1] <- x1 
x[n] <- f(x[n-1])

I am assuming that the vector x of proper length is preallocated. Is there a smarter way than just looping?

Variant: extend this to vectors:

 x[,1] <- x1 
 x[,n] <- f(x[,n-1])

Answer 1

Solve the recurrence relationship ;)

Answer 2

In terms of the question of whether this can be fully "vectorized" in any way, I think the answer is probably "no". The fundamental idea behind array programming is that operations apply to an entire set of values at the same time. Similarly for questions of "embarassingly parallel" computation. In this case, since your recursive algorithm depends on each prior state, there would be no way to gain speed from parallel processing: it must be run serially.

That being said, the usual advice for speeding up your program applies. For instance, do as much of the calculation outside of your recursive function as possible. Sort everything. Predefine your array lengths so they don't have to grow during the looping. Etc. See this question for a similar discussion. There is also a pseudocode example in Tim Hesterberg's article on efficient S-Plus Programming.