Рекурсивное суммирование элементов списка

Question

def sum(L):
    if len(L) == 1:
        return L[0]
    i = sum (len (L) // 2)
    if  len(L) > 1:
        return i + i

L=[2,4]

print (sum(L))

когда я пытаюсь запустить его, возникает ошибка TypeEr: объект типа 'int' не имеет len ().

Answer 1

В вашем коде

i = сумма (len (L) // 2)

строка выдает ошибку, потому что в рекурсии после первого вызова суммы() вы передаете целое число, а не список

def sum(L):
    if len(L) == 0:
        return 0
    elif len(L) == 1:
        return L[0]
    else:
        index = len(L)-1
        return L[index] + sum(L[0:index])

L=[2,4]

print (sum(L))

Answer 2

В sum (len (L) // 2) вы передаете целое число (результат len(L) // 2) в качестве аргумента L вашей функции sum().(Пожалуйста, не называйте функции тем же именем, что и встроенные функции.) Затем рекурсивно вызываемый sum() пытается вычислить len(L) == 1 для этого целого числа, но целые числа не поддерживают len(), и поэтому вы получаетесообщение об ошибке в вопросе.Что именно ты на самом деле пытаешься сделать?

Answer 3

Я думаю, что вы хотели создать рекурсивную функцию sum, которая непрерывно разбивает список на более мелкие фрагменты.Таким образом, в основном вам нужно вычислить индекс средней точки, а затем использовать разрезание списка, чтобы рекурсивно передать первый подсписок и второй подсписок обратно в функцию, пока не будет достигнут базовый вариант (ы) элементов 0 или 1.оставшиеся.

def add(values):
    if len(values) == 0:
        return 0
    elif len(values) == 1:
        return values[0]
    mid = len(values)//2
    return add(values[:mid]) + add(values[mid:])

>>> add([1,2,3,4,5])
15

Answer 4

1. Не называйте вашу функцию sum, она затеняет встроенную функцию

2. Реализуйте вашу функцию, чтобы четко определить базовый случай и рекурсивный случай.

   Для базового случая, когда длина равна 1, вернуть этот элемент.Вы правильно поняли.
   Для рекурсивного случая разделите ваш список на половину и рекурсивно вычислите сумму для каждой половины.

def sum_recursive(L):
    if len(L) == 1:
        return L[0]

    idx = len(L) // 2
    return sum_recursive(L[:idx]) + sum_recursive(L[idx:])

sum_recursive всегда должен получать список и возвращать целое число.

Некоторые пробные прогоны:

In [5]: sum_recursive([1, 2, 4, 8])
Out[5]: 15

In [6]: sum_recursive([2, 4])
Out[6]: 6

---

Имейте в виду, что это не сможет обрабатывать пустые списки в качестве входных данных.Если вы также хотите учесть это, измените свой базовый случай на:

def sum_recursive(L):
    if len(L) <= 1:
        return sum(L)
    ...

Мы используем встроенную функцию sum, которая изящно обрабатывает пустые списки, возвращая 0. Для одно-списки элементов, возвращается первый элемент (также важно, чтобы вы не скрывали эти служебные функции).

Если вы не хотите использовать sum, вам нужноразделите ваш базовый случай на две части:

def sum_recursive(L):
    if len(L) == 0:
        return 0
    elif len(L) == 1:
        return L[0]
    ...