They should be able to provide you the Recovery CD's, if they are available, although they may cost a little. Generally, I believe that Gateway uses a recovery partition which is stored on a separate drive on the computer.

Hope this helps.

Grif