could someone help please, i do not know why i get this error:
def sum_list(the_list):
if not the_list:
return 0
else:
mid = len(the_list) // 2
return sum_list(the_list[:mid]) + sum_list(the_list[mid:])
print(sum_list([10, 20, 30]))
if the_list is of length 1 (which will happen at some stage in your recursive calls) you will end up in an infinite recursion... (mid will be 0).
you need to address that as a second base case:
def sum_list(the_list):
if not the_list:
return 0
if len(the_list) == 1:
return the_list[0]
else:
mid = len(the_list) // 2
return sum_list(the_list[:mid]) + sum_list(the_list[mid:])
i assume this is an exercise in recursion. python offers sum to do that efficiently.
You get an infinite recursion for a list of length 1, because the_list[1 // 2:] would return the_list[0:] which is the same list
The cost of calling a function is a creation of a new frame (call stack). There is a soft limit in Python which prevents it from creating too many frames, and this limit is 1000 by default.
You can raise this limit, but it's highly discouraged because it can cause interpreter crash on higher values.
When trying to debug a function, it can sometimes be useful to stick a print statement in there to see how it's being called. We expect that this function should eventually return because it will eventually reduce to the base case, which is an empty list. Does that happen?
def sum_list(the_list):
print(f"Summing {the_list}")
...
prints:
...
Summing [10]
Summing []
Summing [10]
Summing []
Summing [10]
Summing []
...
RecursionError: maximum recursion depth exceeded while calling a Python object
This tells us that something might be wrong with summing a list that's 1 item long. Let's step through that logic step by step:
>>> the_list = [10]
>>> mid = len(the_list) // 2
>>> the_list[:mid]
[]
>>> the_list[mid:]
[10]
So when we do our recursion on [10], we're going to end up making another recursive call to [10] again, which will just repeat infinitely. To fix this we need to extend our base case:
if len(the_list) == 1:
return the_list[0]
Note that if our base case only ever returned zero, it'd be impossible for the recursive call to ever return anything that wasn't a sum of zeroes!
I've taken your function and added some print statements that help show what the problem is.
def sum_list(the_list, depth=1):
print(" The list: ", the_list, "at depth: ", depth)
if not the_list:
print(" List empty at depth", depth)
return 0
else:
mid = len(the_list) // 2
print(" Splitting list at ", depth, "into ", the_list[:mid], " and ", the_list[mid:])
return sum_list(the_list[:mid], depth +1) + sum_list(the_list[mid:], depth + 1)
print(sum_list([10, 20, 30]))
If you run this code, you'll be able to see the value of the_list at each call to sum_list() which can help show why the recursion is infinite.
sum(the_list).