A recovery disk? Recovery disks cannot work without the recovery partition on the hard drive, they are not full installer disks. You need an installer disk. If you run Windows 7, download the free trial disk image from DIGITAL RIVER
that is the same as your version, burn it to a DVD and then install from it. Activate with your key off the sticker on your computer.
You will need to download all of the latest drivers for your model from HP, and will also need to do the Windows updates.