Python: usando um algoritmo recursivo como gerador

Recentemente, escrevi uma função para gerar certas seqüências com restrições não triviais. O problema veio com uma solução recursiva natural. Agora acontece que, mesmo para entradas relativamente pequenas, as seqüências são de vários milhares; portanto, eu preferiria usar meu algoritmo como gerador em vez de usá-lo para preencher uma lista com todas as seqüências.

Aqui está um exemplo. Suponha que queremos calcular todas as permutações de uma string com uma função recursiva. O seguinte algoritmo ingênuo usa um argumento extra 'storage' e anexa uma permutação a ele sempre que encontra um:

def getPermutations(string, storage, prefix=""):
   if len(string) == 1:
      storage.append(prefix + string)   # <-----
   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

(Por favor, não se preocupe com a ineficiência, este é apenas um exemplo.)

Agora, quero transformar minha função em um gerador, ou seja, para gerar uma permutação em vez de anexá-la à lista de armazenamento:

def getPermutations(string, prefix=""):
   if len(string) == 1:
      yield prefix + string             # <-----
   else:
      for i in range(len(string)):
         getPermutations(string[:i]+string[i+1:], prefix+string[i])

for permutation in getPermutations("abcd"):
   print permutation

Este código faznão trabalho (a função se comporta como um gerador vazio).

Estou esquecendo de algo? Existe uma maneira de transformar o algoritmo recursivo acima em um geradorsem substituí-lo por um iterativo?