The SRBs from Shuttle launches were indeed reused... after a fashion. Each booster was four segments. After each flight and recovery, the boosters were disassembled and the segments renovated and reloaded. The segments were not kept together as a set, so each SRB used in a launch would have four segments each with their own history. (This was expressly noted on NASA TV during each launch, with comments about the oldest and newest segments on the flight and so on.)
As for SpaceX, early Falcon 9 flights had parachutes on the first stage, but the stages did not survive reentry (much less make it all the way to landing). Since you can not land anything large on Mars with parachutes, SpaceX would have eventually had to work on hypersonic retropropulsion, propulsive landings, and so on; they merely pivoted away from the parachute "dead end" and went straight to propulsive recovery with Falcon 9 v1.1.