The recursion method provides a beautiful theoretical framework realizing O(N) electronic structure calculations . We have extented the recursion method for large-scale tight-binding (TB) molecular dynamics simulations within an orthogonal TB model by introducing the block Lanczos algorithm [2,3]. The block scheme handles automatically the very different character of σ and π bonds by introducing block elements, which produces rapid convergence of the energies and forces within insulators, semiconductors, metals, and molecules. The method gives the first convergent results for vacancies in semiconductors using a moments-based method with a low number of moments. Our use of the Lanczos basis simplifies the calculations of the band energy and forces, which allows the application of the method to the molecular dynamics simulations of large systems. We have further extended the recursion method for O(N) ab initio tight-binding calculations based on the density functional theory (DFT) . A long-standing problem of generalizing the recursion method to a non-orthogonal basis, which is a crucial step to make the recursion method applicable to ab initio calculations, is solved by the introduction of hybrid representation and a two-sided block Lanczos algorithm. As a test of efficiency of the proposed method, convergence properties in energy and force of insulators, semiconductors, metals, and molecules are studied for not only simple model systems but also some real materials within DFT. The present O(N) method possesses good convergence properties for metals as well as insulators. In addition, we have presented an O(N) algorithm based on a recursion method for calculating the inverse of an overlap matrix which is needed in electronic structure calculations with the nonorthogonal localized basis set . This efficient inverting method can be incorporated in several O(N) methods for the diagonalization of a generalized secular equation. The research was conducted in collaboration with Gifu University and the University of Oxford.