DennngP
DennngP

Reputation: 37

Change the value of the list object in the recursion function

def divide(alist):
    # when the list have only one element, it should return the 0
    if len(alist) == 1:
        alist[:] = list([0])

    else:
        middle = len(alist) / 2
        divide(alist[:middle])
        divide(alist[middle:])
temp = [1, 2, 3, 4, 5, 6]
divide(temp)
print temp

In my function, after the recursion, i want to get the [0, 0, 0, 0, 0, 0],but temp is still the [1, 2, 3, 4, 5, 6]. And i also use alist[:] = list([0])to ensure the alist to be re-assigned.

Why? Is there something wrong with the reference?

Upvotes: 1

Views: 90

Answers (2)

Eric Duminil
Eric Duminil

Reputation: 54263

Please mention your intented goal next time you ask a question. My guess was that you didn't need both recursion and in-place modification of your list.

So my first answer was to propose in-place modification without recursion :

def set_to_zero(alist):
    alist[:] = [0 for _ in alist]

temp = [1, 2, 3, 4, 5, 6]
set_to_zero(temp)
print(temp)
# [0, 0, 0, 0, 0, 0]

It turns out that you need recursion without in-place modification, because you want to write a merge sort.

Merge sort's most common implementation does not sort in place;[5] therefore, the memory size of the input must be allocated for the sorted output to be stored in (see below for versions that need only n/2 extra spaces).

Here's a clean implementation of the sort, with some debug lines. Here's a related question on SO (Mergesort python) with many implementations.

Upvotes: 1

AChampion
AChampion

Reputation: 30268

Your code doesn't work becuase slicing as in divide(alist[:middle]) creates a new list, so alist after the first recursion doesn't refer to temp anymore.

It is more common to return results rather than trying to create side effects in the calling arguments, e.g.:

def divide(alist):
    # when the list have only one element, it should return the 0
    if len(alist) == 1:
        return [0]
    middle = len(alist) // 2
    return divide(alist[:middle]) + divide(alist[middle:])

print(divide(temp))
# [0, 0, 0, 0, 0, 0]

Obviously, this is relatively nonsense but I'm assuming you are just setting up the structure to do something specific.

If you really wanted to do this with side effects (not recommended!!!) then you would need to keep a left and right index and use that to eventually assign the [0], e.g.:

def divide(alist, left, right):
    middle = (right - left) // 2

    # when the list have only one element, it should return the 0
    if middle == 0:
        alist[left:right] = [0]
    else:
        divide(alist, left, left+middle)
        divide(alist, left+middle, right)

temp = [1, 2, 3, 4, 5, 6]
divide(temp, 0, len(temp))
print(temp)
# [0, 0, 0, 0, 0, 0]

If you want to keep the original calling signature then you can use an _inner() function to handle the recursion, which would allow you to default the args but in reality you could just return _inner(0, len(alist)) without them:

def divide(alist):
    def _inner(left=0, right=len(alist)):  # default args based on comment @EricDuminil
        middle = (right - left) // 2
        # when the list have only one element, it should return the 0
        if middle == 0:
            alist[left:right] = [0]
        else:
            _inner(left, left+middle)
            _inner(left+middle, right)
    return _inner()

temp = [1, 2, 3, 4, 5, 6]
divide(temp)
print(temp)
# [0, 0, 0, 0, 0, 0]

Upvotes: 2

Related Questions