Exercise $2$: Permutations

A permutation of a sequence $(s_0,s_1,$dots,$s_{n-1})$ is a sequence with the same terms, but in a different order. For example, the sequence $(3,4,6)$ admits $6$ permutations:

$(3,4,6),(3,6,4)$

$(4,3,6),(4,6,3)$

$(6,3,4),(6,4,3)$

Give a decrease and conquer algorithm to output all permutations of a sequence of $n$ distinct elements.

Prove that this algorithm is correct.

Give a recurrence for the runtime of this algorithm.

Solve this recurrence.