Das hat nichts mit der Rekursion an sich zu tun: Wiederholte String Concatenation (ist das richtig geschrieben?) ist generell nicht besonders schnell. Und wenn man dann noch eine Schleife drumherum baut, wirds auch nicht schneller
Probier mal den StringBuilder aus