为什么在递归中乘以总和与乘以单个整数然后求和不同？

Question

我正在解决以下问题：给定一个嵌套的整数列表，我们想要找到乘积和。积和只是数字的总和，但是对于嵌套列表中的数字，我们需要将它们乘以嵌套深度。

例如：array = [2,5,[7,-1]] -> output = 19 ### 2+5+ 2*(7+ -1)

这是一个正确的递归解法：

def productSum(array, multiplier = 1):
    total_sum = 0 
    for i in range(len(array)): 
        if isinstance(array[i],int): 
            total_sum += array[i]
        else: 
            total_sum += productSum(array[i],multiplier+1)
    
    return total_sum *multiplier

然而，当我最初编写我的解决方案时，我没有在 return 末尾使用 *multiplier，而是在 'if' 语句中使用 multiplier，所以我的解决方案是：

def productSum(array, multiplier = 1):
    total_sum = 0 
    for i in range(len(array)): 
        if isinstance(array[i],int): 
            total_sum += array[i] * multiplier
        else: 
            total_sum += productSum(array[i],multiplier+1)

    return total_sum

我只是想了解为什么我上面的解决方案没有产生预期的结果，因为我的理解是它们是相同的，因为在每个递归调用中 'multiplier' 是固定的，所以为什么会这样重要的是我将整数乘以乘数然后将它们相加，而不是将整数相加然后乘以乘数？？？其中，如果我以上理解正确的话就是两者的区别。

举个例子，输入：数组：[5, 2, [7, -1], 3, [6, [-13, 8], 4]]，第一个解产生 27，这是正确的，但是第二个解决方案产生了 12，这是错误的！

Answer 1

问题是，在最初的解决方案中，您没有将 productSum(array[i],multiplier+1) 乘以乘数。

如果您只想乘以数值，则乘数需要是深度级别的阶乘，因为乘法会相互叠加。

例如：

[5, 2, [7, -1], 3, [6, [-13, 8], 4]]

计算为：

5 + 2 + 2*(7 + -1) + 3 + 2*(6 + 3*(-13 + 8) + 4)

传播乘法：

5 + 2 + 2*7 + 2*-1 + 3 + 2*6 + 2*3*-13 + 2*3*8 + 2*4

请注意，-13 和 8 分别乘以 2 和 3（而不是像初始代码那样乘以 3）。

顺便说一句，您可以在推导式上使用 sum 函数而不是 for 循环。

# like 'correct' solution:        depth * ∑ recursion | value
def productSum(a,d=1):
    return d*sum(productSum(n,d+1) if isinstance(n,list) else n for n in a)

# like initial solution (fixed):  ∑ depth * (recursion | value)
def productSum(a,d=1):
    return sum(productSum(n,d+1)*d for n in a) if isinstance(a,list) else a 

# or factorial approach:          ∑ (recursion | value * depth!)
def productSum(a,d=1,m=1):
    return sum(productSum(n,d+1,m*d) for n in a) if isinstance(a,list) else a*m

为什么在递归中乘以总和与乘以单个整数然后求和不同？

why is multiplying a sum in a recursion different from multiplying the individual integers then summing?

python

recursion

nested-lists