python - python中的递归代码

我是python的新手，正在尝试解决我的作业...我正在尝试创建一个递归函数，该递归函数将一个数字列表[a，b，c ....]转换为以下列表：[a ，a + b，a + b + c，....]。

这是我的代码：

def rec_cumsum(numbers):
    ''' Input: numbers - a list of numbers,
            Output: a list of cumulative sums of the numbers'''
    new_list=numbers
    last=new_list[-1]
    if numbers==[]:
         return numbers
    if len(numbers) == 1:
         return numbers[0]
    new_list.remove(last)
    rec= rec_cumsum(new_list)
    new_list.append(rec+last)
    return last+rec

这行得通，但是因为我将return用于last + rec，所以无法使用return来获取列表（new_list）。请向我解释我做错了什么...谢谢！

最佳答案

让我们编写一些测试用例并实践一些测试驱动的开发：

tests = [[],         # Desired answer: []
         [1],        # [1]
         [1,2],      # [1, 3]
         [1,2,3],    # [1, 3, 6]
         [1,2,1,3]]  # [1, 3, 4, 7]
for t in tests:
    print(rec_cumsum(t))

如果我们将其添加到您的代码和run it, we get中：

    last=new_list[-1]
IndexError: list index out of range

为什么是这样？显然-1是超出范围的索引。为什么new_list没有-1索引？

啊哈如果new_list为空，则会发生这种情况。因此，我们需要首先解决基本情况。在讨论的同时，我们还要使用@MartijnPieters的建议：

if len(numbers) <= 1:
     return numbers

获得

def rec_cumsum(numbers):
    ''' Input: numbers - a list of numbers,
            Output: a list of cumulative sums of the numbers'''
    if len(numbers) <= 1:
         return numbers
    new_list=numbers
    last=new_list[-1]
    new_list.remove(last)
    rec = rec_cumsum(new_list)
    new_list.append(rec[-1]+last)
    return last+rec

现在再次运行测试。 This time we get

    return last+rec
TypeError: unsupported operand type(s) for +: 'int' and 'list'

所以现在Python在说last是int，而rec是list，我们不能将两者加在一起。

好的，rec应该是一个列表，因为它是rec_cumsum(new_list)的返回值。用什么代替last+rec？

让我们考虑一个具体的例子。如果rec是[a, a+b]，那么我们要返回[a, a+b, a+b+c]。我们如何形成a+b+c？

如何将rec中的最后一个元素与numbers中的最后一个元素相加：

rec[-1]+last

我们要将其附加到rec的末尾：

rec.append(rec[-1]+last)

让我们进行更改，看看会发生什么。但是，在编辑时，我们还要清理一些我们从未使用过的代码。我们可以删除new_list.append(rec[-1]+last)：

def rec_cumsum(numbers):
    ''' Input: numbers - a list of numbers,
            Output: a list of cumulative sums of the numbers'''
    if len(numbers) <= 1:
         return numbers
    new_list=numbers
    last=new_list[-1]
    new_list.remove(last)
    rec = rec_cumsum(new_list)
    rec.append(rec[-1]+last)
    return rec

Now our program returns

[]
[1]
[1, 3]
[1, 3, 6]
[2, 3, 4, 7]

谢谢，我们的程序运行没有错误。但是，请稍候...它返回错误的结果。看最后一行。

rec_cumsum([1,2,1,3])返回[2,3,4,7]，而正确的答案是[1,3,4,7]。为什么第一个数字错误？

它与new_list.remove(last)有关。此命令从last中删除​​第一次出现的new_list。我们要删除最后一次出现。

因此，让我们使用

new_list = numbers[:-1]

因此，程序变为：

def rec_cumsum(numbers):
    ''' Input: numbers - a list of numbers,
            Output: a list of cumulative sums of the numbers'''
    if len(numbers) <= 1:
         return numbers
    new_list=numbers[:-1]
    last=numbers[-1]
    rec = rec_cumsum(new_list)
    rec.append(rec[-1]+last)
    return rec

Run the tests。有用！现在，回顾一下我们的解决方案，看看如何将其收紧并变得更优雅，是一种好习惯。
我看到我们使用new_list和last作为临时变量。我们真的需要它们吗？

def rec_cumsum(numbers):
    if len(numbers)<=1:
        return numbers
    result = rec_cumsum(numbers[:-1])
    result.append(result[-1]+numbers[-1])
    return result

关于python - python中的递归代码，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13440069/