A Macbook air 2011 mid doesn't have the kind of recovery disks. Usually, we recover Lion through the internet. Of course, we need to start Utilities in the recovery partition.
However I had erased the recovery partition and could never start Utilities. It would be erased when HDD device name at the top of a device tree is highlighted. A Macbook air without a recovery partition goes net boot mode. Mine also did. It could recover with enough band width. Unfortunately my WiFi never has enough band width and net boot failed.
I brought my Macbook air to an Apple store. I made mine recovery with the store's WiFi.
After I returned my apartment, I made recovery disks as follows.
(1) insert a SD card or connect a USB HDD.
(2) copy a disk image file of the recovery partition to Desktop as follows.
$ diskutil list
/dev/disk0
#: TYPE NAME SIZE IDENTIFIER
0: GUID_partition_scheme *251.0 GB disk0
1: EFI 209.7 MB disk0s1
2: Apple_HFS Macintosh HD 250.1 GB disk0s2
3: Apple_Boot Recovery HD 650.0 MB disk0s3
$ diskutil mount /dev/disk0s3
$ cp -p /Volumes/Recovery\ HD/com.apple.recovery.boot/ BaseSystem.dmg ~/Desktop/
$ chflags nohidden ~/Desktop/BaseSystem.dmg
$ diskutil umount /dev/disk0s3
(3) Click BaseSystem.dmg, so it would be mounted.
(4) Use Disk Recovery to make a recovery disk from BaseSystem.dmg.