python中的递归代码

Question

我是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 for last + rec,我不能使用return来获取列表(new_list).请向我解释我做错了什么...谢谢!

Answer 1

让我们编写一些测试用例并练习一些测试驱动的开发:

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))

如果我们将其添加到您的代码并运行它,我们得到:

    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

现在再次运行测试.这次我们得到了

    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

现在我们的程序返回

[]
[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

运行测试.有用!现在回顾一下我们的解决方案是一个很好的做法,看看它如何能够收紧并变得更加优雅.我看到我们使用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