Solaxun 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'))

Answer
res = res + repl #using += works, due to extending being a mutation (same list referenced at each call)

This line is the issue, as you seem to have guessed. Each time, in the recursive call, it assigns a new local list, which doesn't keep the reference to the old one, so the caller isn't notified of changes.

Luckily your function already returns the list, so let's just capture that:

     res = repl_underscores(each,res) #trying to pass modified list to keep building up
Comments