CODEWITHSUNDEEP
pythonrecursiontypes
slowpoking9
slowpoking9

Reputation: 309

python recursion type errors

I'd be grateful if someone could tell me why sum_all([1,[2,[3,[4]]]]) doesn't work? It says that it can only concatenate list (not "int") to list but if my code works as I think it should that shouldn't happen. Btw my code uses recursion to sum all elements of a list regardless of whether they're an integer or another list

def rec_sum(numbers):
    lnum = len(numbers)
    if lnum == 0:
        return 0
    elif lnum == 1:
        return numbers[0]
    else:
        numbers[0] = numbers[-1] + numbers[0]
        del numbers[-1]
        return rec_sum(numbers)

def sum_all(numbers):
    lnum = len(numbers)
    if lnum == 0:
        return 0
    elif lnum == 1:
        if isinstance(numbers[0], int):
            return numbers[0]
        elif isinstance(numbers[0], list):
            return rec_sum(numbers[0])
    else:
        if isinstance(numbers[-1], list) and isinstance(numbers[0], list):
            numbers[0] = rec_sum(numbers[0]) + rec_sum(numbers[-1])
            del numbers[-1]
            return sum_all(numbers)
        elif isinstance(numbers[-1], list) and isinstance(numbers[0], int):
            numbers[0] = numbers[0] + rec_sum(numbers[-1])
            del numbers[-1]
            return sum_all(numbers)
        elif isinstance(numbers[-1], int) and isinstance(numbers[0], list):
            numbers[0] = rec_sum(numbers[0]) + numbers[-1]
            del numbers[-1]
            return sum_all(numbers)
        elif isinstance(numbers[-1], int) and isinstance(numbers[0], int):
            numbers[0] = numbers[0] + numbers[-1]
            del numbers[-1]
            return sum_all(numbers)

Traceback (most recent call last):

File "<pyshell#8>", line 1, in <module> sum_all([1, [2, [3, [4]]]])
 File "C:/Users/#/Documents/python/recursion.py", line 36, in sum_all numbers[0] = numbers[0] + rec_sum(numbers[-1])
  File "C:/Users/#/Documents/python/recursion.py", line 17, in rec_sum numbers[0] = numbers[-1] + numbers[0]
   TypeError: can only concatenate list (not "int") to list

Upvotes: 0

Views: 45

Answers (2)

blhsing
blhsing

Reputation: 106946

You don't need rec_sum at all. The idea of recursion is that every sub-list is treated in the same way as the current list, and your rec_sum doesn't have the same logic that distinguishes list from numbers as the your main function sum_all as it treats every item as a number, so when it tries to add the items but one of them is a list, an exception is thrown because you can't "add" (or concatenate a list with a number).

Instead, simply remove rec_sum and replace all your calls to rec_sum with sum_all and your code is good.

def sum_all(numbers):
    lnum = len(numbers)
    if lnum == 0:
        return 0
    elif lnum == 1:
        if isinstance(numbers[0], int):
            return numbers[0]
        elif isinstance(numbers[0], list):
            return rec_sum(numbers[0])
    else:
        if isinstance(numbers[-1], list) and isinstance(numbers[0], list):
            numbers[0] = sum_all(numbers[0]) + sum_all(numbers[-1])
            del numbers[-1]
            return sum_all(numbers)
        elif isinstance(numbers[-1], list) and isinstance(numbers[0], int):
            numbers[0] = numbers[0] + sum_all(numbers[-1])
            del numbers[-1]
            return sum_all(numbers)
        elif isinstance(numbers[-1], int) and isinstance(numbers[0], list):
            numbers[0] = sum_all(numbers[0]) + numbers[-1]
            del numbers[-1]
            return sum_all(numbers)
        elif isinstance(numbers[-1], int) and isinstance(numbers[0], int):
            numbers[0] = numbers[0] + numbers[-1]
            del numbers[-1]
            return sum_all(numbers)

Output of print(sum_all([[4,5],1,4,5,[3,[1],5]])): (this used to throw an exception)

28

Upvotes: 1

Primusa
Primusa

Reputation: 13498

Very simply consider what happens when a nested input is in your code. In the code:

if isinstance(numbers[-1], list) and isinstance(numbers[0], list):

Lets say this criteria is indeed satisfied. You then have:

numbers[0] = rec_sum(numbers[0]) + rec_sum(numbers[-1])

We know that numbers[-1] is a list, but we don't know if it is a flat list. In rec_sum(numbers[-1]) you have line:

numbers[0] = numbers[-1] + numbers[0]

Since numbers was nested, one element in numbers can be a list, and another an integer. Trying to add them throws an error.

You are trying to approach this problem wrong. Think about it this way:

  1. Try to add together all the elements in the input
  2. If you encounter a list, replace it with the sum of all of it's elements
  3. Repeat steps 1 and 2 until no more nested lists

Here's a neat one liner that applies the above logic:

def sum_all(l): return sum([i if isinstance(i, int) else sum_all(i) for i in l])

Upvotes: 1

Related Questions