What is "signature recovery"? Bolt #11 defines a "tagged field," n, which identifies the payee by a public key, but it isn't required.  It also requires a signature which can be verified only if the public key is known.  When tagged field n is not included, something called "signature recovery" is required.  How does that work?

I ask because I was thinking that if I get two invoices, I should be able to determine if they indicate the same payee.  I thought tagged field 'n' would be great for this, but it might not be supplied.  So how can I compare the two invoices to see if they came from the same node?  If signature recovery is built in, I guess that means I can get the public key even if tagged field 'n' is missing.  But how would I do that?
It is as you suspect: You can recover the public key knowing only the signature and the message. The recovery id byte in the signature is not strictly necessary as there's a brute force option, but it is included for efficiency.

There's an implementation of public key recovery in bitcoin core's secp256k1 library.