Ошибки типа рекурсии python

slowpoking9 спросил: 13 июня 2018 в 09:30 в: python

Буду признателен, если кто-нибудь скажет мне, почему sum_all ([1, [2, [3, [4]]]]) не работает? В нем говорится, что он может только перечислить список (а не "int"), но если мой код работает так, как я думаю, это должно произойти не должно. Btw мой код использует рекурсию для суммирования всех элементов списка независимо от того, являются ли они целым или другим списком

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 (последний последний вызов):

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

2 ответа

Есть решение
Primusa ответил: 13 июня 2018 в 09:57

Очень просто подумайте о том, что происходит, когда вложенный код находится в вашем коде. В коде:

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

Допустим, что этот критерий действительно удовлетворен. У вас есть:

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

Мы знаем, что numbers[-1] - это список, но мы не знаем, является ли он плоским списком. В rec_sum(numbers[-1]) у вас есть строка:

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

Поскольку числа были вложенными, один элемент в числах может быть списком, а другой - целым. Попытка добавить их выдает ошибку.

Вы пытаетесь подойти к этой проблеме неправильно. Подумайте об этом так:

  1. Попробуйте добавить все элементы во входные данные
  2. Если вы столкнулись со списком, замените его суммой всех его элементов
  3. Повторите шаги 1 и 2, пока не появится больше вложенных списков.

Вот аккуратный один лайнер, который применяет вышеприведенную логику:

def sum_all(l): return sum([i if isinstance(i, int) else sum_all(i) for i in l])
slowpoking9 ответил: 13 июня 2018 в 10:00
Большое вам спасибо за то, что нашли время, чтобы помочь мне!
Primusa ответил: 13 июня 2018 в 10:01
Нет проблем :) Если это решит вашу проблему, отметьте это как принятое, нажав зеленую галочку рядом с ответом. Благодаря :)
blhsing ответил: 13 июня 2018 в 10:03

Вам вообще не нужен rec_sum. Идея рекурсии состоит в том, что каждый под-список обрабатывается так же, как текущий список, и ваш rec_sum не имеет той же логики, которая отличает список от чисел в качестве основной функции sum_all, поскольку она обрабатывает каждый элемент как число, поэтому, когда он пытается добавить элементы, но один из них представляет собой список, генерируется исключение, потому что вы не можете "добавить" (или объединить список с числом).

Вместо этого просто удалите rec_sum и замените все ваши вызовы на rec_sum на sum_all и ваш код хорош.

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)

Вывод print(sum_all([[4,5],1,4,5,[3,[1],5]])): (это используется для исключения исключения)

28