Sum integers in 2d array using recursion ?

Question

Hello! I need some help with this problem. I have to sum alle the integers in a 2d array using recursion. Below is what I have managed to do on my own, but I'm stuck. This code generates the sum 14, which should be 18. Any suggestions? Is the base case wrong? Or is the recursive method wrong?

public class tablerecursion {

public static void main(String[] args) {

    int [][] tabell = new int[][] { {1,2,3},
                                    {3,2,1},
                                    {1,2,3}  }; 
    int sum = rec(tabell,2,2);
    System.out.println(sum);

}

static int rec(int [][] table, int n,int m) {

    if (m == 0) return table [n][0];
    if (n == 0) return table [0][m];
    System.out.println("n:"+n+ "  m:"+m);
    return  rec(table, n-1, m) + rec(table, n, m-1);

}

}

Answer 1

You need to tell your professor that this problem is totally unsuited to a recursive solution. Any solution would be entirely artificial. It might be interesting to solve it in Linq, but that is whacking a fly with a sledgehammer.

Answer 2

I would solve this using two functions. First create a function that can recursively sum a single (1d) array. The write a function that recursively sums the previous function over the outer array.

Remember that table[N] is itself an array. You don't have to access it all in one go.

Answer 3

A couple of other answers suggest using a 1D routine to sum the column and the row adjacent to an element in the corner of the 2D array

BUT

It would be just as valid to cut your 2D array into four smaller 2D arrays, and recurse that way. The stopping condition is of course when the input is a 1x1 2D array, where the answer is trivial.

follow up

This runs into a snag unless the array dimensions are 2^m x 2^m ; anything else and sooner or later you encounter an Nx1 or 1xN input, and you simply cannot cut this into four sub-arrays. So you end up having to deal with 1D input anyway.

Answer 4

See here is what I would turn in, and point out that a recursive solution doesn't apply:

public static void Main()
{
        var a = new int[][] {  new int[] {1,2,3},
                               new int[] {3,2,1},
                               new int[] {1,2,3}  }; 
        int result = a.Sum(row => row.Sum());
        Console.WriteLine(result);
}

It is better to be right than simply considered right.

Answer 5

Here is an example of possible solution. If java compiler could optimize tail recursion then it would be as efficient as iterative solution. Now it eats stack very agressively.

public static long countSum (int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    return countSum (matrix, 0, 0, 0, matrix.length, matrix[0].length);
}

private static long countSum (int[][] matrix, long acc, int curI, int curJ, int maxI, int maxJ) {
    if (curI >= maxI) {
        return acc;
    }
    if (curJ >= maxJ) {
        return countSum(matrix, acc, curI + 1, 0, maxI, maxJ);
    }
    return countSum(matrix, acc + matrix[curI][curJ], curI, curJ + 1, maxI, maxJ);

}