Where you notified of a service recovering? If so, then it's assumed, that if the service recovered, that the host did also.
Example: I powered off my ftp server. I am notified of the HOST being down, because first the service check failed, then nagios looked to see if the host is ok, and it wasn't. So nagios knows that it's not a service problem, but a host problem and I'm notified of that fact.
Now, I power on the ftp server. Nagios is still looking in it's schedule of checks to make, and all those checks are for SERVICES ONLY. This time, the ftp server service check passed, and since that is a state change, I am notified of this state change and it says my ftp service is ok on host "whatever". So of course, I have to assume that the host has recovered.
Now, as another example to find out if what you say is true, then try this:
Example I do the same as above, except that when I power back on, the ftp service is still not working. Nagios does it's check's again, and see's that the service still fails. It then checks to see if host is still bad, and it is found to be OK. So again, this is a state change and you are notified that the HOST has recovered. You are also notified that the service ftpd is not running.