This entirely depends on the type of recovery CD used.
Some vendors allow XP to be reinstalled from their CD (CD boot has to be active in BIOS)
Alternatively, some vendors place their installation sets on a hidden partition on the HD.
If all you did is format the C: drive, then the partition should still exist - if you performed an FDISK, removing all partitions, then go to the final option...
If the options above do not work for you, then
I would suggest you borrow an XP installation CD from a friend or neighbour and install from this CD.
When asked for the product key, this should be on the sticker on your PC.
As a final resort, you could contact your PC vendor and ask their advice - they might be able to provide you with another installation set (probably at a cost...)