sum of numbers in 2D list using recursion

Question

The matrix above is represented like this in Python:

m = [[2, 1, 3], 
     [4, 9, 8],      
     [6, 2, 7]]

The function should return the following output 2D list.

output = [[18, 16, 21],          
         [31, 28, 23],           
         [21, 11, 14]]  

e.g. 1: for the cell in the first row and first column (2), the sum for 2 across is 2 + 1 + 3 = 6. The sum for 2 down is 2 + 4 + 6 = 12. Add across (6) and down (12) and store the value 18 in the corresponding cell in the output.

The function: def recursive(m, output, row, col):

base case

reduction step - valid cell => process across and down and compute total

How to solve this with recursion method?

Answer 1

The formula seems to be: for each [i][j] take the sum of the row right to [i][j] and the column down from [i][j]. Both sums start with the element at [i][j].

Here is a version without recursion:

m = [[2, 1, 3],
     [4, 9, 8],
     [6, 2, 7]]

def strange_sum(m):
    return [[sum(m[i][j:]) + sum([m[k][j] for k in range(i, len(m))]) for j in range(len(m[i]))] for i in range(len(m))]

print(strange_sum(m))

Output: [[18, 16, 21], [31, 28, 23], [21, 11, 14]]

To involve recursion, one could calculate the row and column sums separately:

def recursive_row_sum(m, i, j):
    if j == len(m[i]):
        return 0
    else:
        return m[i][j] + recursive_row_sum(m, i, j+1)

def recursive_col_sum(m, i, j):
    if i == len(m):
        return 0
    else:
        return m[i][j] + recursive_col_sum(m, i+1, j)

def recursive_sum(m):
    return [[recursive_row_sum(m, i, j) + recursive_col_sum(m, i, j) for j in range(len(m[i]))] for i in range(len(m))]

print(recursive_sum(m))

Still another recursive approach could calculate the value at [i][j] as the sum of the values 1 to the left and 1 below minus the value diagonal below. Then summing m[i][j] twice and subtract m[i+1][j] and m[i][j-1].

def f(m, i, j):
    s = 2 * m[i][j]
    if i < len(m) - 1:
        s += f(m, i + 1, j) - m[i + 1][j]
    if j < len(m[i]) - 1:
        s += f(m, i, j + 1) - m[i][j + 1]
    if i < len(m) - 1 and j < len(m[i]) - 1:
        s -= f(m, i + 1, j + 1)
    return s

def recursive_sum_bis(m):
    return [[f(m, i, j) for j in range(len(m[i]))] for i in range(len(m))]

print(recursive_sum_bis(m))