How are recovery keys possible if something is encrypted using a password? I thought that encryption works as follows - it is about changing the thing we want to secure using an algorithm and using the password to mathematically change the secured content so it is unreadable.
If something is encrypted using a password then doesn’t it mean that the password is the only thing that can be used to mathematically change the encrypted thing so it becomes unecrypted?
I just have no idea how do recovery keys can even work!
Conceptually, a recovery key is usually like a second password.  The data is typically encrypted with a data encryption key and then the data encryption key is then encrypted twice, once with a key derived from recovery key and once with a key derived from the user password.  A significant point here is that the data encryption key never changes.  If you change your password then that just results in the data encryption key being encrypted with a new key derived from the new password.
The specifics depend on the exact product that you're interested in (e.g. Bitlocker or Apple or whatever).
By the way, the above (again at a high level) is very similar to how data is encrypted using PGP and I've read that it's similar to S/MIME as well (though I've never read that spec so cannot confirm that).