user2075: 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?

user12983: 
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

2075: <p>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?</p>
 12983: <blockquote>
  <p>it is possible to recover the public key</p>
</blockquote>

<p>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.</p>

<p>Have a look to this discussion: <a href="https://bitcointalk.org/index.php?topic=6430.0" rel="nofollow noreferrer">https://bitcointalk.org/index.php?topic=6430.0</a> I can not explain better</p>
