Where did the recovery disk come from that you are trying to use ?
If it came from another PC by another hardware company it may check it is the correct hardware before allowing you to do a recovery.
I am not sure if you are aware, but a recovery CD is NOT a simple install of Windows.
It is normally a disk image of Windows for particular hardware enviroment and includes all the drivers and other files need for that hardware platform.
So if you have say a recovery CD for a Sony computer, and you are trying to install it on a HP computer then the drivers for the sound card, graphics card etc will not be the same, so even if you could get it to install much of the PC would not work properly.
I guess you have two choices:
Go back to the company who you bought the PC off, and ask if you can have a recovery CD. If it is an old PC this may be difficult.
Or go out an buy a new copy of Windows. If you buy Windows XP Home edition in an OEM version then this should only cost you about 60 or 70 pounds.
OEM versions are used by peole who build their own PC and it does not come with all the fancy packagaing.