You will need a full Windows install disk, not just an HP recovery disk. Boot from the installer disk and select custom install, then unpartition all existing partitions and install to the single remaining unpartitioned space.
If you need an installer disk you can get a Microsoft authorized image from HERE and then burn it to a DVD and install. Make sure to get the same version that your laptop came with so that your activation key will work with the re-install.