Hi, I'm wondering if the address of a smart contract is calculated based on its own code, and when the contract is mutable even after deployment, what will happen when we change the code?
Does its address change accordingly?

no, address will not change

Address is based on StateInit.

there was a special "empty" contract and console tool to find vanity address (by changing meaningless random init variable), then you deploy this contract (to address found) and then you update code of this contract to your conract code, so you'll have your contract with vanity address

oh right. I forgot about that part. But what if, say:
1. I deploy a contract
2. Modified the contract
3. The contract ran out of TONCOIN for storage fee
4. (I suppose) the nodes remove the contract from their storage
Then is there a way to recover the contract? I thought the recovery was done by re-uploading the contract's bytecode and calculate the address to see if it matches the old one. But seems like I was wrong?

Or is the part that will change the StateInit immutable?

i guess you'll need to re-upload initial contract (to get same address as before) and then re-modify it again.