Блог

Эй, ребята, у меня возникли проблемы с написанием этой части моего кода. Я должен суммировать элементы этого 2-мерного массива с помощью рекурсии. Я понимаю, что мне нужно сделать, но я не понимаю, как реализовать это для пошагового просмотра массива. Я продолжаю получать ошибки. Не мог бы кто-нибудь мне помочь?

 import java.util.Scanner;

public class Main {

    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  );
    }

}
  

Основной план, когда вам нужно рекурсивное решение, заключается в поиске способа разбить проблему так, чтобы она содержала меньшую проблему (или более одной меньшей проблемы), которая выглядит точно так же, как исходная проблема, только меньшего размера.

Для 2-мерного массива это может быть сложно. Допустим, ваш массив выглядит так

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

Первой мыслью может быть написать рекурсивную функцию, которая принимает row и column и добавляет a[row][column] к сумме остальной части массива. Проблема в том, что если, например, row=0 и column=0 , «меньшая проблема», которую вам нужно решить, выглядит так

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

(пожалуйста, извините за плохое оформление ASCII). Итак, теперь ваша меньшая проблема вообще не похожа на массив, а на какой-то странный многоугольник. Этот подход все еще можно использовать, написав рекурсивную функцию типа

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

Но это определенно злоупотребление рекурсией. Лучше было бы разбить массив на «первую строку» и «остальные строки»:

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

(Или вы можете разбить его на «последнюю строку» и «остальные строки».)

Теперь ваша меньшая проблема очень похожа на исходную проблему, верно? Итак, ваш ответ будет таким: «сумма элементов в массиве равна сумме первой строки плюс сумма элементов в меньшем массиве, начиная со следующей строки». Вторая часть этого — рекурсивный вызов. Первая часть, сумма первой строки, потребует, чтобы вы вызвали новую функцию для сложения строки; и поскольку вам все еще не разрешено использовать циклы, функция «сложить строку» также будет рекурсивной, но это должно быть легко.

Сказав все это, никто никогда не будет использовать рекурсию в реальном мире для решения этой проблемы. Однако, если цель состоит в том, чтобы ознакомиться с рекурсией, чтобы вы могли использовать ее, когда это требуется, тогда вам нужно следовать такому мыслительному процессу.

Чтобы сделать это без рекурсии, просто создайте два вложенных цикла for:

 int sum = 0;
for(int i=0;i<array.length;i  )
   for(int j=0;j<array[i].length;j  )
      sum  = array[i][j];
return sum;
  

Чтобы сделать это с помощью рекурсии:

 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 1,0);

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

По сути, вы делаете то же самое: просматриваете каждую строку и столбец и добавляете их вместе.

Однако обратите внимание, что существует ограничение на количество рекурсивных подпрограмм, которые вы можете использовать. Если вы повторите слишком глубоко, вы получите ошибку StackOverflow.