Solaxun - 4 months ago 14
Python Question

# Recursive algorithm - extend vs creating new list with '+'

So I have a recursive function below that keeps replacing

`'_'`
characters with each lowercase letter in the alphabet, until all combinations of those possible lowercase letters are substituted for the
`'_'`
characters.

Simple Example:

`repl_underscores('__A')`

`>>>[a_A,b_A,c_A......aaA,abA,acA....zzA]`

I had this function working with extend to build up the list, which as the comment below mentions, modifies the same existing list in-place repeatedly and accomplishes the job.

For the sake of practice, I wanted to re-write to build a new list on each call and pass that result to the successive recursive calls, with the goal of getting the same result.

It's not working and I know it has to do with the fact that I'm building up a new list on each call, but I thought that since I was passing in the built-up version on each recursive call that I would be OK since those calls would then be informed of changes.

I'm having trouble finding out where it is breaking. I know I can get it to work by modifying the same list (either through mutable default, global variable, or extend), but I would like to build up a new clean list each time I recurse.

``````def repl_underscores(letters,res=None):
if res is None: res = list()
if '_' not in letters: return res
repl = [letters.replace('_',letter,1) for letter in string.ascii_lowercase]
res = res + repl #using += works, due to extending being a mutation (same list referenced at each call)
for each in repl:
repl_underscores(each,res) #trying to pass modified list to keep building up
return res

print(repl_underscores('__DER'))
``````

``````res = res + repl #using += works, due to extending being a mutation (same list referenced at each call)
``````     res = repl_underscores(each,res) #trying to pass modified list to keep building up