如何正确格式化递归基本情况以限制无限迭代

Question

递归错误：调用Python对象时超过了最大递归深度

在使用递归遍历列表时，我试图将任何奇数添加到"res"，并将任何偶数乘以"res"。

输入为：

calc_res([3, 2, 2, 4, 15], 2))

输出应为：95

假设第一个元素总是奇数，如果它为0，则忽略该元素。

截至目前，我的代码是：

def calc_res(some_list, res):
i = 0
if some_list[i] >= len(some_list):
return
if some_list[i] % 2 != 0:
result = i + res
return result + calc_res(some_list, res)
if some_list[i] % 2 == 0:
result = i * res
return result + calc_res(some_list, res)
print(calc_res([3, 2, 2, 4, 15], 2))

Answer 1

您需要将中间结果作为参数传递给下一个递归调用。

当没有元素存在时，您可以直接返回传入的res

def calc_res(some_list, res):
if len(some_list) == 0:
# no remaining elements, just return the result.
return res
current_number = some_list[0]
if current_number % 2 != 0:
# this means that calc_res from the remaining of some list.
# and current number's result is added to res, pass to next call.
return calc_res(some_list[1:], res + current_number)
else:
if current_number == 0:
return calc_res(some_list[1:], res)
else:
return calc_res(some_list[1:], res * current_number)

Answer 2

这样的东西可能效果更好：

def calc_res(some_list, res, i=0):
if i == len(some_list):
return res
if some_list[i] % 2 != 0:
result = some_list[i] + res
else:
result = some_list[i] * res
return calc_res(some_list, result, i + 1)
print(calc_res([3, 2, 2, 4, 15], 2))

在这里，我们向calc_res()添加第三个参数，它是要在给定调用中处理的some_list中的索引i。如果i已经到达some_list的末尾，则返回res。否则，我们将some_list的第i个元素相加或相乘，并用更新的结果和递增的i值递归调用calc_res()。

其他解决方案也是可能的，例如避免i，而是将some_list的较小切片向下传递到递归堆栈，但没有切片的方法使用较少的空间。

Answer 3

修改constantstranger的答案以忽略some_list中的元素(如果其值为0)会得到：

def calc_res(some_list, res, i=0):
if i == len(some_list):
return res
if some_list[i] % 2:
result = some_list[i] + res
elif some_list[i]:
result = some_list[i] * res
else:
return res
return calc_res(some_list, result, i + 1)
print(calc_res([3, 2, 2, 4, 15, 0], 2))

输出：95