For statistical inference of means of stationary processes, one needs to estimate their time-average variance constants (TAVC) or long-run variances. For a stationary process, its TAVC is the sum of all its covariances and it is a multiple of the spectral density at zero. The classical TAVC estimate which is based on batched means does not allow recursive updates and the required memory complexity is O(n). We propose a faster algorithm which recursively computes the TAVC, thus having memory complexity of order O(1) and the computational complexity scales linearly in n. Under short-range dependence conditions, we establish moment and almost sure convergence of the recursive TAVC estimate. Convergence rates are also obtained.