MacOS – Missing Yosemite Recovery Partition

Start by reading this document from Apple, which explains the recovery partition in Lion. From the article:

OS X Lion includes a new feature called Lion Recovery that includes all of the tools you need to reinstall Lion, repair your disk, and even restore from a Time Machine backup without the need for optical discs.

In short, if you remove this partition you'll need a Lion USB drive, or physical media to perform the actions described by Apple above.

To reclaim the space of the recovery partition follow the steps below:

1. Open Terminal.app
2. Run the commands below (omit the # and everything after)

$ diskutil list                                   # list disk partitions
/dev/disk0
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:      GUID_partition_scheme                        *500.1 GB   disk0
   1:                        EFI                         209.7 MB   disk0s1
   2:                  Apple_HFS Nymeria                 499.2 GB   disk0s2
   3:                 Apple_Boot Recovery HD             650.0 MB   disk0s3 <---
$ diskutil eraseVolume HFS+ Blank /dev/disk0s3    # Erase Recovery HD
$ diskutil mergePartitions HFS+ "Nymeria" disk0s2 disk0s3  # Merge partitions / reclaim space

One thing to note here, you can only merge consecutive partitions. If you have disk0s2 and disk0s4 running diskutil mergePartitions HFS+ "Nymeria" disk0s2 disk0s4 will merge partitions disk02s2, disk02s3, disk02s4. Also, only the data on the first partition will be preserved when merging. As an example, if your Recovery HD is disk0s3 and your OS partition is disk0s4, merging using diskutil is not possible. Use extreme caution modifying your partition table, and I'd highly recommend taking a full backup before hand.

Apple recommends that you backup, erase and reinstall the original OS X, then try updating again, as per the instructions below. However, it is feasible to merge steps 3 and 4, installing Mavericks in step 3, then restoring your data to that OS.

1. Make a full backup of your hard disk and all of its data (including your Boot Camp partition, which is not normally backed up by Time Machine).
2. Erase your hard disk and create a single Mac OS Extended (Journaled) partition.
3. Reinstall your original copy of OS X.
4. Re-download the OS X upgrade from the Mac App Store and retry your upgrade install.

^{Source: Apple KB Article HT4649}

Alternatively, you could use an app such as iPartition to delete the Recovery HD then extend the startup disk to fill the free space. Since there is now no Recovery HD, the installer should have no problem creating one from scratch.