Hola.
¿En qué lenguaje lo necesitas?
No parece algo complicado.
No tengo noción de C, pero no debe ser complicado la verdad.
Yo creo que alguien con una idea en el lenguaje puede hacerlo sin problemas, pero bueno...
Te dejo una referencia de lo que deberías hacer pero en Python a ver si te sirve de algo:
ejemplo = "1359182"
presolucion = max(ejemplo)
presolucion2 = ejemplo.replace(presolucion, '')
solucionfinal = presolucion2+presolucion
print("Ejemplo: "+ejemplo)
print("Solucion: "+solucionfinal)
#El code de arriba devuelve:
Ejemplo: 1359182
Solucion: 1351829
Te advierto de antemano, que aquí no realizan tareas y hubo revuelo sobre eso hace poco, así que te recomiendo aportar lo que intentaste.
Edito:En cuando a la recursividad, lo mismo, no es nada complejo hacer algo así...
Saludos.