OP wants to send the 'recording' to a phone.
Arduino by itself can not record a sound file... but I think I recall some library using an Uno and Waveshield ..
It wasnt WaveHC.... WaveRC perhaps? (been a while).. must save it to the SD card or something? (never played with that functionality personally... just WaveHC stuff)
And technically you could receive data back from a phone using bluetooth (once paired..etc).
Ive done it to make little 'GUI's' for my phone using MIT App Inventor before to send data to my Arduino to control a RGB laser cut lamp I made.. (re: simple bluetooth)
The issue/gap I see is.. sending this 'whatever' (audio file/clip/data) -TO- the phone unfortunately....