Efficient LRS evaluation

Consider a linear recurrence sequence $f : \mathbb N \to \mathbb Q$. Given an input index $n \in \mathbb N$ in binary encoding, decide whether $f(n) = 0$. Can this be done in polynomial time?