Are you quite sure you really have no Recovery Partition? I, too, was getting this notice when I tried to set up Find My Mac, yet I know I had a Recovery Partition. Perhaps it's too late, (or maybe this can help someone else), but before you go and reinstall the system, I'd check whether the Recovery Partition exists. You can do this by opening Applications/Utilities/Terminal.app and when the prompt appears, type:
diskutil list
You should see something like:
~ $ diskutil list
/dev/disk0 (internal, physical):
#: TYPE NAME SIZE IDENTIFIER
0: GUID_partition_scheme *1.0 TB disk0
1: EFI EFI 209.7 MB disk0s1
2: Apple_CoreStorage Thee HD 999.3 GB disk0s2
3: Apple_Boot Recovery HD 650.0 MB disk0s3
~ $
Apple_Boot Recovery HD being the key thing. If you see that, then you have a Recovery Partition.
Or, you can simply restart and hold down the < command + r > keys and see if it boots into the recovery disk. If the Recovery Partition exists, and I suspect it does, then you have a different issue. If you restored from SuperDuper, as someone mentioned, it should not have affected the Recovery Partition.
What solved this problem for me was that I'd created a Recovery Partition on a USB stick for Disk Warrior, (and had it mounted on the Desktop). Once I'd unmounted that, my iCloud Settings were then able to recognize the original Recovery Partition. I don't know if this is possible, but if you somehow cloned all of your hard drive onto an external disk, including the Recovery Partition, having this mounted might be confusing to Settings. Try unmounting, then disconnecting, any external drives. Then see if the original Recovery Partition is recognized.