This applies to OS X Sierra also. Every time I update the OS the recovery partition is left untouched, or at least it appears to be. Long time ago, I searched for a solution and found this post which solved this problem. Read the first post in this thread, written by 'tywebb13'.
This instruction involves downloading Lion Recovery Update 1.0, and a shell script (you can create your own with the contents copy-pasted from below), and also an image of the latest OS X (in my case OS X Sierra 10.12.2) and copying a file from that downloaded image. Keep everything in ~/Downloads folder.
Detailed instruction quoted from the source with minor edits from myself: (the script file in Step 2 is also copy and pasted below this quote for completeness)
Download the Lion Recovery Update from http://support.apple.com/kb/dl1464 . (And before you ask, YES. I mean
LION recovery update!) Make sure it is in your downloads folder.
Download the OS X Sierra or whatever latest version from AppStore.
In Finder, go to Applications and look for the Sierra installation app.
Right click on "Install Sierra.app" or whatever it's called in Finder,
go to Contents/SharedSupport/
Copy or move the InstallESD.dmg file into your ~/Downloads folder.
Download and decompress the file recovery.sh.zip from LINK 4unitmaths.com/recovery.sh.zip and move recovery.sh into your
Downloads folder. This file can also be created by copy-paste
from below source.
Open Terminal and type the following two commands:
chmod +x ~/Downloads/recovery.sh
Wait a few minutes for it to finish and return back to a prompt. Reboot with holding down the option key to test your 10.xx.x recovery
This is the content of recovery.sh file from the source link (all credit to 'tywebb13' again):
read -p "Ensure "RecoveryHDUpdate.dmg" and "InstallESD.dmg" are in your Downloads folder and press [Enter]"
#access dmtest from RecoveryHDUpdate.pkg
rm -rf /private/tmp/RecoveryHDUpdate
echo "Expanding RecoveryHDUpdate.pkg"
hdiutil attach -nobrowse ~/Downloads/RecoveryHDUpdate.dmg
pkgutil --expand /Volumes/Mac\ OS\ X\ Lion\ Recovery\ HD\ Update/RecoveryHDUpdate.pkg /tmp/RecoveryHDUpdate
#access BaseSystem.dmg and BaseSystem.chunklist
echo "Expanding InstallESD.dmg"
hdiutil attach -nobrowse ~/Downloads/InstallESD.dmg
#build Recovery partition
echo "Building Recovery Partition. Please Wait"
/tmp/RecoveryHDUpdate/RecoveryHDUpdate.pkg/Scripts/Tools/dmtest ensureRecoveryPartition / /Volumes/OS\ X\ Install\ ESD/BaseSystem.dmg 0 0 /Volumes/OS\ X\ Install\ ESD/BaseSystem.chunklist
echo "Cleaning up"
hdiutil eject /Volumes/Mac\ OS\ X\ Lion\ Recovery\ HD\ Update
hdiutil eject /Volumes/OS\ X\ Install\ ESD/
sudo touch /Library/Preferences/SystemConfiguration/com.apple.Boot.plist
sudo kextcache -f -u /
Tested with Sierra 10.12.2 in December 22, 2016.