python - 在python中将for循环转换为递归函数时遇到问题

Question

我正在尝试编写一个程序来查找一维数组中不相邻元素的最大总和，到目前为止我有这个:

def find_max_sum(arr):
    incl = 0
    excl = 0

    for i in arr:

        # Current max excluding i 
        new_excl = excl if excl>incl else incl

        # Current max including i
        incl = excl + i
        excl = new_excl

    # return max of incl and excl
    return (excl if excl>incl else incl)

它有效。我唯一的问题是如何在不使用 for 循环的情况下将此函数转换为递归函数？我的大脑似乎无法找到执行此操作的方法。

Answer 1

第 1 步:重写您的函数，使其更像 Pythonic

def find_max_sum(lst):
    incl, excl = 0, 0

    for i in lst:
        incl, excl = excl + i, max(excl, incl)

    return max(excl, incl)

第 2 步:现在很容易将其重写为递归函数

def find_max_sum_recursive(lst, incl, excl):        
    if len(lst) > 0:
        i = lst[0]
        incl, excl = excl + i, max(excl, incl)

        return find_max_sum_recursive(lst[1:], incl, excl)
    else:
        return incl, excl

def call_find_max_sum_recursive(lst):
    return max(find_max_sum_recursive(lst, 0, 0))

现在你打电话

>>> call_find_max_sum_recursive([1, 2, 10, 3, 4])
15

第 1 步不是绝对必要的。毕竟它是关于 for i in arr: 中的代码块以及它们如何影响 incl 和 excl。但是，它可能会帮助您重写。