This is a nice, practical algorithm. Beware though that in theory it can take an unbounded amount of time, since in order for it to make progress it must generate at least one heads and one tails on the input, and although runs of all-heads or all-tails become exponentially unlikely as input size increases (or as the number of passes performed on a fixed-size input increases), there's still no guarantee that a mixed run will happen before any fixed amount of computation has been done.
If it's implemented to run in the typical "depth-first sequential" manner of a recursive algorithm, in which each problem generates its own subproblems, solves them all, and then immediately continues execution until it is itself solved, then it is guaranteed to eventually terminate, since the only way to stall progress forever in this situation would be an infinite, uninterrupted sequence of one outcome (e.g., heads), and that would contradict the assumption that P(heads) = 0.5. OTOH, if a "breadth-first" computation was used, in which all subproblems at a given recursion depth are solved in sequence before any higher-level subproblems, the algorithm could run forever: The top-level problem could produce a mixed run, resulting in two equal-sized subproblems, each of which never makes any progress due to one subproblem always getting all-heads, the other always all-tails.
Any unbiased algorithm that uses an unbiased coin to shuffle n > 2 elements must be potentially unbounded.
Proof: there are n! possible permutations. If the algorithm always finishes within k coin tosses then there are 2^k possible outcomes. For n > 2 we have that n! does not divide 2^k, so not all outcomes can be equiprobable.
This is a proof by contradiction: it shows that any bounded algorithm doesn't have equally probable outputs, i.e., that it is necessarily biased, contradicting our assumption that it is unbiased. Therefore, an unbiased, bounded algorithm cannot exist (for n > 2): any algorithm is necessarily either biased or unbounded.
Comments
This is a nice, practical algorithm. Beware though that in theory it can take an unbounded amount of time, since in order for it to make progress it must generate at least one heads and one tails on the input, and although runs of all-heads or all-tails become exponentially unlikely as input size increases (or as the number of passes performed on a fixed-size input increases), there's still no guarantee that a mixed run will happen before any fixed amount of computation has been done.
If it's implemented to run in the typical "depth-first sequential" manner of a recursive algorithm, in which each problem generates its own subproblems, solves them all, and then immediately continues execution until it is itself solved, then it is guaranteed to eventually terminate, since the only way to stall progress forever in this situation would be an infinite, uninterrupted sequence of one outcome (e.g., heads), and that would contradict the assumption that P(heads) = 0.5. OTOH, if a "breadth-first" computation was used, in which all subproblems at a given recursion depth are solved in sequence before any higher-level subproblems, the algorithm could run forever: The top-level problem could produce a mixed run, resulting in two equal-sized subproblems, each of which never makes any progress due to one subproblem always getting all-heads, the other always all-tails.
Any unbiased algorithm that uses an unbiased coin to shuffle n > 2 elements must be potentially unbounded.
Proof: there are n! possible permutations. If the algorithm always finishes within k coin tosses then there are 2^k possible outcomes. For n > 2 we have that n! does not divide 2^k, so not all outcomes can be equiprobable.
You proved that not all outcomes are equiprobable, not that they're unbounded.
This is a proof by contradiction: it shows that any bounded algorithm doesn't have equally probable outputs, i.e., that it is necessarily biased, contradicting our assumption that it is unbiased. Therefore, an unbiased, bounded algorithm cannot exist (for n > 2): any algorithm is necessarily either biased or unbounded.
That is not enough because k is allowed to depend on n.
For n > 2, n! does not divide 2^k for any k, since n! has a factor of 3.