Prawdopodobnie, z rekurencją będzie jeszcze wolniej, o ile wcześniej nie skończy się stos.
Aktualnie przekazujesz kopię stringa z każdym wywołaniem funkcji. Prawdopodobnie chcesz przekazywać referencję lub wskaźnik:
int przemiana(string& a,int u, int i )
{
if(u==i){
return...