A nearly linear recurrence sequence (nlrs) is a complex sequence (an) with the property that there exist complex numbers A0,...., Ad-1 such that the sequence is bounded. We give an asymptotic Binet-type formula for such sequences. We compare (an) with a natural linear recurrence sequence (lrs) (ãn) associated with it and prove under certain assumptions that the difference sequence (an - ãn) tends to infinity. We show that several finiteness results for lrs, in particular the Skolem-Mahler-Lech theorem and results on common terms of two lrs, are not valid anymore for nlrs with integer terms. Our main tool in these investigations is an observation that lrs with transcendental terms may have large fluctuations, quite different from lrs with algebraic terms. On the other hand, we show under certain hypotheses that though there may be infinitely many of them, the common terms of two nlrs are very sparse. The proof of this result combines our Binet-type formula with a Baker type estimate for logarithmic forms.