Please consider the following PHP function. It's objective is simple: given an ASCII string, to replace all ASCII chars with their Cyrillic equivalents. As can be seen, certain ASCII chars have two possible equivalents. 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. So, 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? Any help is much appreciated.

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