O recovery trata-se de uma um auxílio ou até mesmo um backup de todas as configurações de fábrica,programas vindos com o micro
o que ocorre nele é que ao utiliza-lo seu notebook voltará as configurações,programas,tudo como se ele estivesse vindo de fábrica.Já na Formatação via CD do WINDOWS,você irá limpar totalmente seu HD de todos os arquivos dos quais eram contidos nele,ou seja, uma instalação por completa,limpa,ou seja,terá de atualizar o windows e instalar todos os programas após o processo de formatação.
Recomendar uma ou outra só em caso de uma situação concreta,pois nem sempre tem de formatar,o próprio recovery já solucionaria,e nem sempre o recovery dependendo da situação resolveria e ai entraria a formatação,depende da situação um ou o outro são recomendados.