You must have GNU Recode 3.5 or higher installed on your system. You can download the package from » http://directory.fsf.org/All_GNU_Packages/recode.html.
The Recode library version 3.6 adds weird characters behind converted strings under certain circumstances. Thus it's safer to use Recode v3.5 or one of the available alternatives like the iconv or mbstring extension.
To be able to use the functions defined in this module you must compile your PHP interpreter using the --with-recode[=DIR] option.
Crashes and startup problems of PHP may be encountered when loading the recode as extension after loading any extension of mysql or imap. Loading the recode before those extension has proved to fix the problem. This is due a technical problem that both the c-client library used by imap and recode have their own hash_lookup() function and both mysql and recode have their own hash_insert function.