Recent experiments have demonstrated that plastic strains in nanocrystalline aluminum and gold films with grain sizes on the order of 50 nm are partially recoverable. To reveal the mechanisms behind such strain recovery, we perform large scale molecular dynamics simulations of plastic deformation in nanocrystalline aluminum with mean grain sizes of 10, 20, and 30 nm. Our results indicate that the inhomogeneous deformation in a polycrystalline environment results in significant residual stresses in the nanocrystals. Upon unloading, these internal residual stresses cause strain recovery via competitive deformation mechanisms including dislocation reverse motion/annihilation and grain-boundary sliding/diffusion. By tracking the evolution of each individual deformation mechanism during strain recovery, we quantify the fractional contributions by grain-boundary and dislocation deformation mechanisms to the overall recovered strain. Our analysis shows that, even under strain rates as high as those in molecular dynamics simulations, grain-boundary-mediated processes play important roles in the deformation of nanocrystalline aluminum.