Some recovery CDs will install an entire hard drive image making the machine act just like it did when you first turned the power on. In this case, yes, all you would need are the recovery CDs
On the other hand, I've come across some recovery CDs that require the OS to be running, and they simply restore certain system files.
Typically, most recovery CDs are the first type. Look at the documentation that came with them. It's a dead giveaway if they have a warning about erasing all information on disc.