The Capon algorithm, which was originally proposed for wavenumber estimation in array signal processing, has become a powerful tool for spectral analysis. Over several decades, a significant amount of research attention has been devoted to the estimation of the Capon spectrum. Most of the developed algorithms thus far, however, rely on the direct computation of the inverse of the input correlation (or covariance) matrix, which can be computationally very expensive particularly when the dimension of the matrix is large. This paper deals with fast and efficient algorithms in computing the Capon spectrum. Inspired from the recursive idea established in adaptive signal processing theory, we first derive a recursive Capon algorithm. This new algorithm does not require an explicit matrix inversion, and hence it is more efficient to implement than the direct-inverse approach. We then develop a fast version of the recursive algorithm based on techniques used in fast recursive least-squares adaptive algorithms. This new fast algorithm can further reduce the complexity of the recursive Capon algorithm by an order of magnitude. Although our focus is on the Capon spectral estimation, the ideas shown in this paper can also be generalized and applied to other applications. To illustrate this, we will show how to apply the recursive idea to the estimation of the magnitude squared coherence function, which plays an important role for problems like time-delay estimation, signal-to-noise ratio estimation, and doubletalk detection in echo cancellation.