You can also burn the recovery DVDs yourself. In windows click on Start and look for an app in HP folder (something like Management or Backup and Restore)
I didn't realize you still have access to Windows. I guess you want to reformat just because it has become slow or unstable. Then as mentioned by electrontau you can create as many Recovery cd as you want using an HP application that should be installed in your Windows. I don't know the name of the software but look for something like HP back-up management or something.