It depends, really. Some recovery CDs will make a partition (or two) on your harddrive, hidden or otherwise, and I'd bet that those CDs would ruin your partition. Something you could try if you have two hard drives is to copy over all the files from one to the other after you use the recovery CD on the first one. I remember that working on Win9x but I don't know if it works on later versions.
My preferred method is to obtain (borrow from a friend) a copy of the installation CD (not recovery) and use the license key printed on a sticker on your box. In my opinion, it is not a crime to 'pirate' a copy of the genuine install CD (there are modified, slipstreamed versions) on the internet if you use your valid license key, since the key gives you the rights to one installation of (presumably) Windows, but IANAL.
For some reason, computer companies don't like to make upgrades or reinstallations easy for customers. Some computer manufacturers will supply you the OEM OS CD for free, or for a fee if you ask. Others will flat-out refuse.