1. Power down, all the way off
2. Press the power on button
3. IMMEDIATELY hold down "command-R" (for recovery mode) and keep holding it down for a while.
4. For "internet recovery", do the above but hold down "command-option-R" instead. You will need to enter your wifi password, too.
You didn't tell us WHICH Mac or which version of the OS you use.
The recovery partition doesn't exist on old Macs. I believe it originated with OS 10.7 (Lion).
To do internet recovery, you need a 2010 (2011?) Mac or later.