user1137: Since P2PKH and P2SH addresses use Base58Check_encoding, the 4 byte checksum appended in binary contains some redundancy. Strictly mathematically speaking, those 4 bytes correspond to ca. floor(log(2^32)/log(58)+1) = 6 base58 "digits" (but 6 base58-digits encode 36 bits, i.e. probably only 5 instead of 6 can be omitted). But is this sound? In a 2^n base this would be trivial, but base 58 basically influences all bytes... Is there a recovery algorithm?

user51948: The checksum of Base58Check encoding is simply a truncated hash of the rest of the bytes. This means there is no recovery algorithm other than just brute-forcing until the hash matches.
That is one of the big advantages of the Bech32 address format proposed in BIP-173. It uses an algebraic BCH code which can actually correct errors rather than just detect them, and has better error detection/correction properties than Base58Check.
In both cases, however, it is strongly discouraged for code to perform any address recovery itself. You should report to the user that errors exist, and let the user fix them. Otherwise, you risk loss of funds.

1137: <p>Since P2PKH and P2SH addresses use <a href="https://en.bitcoin.it/wiki/Base58Check_encoding" rel="nofollow noreferrer">Base58Check_encoding</a>, the 4 byte checksum appended in binary contains some redundancy. Strictly mathematically speaking, those 4 bytes correspond to ca. floor(log(2^32)/log(58)+1) = 6 base58 &quot;digits&quot; (but 6 base58-digits encode 36 bits, i.e. probably only 5 instead of 6 can be omitted). But is this sound? In a 2^n base this would be trivial, but base 58 basically influences all bytes... Is there a recovery algorithm?</p>
 51948: <p>The checksum of Base58Check encoding is simply a truncated hash of the rest of the bytes. This means there is no recovery algorithm other than just brute-forcing until the hash matches.</p>
<p>That is one of the big advantages of the Bech32 address format proposed in <a href="https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki" rel="nofollow noreferrer">BIP-173</a>. It uses an algebraic BCH code which can actually correct errors rather than just detect them, and has better error detection/correction properties than Base58Check.</p>
<p>In both cases, however, it is strongly discouraged for code to perform any address recovery itself. You should report to the user that errors exist, and let the user fix them. Otherwise, you risk loss of funds.</p>
