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 genera

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.