You can try again and this time, do internet recovery and not patition recovery.
Here's the info on internet recovery.
Macs released in mid-2011 or later, along with some older Macs once you install a firmware update, include a new feature called OS X Internet Recovery (Lion Internet Recovery under Lion). This feature works much like standard OS X Recovery but with one major difference: Internet Recovery works even if you don't have a Recovery HD partition, if that partition isn't working properly, or if your Mac’s drive is damaged or not connected.
How does Internet Recovery work? Unlike standard recovery mode, which uses software on a partition of your Mac’s drive, Internet Recovery uses a combination of code stored in your Mac’s firmware and a net-boot image stored on Apple’s servers. Specifically, when you start Internet Recovery, your Mac contacts Apple’s Internet Recovery servers and requests the appropriate disk image to boot your Mac into recovery mode. Your Mac then downloads the necessary code over the Internet and boots. At that point, Internet Recovery works much like standard recovery mode, as described in the next section.
One other difference between standard recovery mode and Internet Recovery is that when you boot into Internet Recovery, the system tests your Mac’s RAM and its hard drive to see if either has any obvious hardware problems. Also, because Internet Recovery requires an Internet connection just to boot, if your Mac is not connected to a working Ethernet network, you’re required to connect to a Wi-Fi network right from the start.
However, while Internet Recovery is a useful feature, and it could even be a metaphorical life-saver should your hard drive die, it has one major drawback: It’svery, very slow compared to standard recovery mode, because it must first download the necessary software. In fact, if you boot into Internet Recovery, the first screen you see displays a slow-moving progress bar along with a warning that booting will take a while.
How do you boot into Internet Recovery? If you’re really curious, you may be able to force your Mac to boot into Internet Recovery by holding down Command+Option+R at startup. However, in my testing, this didn’t work on every Internet Recovery-capable Mac.
If that keyboard shortcut doesn’t work for you, the answer is generally, “You can’t unless you really need to.” As long as you have a valid Recovery HD partition, trying to boot into Internet Recovery will instead boot your Mac into standard recovery mode. Internet Recovery comes into play only if you have a compatible Mac with no working Recovery HD partition—in that case, your Mac automatically uses Internet Recovery. In fact, on one of my Macs, to even test Internet Recovery I had to use a number of tricks to make my Mac’s Recovery HD partition visible and then purposely erase and remove it. Only then, with a blank drive with no Recovery HD partition, was I able to boot into Internet Recovery by holding down Command+R at startup. (If you have a compatible Mac with an easily accessible hard drive, you could simply disconnect your hard drive, but that’s not an option for most current Macs.)