Python 列表递归更改

Question

我在尝试以递归方式向列表中添加一系列数字时遇到错误。例如。如果输入是 [5,3,9]，我做 [5+1,3+2,9+3] 并输出 [6,5,12]。我想递归地执行此操作，所以我这样做的方式是遍历并将一个添加到列表的越来越小的部分，如下所示:

def add_position_recur(lst, number_from=0):
    length = len(lst)
    # base case
    if (length <= 1):
        lst = [x+1 for x in lst]
        print "last is", lst
    else:
        lst = [x+1 for x in lst]
        print "current list is", lst
        add_position_recur(lst[1:], number_from)
        return lst

但是，问题在于所有这一切只是将列表的每个元素加 1。错误在哪里？这与我在基本情况下返回列表的方式有关吗？

Answer 1

当你向下递归你的调用堆栈时，你切片 lst 创建一个新列表，这与你返回的不一样，所以你只会返回你应用到你的更改在第一次调用该函数时列出，丢失堆栈中的所有更改:

>>> add_position_recur([1,2,3])
[2, 3, 4]

这应该返回 [2, 4, 6]。
您需要考虑在退出时重新组合列表以获取更改。

return [lst[0]] + add_position_recur(lst[1:], number_from)

并且您需要在基本情况下返回 lst:

def add_position_recur(lst, number_from=0):
    length = len(lst)
    # base case
    if (length <= 1):
        lst = [x+1 for x in lst]
        return lst
    else:
        lst = [x+1 for x in lst]
        return [lst[0]] + add_position_recur(lst[1:], number_from)
>>> add_position_recur([1,2,3])
[2, 4, 6]

但是，这是一种相当复杂的递归方法。基本情况是空列表是惯用的，否则取头部并递归到尾部。所以需要考虑使用 number_from 的东西:

def add_position_recur(lst, number_from=1):
    if not lst:
        return lst
    return [lst[0]+number_from] + add_position_recur(lst[1:], number_from+1)

>>> add_position_recur([1,2,3])
[2, 4, 6]

这也有好处(？)不改变传入的 lst