Given an ASCII string, replace all ASCII chars with their Cyrillic equivalents The objective of the following PHP function is simple: given an ASCII string, replace all ASCII chars with their Cyrillic equivalents.

As can be seen, certain ASCII chars have two possible equivalents.

For example: if the function is fed the string "dvigatel" it should get you "двигател". 

The problem: if I pass "dvigat", the function will finish its execution in a fairly reasonable amount of time.

But, if I pass "dvigatel", which is only a couple letters longer, the execution time exceeds my 30 second PHP execution time limit. 

Could anybody give me a few pointers here, what's wrong with this function, why does it run so slow with an 8-char string?

function transliterate($query) {
        $map=array(
            "a" =&gt; array("а", "ъ"),
            "b" =&gt; "б",
            "c" =&gt; array("с", "ц"),
            "d" =&gt; "д",
            "e" =&gt; "е",
            "f" =&gt; "ф",
            "g" =&gt; array("г", "ж"),
            "h" =&gt; "х",
            "i" =&gt; array("и", "й"),
            "j" =&gt; array("дж", "й"),
            "k" =&gt; "к",
            "l" =&gt; "л",
            "m" =&gt; "м",
            "n" =&gt; "н",
            "o" =&gt; "о",
            "p" =&gt; "п",
            "q" =&gt; "я",
            "r" =&gt; "р",
            "s" =&gt; "с",
            "t" =&gt; "т",
            "u" =&gt; array("ъ", "ю", "у"),
            "v" =&gt; array("в", "ж"),
            "w" =&gt; "в",
            "x" =&gt; array("кс", "х"),
            "y" =&gt; array("ъ", "у"),
            "z" =&gt; "з"
        );
        $query_array = preg_split('/(?&lt;!^)(?!$)/u', $query );

        $en_letters=array_keys($map);

        $this-&gt;processed[]=$query;

        foreach ($query_array as $letter) {
            if (in_array($letter, $en_letters)) {

                if (!is_array($map[$letter])) {
                    $query_translit=str_replace($letter, $map[$letter], $query);
                } else {
                        foreach ($map[$letter] as $bg_letter) {
                            $query_translit=str_replace($letter, $bg_letter, $query);

                            if (!in_array($query_translit, $this-&gt;transliterations)) $this-&gt;transliterations[]=$query_translit;
                        }
                    }

            } else {
                $query_translit=$query;
            }

            if (!in_array($query_translit, $this-&gt;transliterations)) $this-&gt;transliterations[]=$query_translit;
        }

        foreach ($this-&gt;transliterations as $transliteration) {
            if (!in_array($transliteration, $this-&gt;processed)) {
                if (!preg_match("/[a-zA-Z]/", $transliteration)) {
                    return;
                } else {
                    $this-&gt;transliterate($transliteration);
                }
            }
        }
    }
Why a recursive function for such a simple task?

$in = 'This is your input';
$map = 'your char translation array here';
$out = '';
for($i = 0; $i &lt; strlen($in); $i++) {
   $char = $in[$i];
   if (isset($map[$char])) {
       if (is_array($map[$char])) {
           $newchar = $map[$char][0]; // whatever your multi-char selection logic is...
       } else
           $newchar = $map[$char];
       }
       $out .= $newchar;
   }
}