why is multiplying a sum in a recursion different from multiplying the individual integers then summ-CodePudding

I am solving the following problem: we are given a nested list of integers, and we want to find the product sum. The product sum is simply the sum of the numbers, however for numbers in a nested list, we need to multiply them with the depth of the nesting.

For example: array = [2,5,[7,-1]] -> output = 19 ### 2 5 2*(7 -1)

Here is a correct recursive solution:

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

However, when I initially wrote my solution, rather than having the *multiplier at the end with the return, I had the multiplier within the 'if' statement, so my solution was:

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

I just want to understand why my solution above doesn't produce the desired result, because my understanding is that they are the same, since within each recursion call the 'multiplier' is fixed, so why does it matter if I multiply the integers with the multiplier then sum them, vs. summing the integers then multiplying with the multiplier??? Which, if I understand the above correctly is the difference between the two.

To give an example, with the input: array: [5, 2, [7, -1], 3, [6, [-13, 8], 4]], the first solution produces 27, which is correct, however the second solution produces 12, which is wrong!

CodePudding user response：

it has to do with precedence, adding then multiplying is different than multiplying then adding.
in the first code,

a = a b;
return a*c

in the second code

a = a b*c
return a

here, b*c happens first then a is added

CodePudding user response：

The issue is that, in the second solution, you are not multiplying productSum(array[i],multiplier 1) by the multiplier.

If you only want to multiply the numeric values, your multiplier will need to be the factorial of the depth level because the multiplications compound over each other.

You could use the sum function over a comprehension instead of a for-loop.

# like 1st 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 2nd solution:       ∑ 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