In this paper, we present three order-recursive formulas for the Moore-Penrose pseudoinverses of matrices which are the improved and extended Greville formulas (1960). These new versions not only reduce almost half memory locations of Greville formula at each recursion, but also are very useful to derive recursive formulas for the optimization solutions involving the pseudoinverses of matrices. As applications, using the new formulas, we derive Recursive Least Squares (RLS) procedures which coincide exactly with the batch LS solutions to the problems of unconstrained LS, LS with linear equality constraints, and weighted LS, respectively, including their simple and exact initializations. In comparison with previous results of Albert and Sittler (1965), not only the derivation of the recursive formulas are much easier, but also the formulas themselves are clearer and simpler. In particular, the linear equality constrained RLS can be of the same version of RLS without constraint except the initial values, which has important practical applications.