A good exercise to test one's understanding of recursion is to write a function that generates all permutations of a string:
def get_perms(to_go, so_far=''):
if not to_go:
return [so_far]
else:
ret = []
for i in range(len(to_go)):
ret += get_perms(to_go[:i] + to_go[i+1:], so_far + to_go[i])
return ret
This code is fine, but we can significantly improve the efficiency from a memory standpoint by using a generator:
def perms_generator(to_go, so_far=''):
if not to_go:
yield so_far
else:
for i in range(len(to_go)):
for perm in perms_generator(to_go[:i] + to_go[i+1:], so_far + to_go[i]):
yield perm
(Note: the last for
loop can also be replaced with yield from
in python 3.3)
My question: why do we need to iterate over the results of each recursive call? I know that yield
returns a generator, but from the statement yield so_far
it would seem as though we're getting a string, and not something we would need to iterate over. Rather, it would seem as though we could replace
for perm in perms_generator(to_go[:i] + to_go[i+1:], so_far + to_go[i]):
yield perm
with
yield perms_generator(to_go[:i] + to_go[i+1:], so_far + to_go[i])
Thank you. Please let me know if the title is unclear. I have a feeling the content of this question is related to this SO question.