Next to Safe mode (and normal operating mode, of course), Recovery mode is the most discussed and recommended. Introduced in OS X 10.7 in 2011, it relies on a hidden volume or partition installed on your boot drive, and offers powerful tools which normal OS X cannot match. Apple details these here.
Unlike Safe mode, for which you hold the Shift key once you hear the startup chime/chord, Apple recommends that you hold the Command and R keys from the moment that you start or restart your Mac, and keep them held until after you see the Apple logo. Prior to macOS Sierra, this should work fine with a wireless keyboard; when running Sierra, you are likely to find that you must connect your keyboard to a USB port, or your Mac may be unable to enter Recovery mode.
In any case, when you are starting to venture into Recovery mode it is often wise to connect a USB keyboard, or connect your Apple Wireless keyboard to a USB port using its charging cable (which effectively turns it into a USB keyboard). Should you then need to run hardware diagnostics, or Bluetooth fails, you will be well prepared.
If you cannot get your Mac to enter Recovery mode, it may not have a usable Recovery partition – either it has not been created (some old models), or the startup disk is sufficiently damaged as to make the partition there unusable. You should then start up from another bootable drive, such as a USB memory stick with OS X installer on it, or, provided you have a good internet connection, you can enter ‘OS X Internet Recovery’ (remote recovery) by holding down the Option, Command and R keys through startup. That is really a get-you-home option, as even with a good bandwidth connection it is the slowest means of starting any Mac up.
Recovery mode runs a special cut-down version of OS X which lacks a Finder but provides a simple graphical interface. It only has a single user, and many of the folders and features of regular OS X are missing. However, it has quite good support for command shell tools, and your normal volumes – including your regular startup disk – are mounted and available in the /Volumes folder. Those who are reasonably competent at the command line can do a great deal in Recovery mode – and those who are inept could do a greal deal of damage in Terminal too!
Rumours about Recovery mode automatically checking and repairing permissions, or repairing keychains, appear completely false: neither of those happens when starting up in Recovery mode, and there are no tools to repair keychains.
Once in Recovery mode, four tools are offered in the standard dialog, and an additional three in the Utilities menu.
To Restore From Time Machine Backup, you will need your Time Machine backup drive connected and available. You can use this to roll back to a previous version of OS X, or to your last backup, as you need. However it copies files one at a time, making it slower than some utilities such as Carbon Copy Cloner, and you can expect it to take several hours even with a USB 3 or Thunderbolt connection to your backup. You also get all the old files and folders, so if you want to roll back, it is usually quicker to initialise, install a fresh copy of OS X and bring it up to date, then to restore selectively from your backups.
Reinstall OS X will download and install OS X on your normal startup disk, the one associated with the active Recovery partition. When run from normal Recovery mode, this will re-install the last version which you had installed. Note that remote recovery behaves differently, and will install the version of OS X which your Mac originally shipped with, as it cannot tell the last version which was installed. Although that should get you up and running again, it also means that it may take you a long time to get your current system re-installed.
Get Help Online uses Safari to connect to the web, and offers Apple’s support website in particular. It can also connect to this website and others, although no Safari plug-ins or extensions are included, and you will have to manually enter any usernames and passwords, as it has no access to your normal keychain.
Disk Utility is probably the most commonly-used tool in Recovery mode: performing First Aid on your normal startup volume is best when run in this mode, and is a wise move after any serious crash or freeze, such as a kernel panic during file writes.
Firmware Password Utility allows you to set and change your firmware password. It does not give you access to your normal keychain, and cannot perform keychain repairs.
Network Utility lets you perform basic troubleshooting of network problems, using Ping, etc.
Terminal gives you full access to shell commands. Because you can only control SIP on your normal boot disk, this is where you might need to turn SIP off, and back on again, should you need.
The System Information app is also tucked away in /Applications/Utilities, and can be run from Terminal, although there doesn’t seem to be any more friendly way of running it.
Other recovery modes
Standard Recovery and Internet Recovery modes are not the only ones available to you. If your startup disk is damaged and you cannot enter normal (local) recovery, you may be able to mount your Time Machine backup drive for recovery purposes. To do this, hold the Option key down as soon as you hear the startup chime/chord, until you see the boot menu, offering different drives for startup. Connect then power up your backup drive, and it should appear in that list. Select it, and your Mac should then start up from that.
You can also create a bootable recovery drive using OS X installer (or another tool), for instance on a USB memory stick. To use that for recovery purposes, hold the Option key down as soon as you hear the startup chime/chord, until you see the boot menu. Then connect the removable drive (e.g. memory stick), and when it appears in the list of drives select it.
If you cannot enter Recovery mode or one of its relatives, you should consider restarting your Mac and testing its hardware out before going any further.
Updated 29 October 2016 with details for Sierra.