Any Hodge integral involving at-most one lambda class is expressed as a polynomial in terms of lower dimensional Hodge integrals with at-most one lambda class. This follows from more general recursion relations between Hodge integrals with one lambda class. The proof is based on virtual localization formula applied to the moduli space of relative stable morphisms with marked points. This gives an algorithm to compute all Hodge integrals with up-to one lambda class of given dimension in terms of lower dimensional ones.