This doesn't answer the original question, but this is how I like to think of sequences like this one.
Take the matrix
0 1 0 0
M = 0 0 1 0
0 0 0 1
4 3 2 1
and the vector
v = f(n-3)
When you multiply M*v you get the vector
So the indices are pushed by one in this operation. If you want to advance two steps at once, use M^2.
Now, in order to compute f(n), compute M^n, and multiply the result by the first four terms (0 1 2 3). Computing a power of a matrix can be done in O(log(n)) multiplications. You can also make this computation more efficient by realizing that the matrices involved all live in a 4-dimensional linear subspace, and you can define a special type that contains 4 numbers with the appropriate operations (this part is a bit tricky).
This method is not only computationally efficient, but it gives you a much deeper understanding of the situation. For instance, if you want to find an explicit formula for f(n), you just need to diagonalize M.
Edited by Álvaro, 21 January 2013 - 08:55 AM.