El tema disco de recuperación es algo
complicado, antes cuando comprabas el ordenador te daban un disco o diskette de recuperación que activaba una partición oculta y recuperaba el sistema desde ahí; de un tiempo a esta parte el disco de recuperación se supone que lo crea uno cuando arranca el ordenador por primera vez, lo malo de este sistema es que mucha gente no sabe que tiene hacerlo y luego no tiene el famoso disco; en tu caso desconozco cual de las dos situaciones es la que te toca, pero igualmente no tiene mayor importancia

Lo que habría que saber es si efectivamente tu equipo tiene esa partición oculta ya que si la tiene (que debería) también se debería de poder recuperar sin el famoso disco y una vez recuperado el sistema cuando arranques por "primera" vez deberías de poder crearlo para futuras ocasiones.
El cómo saberlo es más complicado, con una utilidad de discos se debería de poder ver, con suerte la partición podría no estar oculta y la verías, de unos 5 ó 10 GB a lo sumo; la forma cutre (pero solo sirve para deducirlo) sería por el tamaño del disco, si tu disco duro es de 120 GB pero tú solo ves disponibles 112 lo más probable es que los 8 que faltan sean esa partición oculta.
Ahora viene el pero de la cuestión, en sistemas más nuevos como Windows Vista la mayoría llevan en el Inicio - Todos los programas ... una utilidad de recuperación del sistema, al ejecutarla te permite hacer la recuperación desde la partición oculta o desde el disco de recuperación, aunque yo siempre lo he hecho desde el CD/DVD y no sé si la otra funciona correctamente; esta aplicación se puede ejecutar también arrancando el equipo como si fueses a entrar en modo seguro, en el menú de selección saldría; otros equipos llevan una tecla especial para abrirlo con solo pulsarla en el momento de encender, en el sobremesa de casa (un Packard Bell) creo que era F11, todo esto, claro, puede variar dependiendo del fabricante.
Quizás sabiendo la marca y modelo del ordenador podamos averiguar que tiene o deja de tener, incluso es posible que por el número de serie del ordenador (no de Windows) puedas descargar desde la página del fabricante un disco de recuperación para tu equipo o ponerte en contacto con su soporte online vía mail y ver si te lo pueden facilitar de algún modo; sin duda esta sería la mejor opción.
En cuanto al número de serie de Windows solo te vale para esa preinstalación, si bajas un Windows de por ahí, formateas e instalas es más que probable que te rechaze el número de serie, lo mejor antes de formatear nada es averiguar si se puede recuperar el sistema que ya tienes ya que no te dará problemas con la licencia, de hecho no tendrás ni que meterle el número porque va incrustado en el sistema.