Describe a way to use recursion to compute the sum of all th

Describe a way to use recursion to compute the sum of all the elements in an n times n (two-dimensional) array of integers.

Solution

import java.util.Scanner;

public class SumOfAll {

public static void main(String[] args) {

int[][] a;
a = new int[3][4];
int sum = 0;

System.out.println(\"Enter 12 numbers: \");
Scanner scan = new Scanner(System.in);

for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
a[i][j] = scan.nextInt();
}
}
sum = sum2D(a, 0, 0);
System.out.println(\"The sum of the array: \" + sum);

}

public static int sum2D(int a[][], int row, int col) {
if (row == a.length-1) {
return a[row][col];
}

if (col == a[row].length-1) {
return a[row][col] + sum2D(a, row++, 0);
}

return a[row][col] + sum2D(a, row, col++);
}

}

Explanation:

The basic plan, when you need a recursive solution, is to look for a way to break down the problem so
that it contains a smaller problem (or more than one smaller problem) that looks just like the original problem, only smaller.

For a 2-D array, this can be tricky. Say your array looks like

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15

One\'s first thought might be to write a recursive function that takes a row and column, and adds a[row][column] to the sum of the
rest of the array. The problem is that if, for example, row=0 and column=0, the \"smaller problem\" you have to solve looks like

+---------------------+
1 | 2 3 4 5 |
+---+ |
| 6 7 8 9 10 |
| 11 12 13 14 15 |
+-------------------------+

So now your smaller problem doesn\'t look like an array at all, but some weird polygon. It\'s still possible to use this approach,
by writing a recursive function like

int sumOfWeirdShapedSectionOfArray(int[][] array, int firstRow, int firstCol)

But that\'s definitely an abuse of recursion. Better would be to break down the array into the \"first row\" and \"the rest of the rows\":

1 2 3 4 5
+-------------------------+
| 6 7 8 9 10 |
| 11 12 13 14 15 |
+-------------------------+

Now, your smaller problem looks a lot like the original problem, right? So your answer would be that \"the sum of the elements in the
array is the sum of the first row, plus the sum of the elements in the smaller array starting with the next row\".
The second part of this is a recursive call. The first part, the sum of the first row, would require that you call a new
function to add up a row; and since you\'re still not allowed to use loops, the \"add up a row\" function would also be
but that should be easy.

Having said all this, nobody would ever use recursion in the real world on this problem. However,
if the point is to get familiar with recursion so that you can use it when it\'s called for,
then this sort of thought process is what you need to follow.