Try with internet recovery, hold Command-Option-R at startup, this is different from recovery and is built into the iMac's firmware, should always work.
----------
Hold down the "OPTION" key to get to DU.
Hold down the "R" key for internet recovery.
Option does not bring you into DU, it will get you into the boot manager, and R is also wrong, it is Command-R or Command-Option-R, first is Recovery, second is Internet Recovery.
The difference is that one is built into firmware and the other resides on an invisible partition on the HD/SSD.
__________________________
Edit:
OP, the alt key is called the Option key in OS X, if you can't get into normal Recovery try the internet Recovery, this should always work, but as with recovery you need an active internet connection.
If you don't see the Recovery Option after you held the Option key at startup this means or your Recovery partition is damaged or it is not there due to an earlier wipe of the HD.