CODEWITHSUNDEEP
algorithmrecursion
Kevin
Kevin

Reputation: 6831

Recursive summing up elements of a two-dimensional array?

I am an algorithm beginner and just started reading "Data Structure and Algorithms in Java" by Michael Rich. He presents a binary recursion based function called "BinarySum(A,i,n)".

 BinarySum(A,i,n)
 Input:An array A and integer i and n
 Output: The sum of n integers in A starting and index i
 if n==1 then
  return A[i];
 return BinarySum(A,i,[n/2])+BinarySum(A,i+[n/2],[n/2])

And we will initially start the call by BinarySum(A,0,n).

In the excercise that follows, there is a question asking me to describe a way to use recursion to add all the elements of a n*n two dimensional array of integers. The hint he gives is we can follow the style of BinarySum(A,i,n) by using two recursive calls.

I am stuck on this, I could think of the solution like loop through each row of n*n matrix, then for each row, I call BinarySum(A,i,n), then sum together. But I really don't think that is the purpose of this exercise.

Had thought about other possible solutions, but I am stuck on using recursion achieving it. Could experts give some hints? Thanks.

Upvotes: 3

Views: 9343

Answers (5)

shiva rao
shiva rao

Reputation: 172

Working c++ code

int main() {
    int arr[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    cout << arraySum(arr, 2, 2, 2) << endl;
    return 0;
}
/*
 * arr: 2d array data
 * i = current row index(will start from rowSize - 1)
 * j = current column index(will start from columnSize - 1)
 * mSize = Column Size
*/
int arraySum(int arr[3][3], int i, int j, int mSize ) {
    if (i == 0 && j == 0) {
        return arr[i][j]; // condition 3
    }
    if (j == 0) {
        return arr[i][j] + arraySum(arr, i - 1, mSize, mSize); // condition 2
    }
    else {
        return arr[i][j] + arraySum(arr, i, j - 1, mSize); // condition 1
    }
}

Basic Explanation:

function arraySum starts from [n-1][m-1] position to [0][0]

End<-1 | 2 | 3
     ---------
     4 | 5 | 6
     ---------
     7 | 8 | 9 <- start
  1. (i = 2, j = 2) condition 1 will be executed: a[2][2] + a[2][1] + (a[2][0] as col val is 0 then we will go to condition 2)
  2. After condition 2 changes(i = 1, j = 2) a[1][2] + a[1][1] + (a[1][0] as col val is 0 then we will go to condition 2)
  3. After condition 2 changes(i = 0, j = 2) a[0][2] + a[0][1] + (a[0][0] as both row and col are 0 we will hit condition 3)

Volla ! Answer

Upvotes: 0

Elliott de Launay
Elliott de Launay

Reputation: 1168

  // Break the 2D array into shorter arrays via rows
  // Initial n is A.length - 1 
  public int binarySum(int[][] A, int j, int n){
    if(j > n) return 0;
    if(j == n ) return binarySum(A[j], 0, A[j].length - 1);
    int m = (j + n) / 2;
    return binarySum(A, j, m) + binarySum(A, m + 1, n);
  }

  //Break the array into smaller arrays via cols
  public int binarySum(int[] A, int i, int n){
    if( i > n) return 0;
    if(i == n) return A[i];
    int m = (i + n) / 2;
    return binarySum(A, i, m) + binarySum(A, m+1, n);
  }

Upvotes: 0

Andrew
Andrew

Reputation: 876

public static int deepSum(int[][] data){
    //n*n
    return deepSum(data, data.length, data.length);
}
private static int deepSum(int[][] data, int n, int m){
    if (n ==1)
        return deepSumCol(data ,m, 0);
    else
        return  deepSum(data, n-1,m) + deepSumCol(data, m, n-1);
}

private static int deepSumCol(int[][] data, int n ,int m){
    if (n ==1)
        return data[m][0];
    else{
        return  deepSumCol(data, n -1,m) + data[m][n-1];
    }

}

Upvotes: 0

Pham Trung
Pham Trung

Reputation: 11294

Working java Code,

This is the BinarySum for 2D matrix, assuming you have n1 rows and n2 column, So, the total sum will be equals to the sum of n1/2 first rows and n1/2 last rows. For each row, the sum will be divided into n2/2 first columns and n2/2 last columns, 

public static void main(String[] args) {

    int[][] data = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
    System.out.println(sum(data, 0, 3, 0, 4));
}

public static int sum(int[][] data, int x, int n1, int y, int n2) {

    if (n1 == 1 && n2 == 1) {
        return data[x][y];
    }
    if (n1 == 1) {
        return sum(data, x, n1, y, (n2 / 2)) + sum(data, x, n1, y + (n2 / 2), n2 - (n2 / 2));
    } else {
        return sum(data, x, (n1 / 2), y, n2) + sum(data, x + (n1 / 2), n1 - (n1 / 2), y, n2);
    }
}

Output:

78

Upvotes: 2

Ashu Pachauri
Ashu Pachauri

Reputation: 1403

I will not give you the pseudocode. I guess you can easily figure that out after the explanation. There are more than one ways to achieve this with similar recursion technique.

  1. For 2-D array, your recursion now branches into 4 sub-branches instead of 2. You can think of this as dividing your grid into 4 sub-grids and recursively summing them up. This essentially means that, now your recursive function BinarySum (A, i, j, n) will sum n rows and n columns starting from cell (i,j) (Make sure you take care of taking floor and ceiling at appropriate places when n is odd).

  2. Another way to look at this is having two functions, one for recursively summing rows and other for recursively summing up columns. So your BinarySum(A, i, n) will recursively sum all rows from row number i to row number n. When n = 1, your problem reduces to summing all the elements of a 1-D array (use the function you already have to calculate that).

Upvotes: 1

Related Questions