I did the same, but with two caveats:

1. The same as zebula suggested.
2. Made a copy of the xs with copy.copy (as you're popping items out of the list)

I wouldn't use recursion unless it's a must / makes it really simple, and here you can easily unroll.

@jlreeder is correct. I like this one too. Goes in line with "Ask forgiveness rather than permission".