This work studies the recursive robust principal components analysis (PCA) problem. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, $S_t$, in the presence of large but structured noise, $L_t$. The structure that we assume on $L_t$ is that $L_t$ is dense and lies in a low dimensional subspace that is either fixed or changes "slowly enough". A key application where this problem occurs is in video surveillance where the goal is to separate a slowly changing background ($L_t$) from moving foreground objects ($S_t$) on-the-fly. To solve the above problem, in recent work, we introduced a novel solution called Recursive Projected CS (ReProCS). In this work we develop a simple modification of the original ReProCS idea and analyze it. This modification assumes knowledge of a subspace change model on the $L_t$'s. Under mild assumptions and a denseness assumption on the unestimated part of the subspace of $L_t$ at various times, we show that, with high probability (w.h.p.), the proposed approach can exactly recover the support set of $S_t$ at all times; and the reconstruction errors of both $S_t$ and $L_t$ are upper bounded by a time-invariant and small value. In simulation experiments, we observe that the last assumption holds as long as there is some support change of $S_t$ every few frames.