Given an ASCII string, replace all ASCII chars with their Cyrillic equivalents

Question

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

        $en_letters=array_keys($map);

        $this->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->transliterations)) $this->transliterations[]=$query_translit;
                        }
                    }

            } else {
                $query_translit=$query;
            }

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

        foreach ($this->transliterations as $transliteration) {
            if (!in_array($transliteration, $this->processed)) {
                if (!preg_match("/[a-zA-Z]/", $transliteration)) {
                    return;
                } else {
                    $this->transliterate($transliteration);
                }
            }
        }
    }

Answer 1

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 < 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;
   }
}