  If $A$ is a tridiagonal matrix, then the equations $AX=I$ and $XA=I$ defining
the inverse $X$ of $A$ are in fact the second order recurrence relations for
the elements in each row and column of $X$. Thus, the recursive algorithms
should be a natural and commonly used way for inverting tridiagonal matrices --
but they are not. Even though a variety of such algorithms were proposed so
far, none of them can be applied to numerically invert an arbitrary tridiagonal
matrix. Moreover, some of the methods suffer a huge instability problem. In
this paper, we investigate these problems very thoroughly. We locate and
explain the different reasons the recursive algorithms for inverting such
matrices fail to deliver satisfactory (or any) result, and then propose new
formulae for the elements of $X=A^{-1}$ that allow to construct the
asymptotically fastest possible algorithm for computing the inverse of an
arbitrary tridiagonal matrix $A$, for which both residual errors, $\|AX-I\|$
and $\|XA-I\|$, are always very small.
