In this paper, the problem of recursively estimating the state uncertainty set of a discrete-time linear dynamical system is addressed. A novel approach based on minimum-volume bounding parallelotopes is introduced and an algorithm of polynomial complexity is derived. Simulation results and performance comparisons with ellipsoidal recursive state-bounding algorithms are also given.