title: Python: using a recursive algorithm as a generator
body: <p>Recently I wrote a function to generate certain sequences with nontrivial constraints. The problem came with a natural recursive solution. Now it happens that, even for relatively small input, the sequences are several thousands, thus I would prefer to use my algorithm as a generator instead of using it to fill a list with all the sequences.</p>
  
  <p>Here is an example. Suppose we want to compute all the permutations of a string with a recursive function. The following naive algorithm takes an extra argument 'storage' and appends a permutation to it whenever it finds one:</p>
  
  <pre><code>def getPermutations(string, storage, prefix=""):
     if len(string) == 1:
        storage.append(prefix + string)   # &lt;-----
     else:
        for i in range(len(string)):
           getPermutations(string[:i]+string[i+1:], storage, prefix+string[i])
  
  storage = []
  getPermutations("abcd", storage)
  for permutation in storage: print permutation
  </code></pre>
  
  <p>(Please don't care about inefficiency, this is only an example.)</p>
  
  <p>Now I want to turn my function into a generator, i.e. to yield a permutation instead of appending it to the storage list:</p>
  
  <pre><code>def getPermutations(string, prefix=""):
     if len(string) == 1:
        yield prefix + string             # &lt;-----
     else:
        for i in range(len(string)):
           getPermutations(string[:i]+string[i+1:], prefix+string[i])
  
  for permutation in getPermutations("abcd"):
     print permutation
  </code></pre>
  
  <p>This code does <em>not</em> work (the function behaves like an empty generator).</p>
  
  <p>Am I missing something?
  Is there a way to turn the above recursive algorithm into a generator <em>without replacing it with an iterative one</em>?</p>