Reputation: 37
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
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
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