Steps taken from from this StackOverflow answer by Lloeki

• Download the Lion Recovery Update v1.0 from Apple or recoveryhdupdate-apple-osxlion.dmg
• Mount it:
  hdiutil attach ~/Downloads/RecoveryHDUpdate.dmg
• Extract its contents:
  pkgutil --expand /Volumes/Mac\ OS\ X\ Lion\ Recovery\ HD\ Update/RecoveryHDUpdate.pkg ~/Desktop/RHD
• Mount a package contained within:
  hdiutil attach ~/Desktop/RHD/RecoveryHDUpdate.pkg/RecoveryHDMeta.dmg
• 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