Using ECDSA, given a signature and the message signed, it is possible to recover the public key. So it seems to be a waste of up to 65 bytes in each transaction. Why does bitcoin do it? Which cryptocurrencies use the key recovery approach?
it is possible to recover the public key
Yes. But this operation is slow (comparing with other bitcoin script operations). May be Satoshi Nakamoto did not know about it. Anyway, the hard-fork required to implement it. So, you are welcome to create hard-fork or altcoin with this feature implemented.
Have a look to this discussion: https://bitcointalk.org/index.php?topic=6430.0 I can not explain better
