How to repair disk using Recovery HD

I just did a repair permissions and verify disk and got the following message:

Disk Utility stopped verifying "Macintosh HD." This disk needs to be repaired using the Recovery HD. Restart your computer, holding down the command key and the R key until you see the Apple logo. When the OS X Utilities window appears, choose Disk Utility. The volume Macintosh HD was found corrupt and needs to be repaired.

This might be a stupid question, but: Following the instructions above, is that procedure the "Recovery HD," or is that an actual disk that I'm supposed to have? What do I do when I go to Disk Utility?

I have a MacBook Pro 13-inch, mid 2010, 2.4GHz Intel Core 2 Duo, with a replaced (May 2014) 500 GB hard drive, OS X Mavericks 10.9.5.

Many thanks!!!