Well you people seem confident in having your entire account tied to a smartphone.
It's not like that could backfire or anything.
There's this neat thing called Notepad, or Word, or whatever you may have. It's on your computer, too! Neatly convenient.
What I do is I type my recovery code INTO that program, and save the file! Hell, maybe even encrypt the file for now. Wow! I still have the recovery code! Sweet!
Lose my phone, forget the code! :o! I have a file that tells me it!
Not that hard of a concept.