[Solved] Add Elements of a 2-Dimensional Array using recursion

by


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  |
  +-------------------------+

(please excuse the bad ASCII art). 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  |
  +-------------------------+

(Or you could break it into “the last row” and “the rest of the rows”.)

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 recursive, 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.

1

solved Add Elements of a 2-Dimensional Array using recursion