CODEWITHSUNDEEP
pythonrecursion
user908015
user908015

Reputation:

Issue with recursive calls

I wrote this function:

def append_to_all(L, v):
    '''Append value v, which may be of any type, to all the nested lists in L.
    L is a list, and may contain other lists.'''

        if len(L) == 0:
            return L.append(v)
        elif isinstance(L[0], list):
            L[0].append(v)
            return append_to_all(L[1:], v)
        else:
            return append_to_all(L[1:], v)

if __name__ == '__main__':
    L = [1, 2, [3]]
    append_to_all(L, 'a')
    print L # should return [1, 2, [3, 'a'], 'a']

The function returns [1, 2, [3, 'a']] instead of [1, 2, [3, 'a'], 'a']. I tried debugging but it can't figure out the error. I seems when the len(L) == 0 function is called the 'a' is appended to the empty list but not to global L.

How would I go about fixing this?

Thank you!

Upvotes: 1

Views: 115

Answers (1)

Winston Ewert
Winston Ewert

Reputation: 45039

L[1:] produces a copy of the list. Its a whole new list with copies of everything in the original list except the first item. If you add elements to it, that has no effect on the original list. Hence when you append to the empty list, that only appends to the empty list not any of the lists that come before it.

In order to do this recursively you shouldn't append to lists, rather you should return new lists

def append_to_all(L, v):
'''Append value v, which may be of any type, to all the nested lists in L.
L is a list, and may contain other lists.'''

    if len(L) == 0:
        return [v]
    elif isinstance(L[0], list):
        return [L[0] + [v]] + append_to_all(L[1:], v)
    else:
        return [L[0]] + append_to_all(L[1:], v)

But this isn't really the place to use recursion. The iterative solution is simpler and more efficient.

def append_to_all(L, v):
    for item in L:
        if isinstance(L, list):
            item.append(v)
    L.append(v)

Upvotes: 3

Related Questions