MacBook Air A1237 Recovery
The MacBook Air (from early 2008) does neither have a Recovery HD by default nor an Internet Recovery.  You would need to install the original OS with the medium you received with your computer (Mac OS X 10.5 Leopard) or if you either have the disc or a USB stick version of Mac OS X 10.6 Snow Leopard, you can install that as well (disc version will require either a USB SuperDrive or a second Mac with an optical drive you can share). Once done, you can at least use your computer again already.

If you, however, want to reinstall Mac OS X 10.7 Lion, you will first have 10.6 Snow Leopard installed and fully updated (see above what that will require). Otherwise, you would need a USB stick with the Lion Installer on it to bypass installing Leopard or Snow Leopard.