||We prove that the sequence of the characters of the Kirillov?Reshetikhin (KR) modules W(a)m , m ∈ ?m≥0 associated to a node a of the Dynkin diagram of a complex simple Lie algebra g satisfies a linear recurrence relation except for some cases in types E7 and E8. To this end we use the Q-system and the existing lattice point summation formula for the decomposition of KR modules, known as domino removal rules when g is of classical type. As an application, we show how to reduce some unproven lattice point summation formulas in exceptional types to finite problems in linear algebra and also give a new proof of them in type G2, which is the only completely proven case when KR modules have an irreducible summand with multiplicity greater than 1. We also apply the recurrence to prove that the function dim W(a)m is a quasipolynomial in m and establish its properties. We conjecture that there exists a rational polytope such that its Ehrhart quasipolynomial in m is dim W(a)m and the lattice points of its m-th dilate carry the same crystal structure as the crystal associated with W(a)m .