Steps taken from from this StackOverflow answer by Lloeki

—

1. Download the Lion Recovery Update v1.0 from Apple or recoveryhdupdate-apple-osxlion.dmg
2. Mount it:
   ```hdiutil attach ~/Downloads/RecoveryHDUpdate.dmg```
3. Extract its contents:
   ``` pkgutil –expand /Volumes/Mac\ OS\ X\ Lion\ Recovery\ HD\ Update/RecoveryHDUpdate.pkg ~/Desktop/RHD```
4. Mount a package contained within:
   ```hdiutil attach ~/Desktop/RHD/RecoveryHDUpdate.pkg/RecoveryHDMeta.dmg```
5. Run that package to recreate the recovery partition:
   ```~/Desktop/RHD/RecoveryHDUpdate.pkg/Scripts/Tools/dmtest ensureRecoveryPartition / /Volumes/Recovery\ HD\ Update/BaseSystem.dmg 0 0 /Volumes/Recovery\ HD\ Update/BaseSystem.chunklist```