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