Hydrogen formation is a key process for the physics and the chemistry of interstellar clouds. Molecular hydrogen is believed to form on the carbonaceous surface of dust grains, and several mechanisms have been invoked to explain its abundance in different regions of space, from cold interstellar clouds to warm photon-dominated regions. Here, we investigate direct (Eley-Rideal) recombination including lattice dynamics, surface corrugation, and competing H-dimers formation by means of ab initio molecular dynamics. We find that Eley-Rideal reaction dominates at energies relevant for the interstellar medium and alone may explain observations if the possibility of facile sticking at special sites (edges, point defects, etc.) on the surface of the dust grains is taken into account.