You cannot format the hard drive from the Recovery mode.
Boot from your c d ,by choosing CD as first boot mode in your CMos Setup.in the Bios.
Continue to recovery option but do not choose it.
Continue on to new windows installation choose C Drive as the location and you will see the option to format your drive in Fat 32 or NTFS system.
You can also format your drives using 3rd party software such as Partition Magic.
If you feel comfortable with floppies instead, use a Windows 98 boot disc, if one is available, and change to C:\ from A:\ , after the "loading with CD Rom support" has loaded and finished, and choose "FORMAT C:"