Io una soluzione sono riuscito a farla.... Forse non rispetta proprio le consegne ma è l'unica, efficace, che mi venisse in mente...

L'idea è:

1) creo una stringa come variabile globale result di dimensione doppia delle altre due;
2) creo anche un puntatore a carattere con lo stesso indirizzo della stringa result (puntano entrambi alla prima cella, così lavorerò su uno e ritornerò l'altro);
3) copie le stringhe passate da input e passate a una funzione 'unione' in una stringa totale;
4) utilizzo una funzione RICORSIVA per riempire la stringa result con i caratteri non ripetuti presenti nella stringa totale;
5) ritorno la stringa result alla funzione 'unione';
6) ritorno il risultato della funzione ricorsiva al main.

Così funzia, so che la volevi ricorsiva del tutto, ma è la cosa più efficacie che mi è venuta in mente!