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
f(n-4)
v = f(n-3)
f(n-2)
f(n-1)
When you multiply M*v you get the vector
f(n-3)
f(n-2)
f(n-1)
f(n)
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.