If you saved the secret key when you first enabled Authenticator you can download Authenticator again and "import" that key to get yourself back up and running.
If you didn't do that you'll have to contact the exchange and go through their specific recovery process.
Make sure that you whenever you save your recovery key for the Authenticator app, that you store it off line, preferably written on paper, with a back up and stored in a safe place. Do not safe the recovery key on your computer or online!