Red blood cells undergo substantial shape changes in vivo. Modeled as a viscoelastic capsule, their deformation and equilibrium behavior has been extensively studied. We consider how 2D capsules recover their shape, after having been deformed to 'equilibrium' behavior by shear flow. The fluid-structure interaction is modeled using the multiple-relaxation time lattice Boltzmann (LBM) and immersed boundary (IBM) methods. Characterizing the capsule's shape recovery with the Taylor deformation parameter, we find that a single exponential decay model suffices to describe the recovery of a circular capsule. However, for biconcave capsules whose equilibrium behaviors are tank-treading and tumbling, we posit a two-part recovery, modeled with a pair of exponential decay functions. We consider how these two recovery modes depend on the capsule's shear elasticity, membrane viscosity, and bending stiffness, along with the ratio of the viscosity of the fluid inside the capsule to the ambient fluid viscosity. We find that the initial recovery mode for a tank-treading biconcave capsule is dominated by shear elasticity and membrane viscosity. On the other hand, the latter recovery mode for both tumbling and tank-treading capsules, depends clearly on shear elasticity, bending stiffness, and the viscosity ratio.