Imprimir Todas as Permutações de uma String

É-lhe dada uma string e pede-se que crie uma função recursiva para gerar e imprimir todas as permutações dos caracteres da string. Uma permutação de uma string é definida como uma rearranjo dos seus caracteres.

A única linha da entrada contém a string s.

A saída do programa deverá ser todas as permutações dos caracteres da string s. Cada permutação deve ser impressa em uma nova linha. A ordem das permutações não importa.