Разделяй и властвуй Сумма массивов целых чисел

Question

Я написал следующую программу, чтобы найти сумму всех целых чисел, используя алгоритм рекурсии «разделяй и властвуй» в Java:

Но как-то сумма получается неверно.

public class DivideAndConquerSum {
 public static void main(String[] args) {
    int[] arr = new int[]{2, 3, 4, 5};
    System.out.println(calculateRecursiveSum(arr, 0, arr.length));
  }
  static long sum = 0;
  static long calculateRecursiveSum(int[] arr, int low, int high) {
    if (high == low) {
      return arr[0];
    } else {
      int mid = (high + low) / 2;
      sum = calculateRecursiveSum(arr, low, mid) +
            calculateRecursiveSum(arr, mid + 1, high);
    }
    return sum;
  }
}

Может Кто-нибудь, пожалуйста, дайте мне знать, что не так в коде, чтобы решить это? Предполагая только положительные целые числа в этом сценарии.

Answer 1

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

       static long calculateRecursiveSum(int[] arr, int low, int high) {
          if (high == low) {
                return 0;
            }
            int mid = (high + low) / 2;
            return arr[mid] + calculateRecursiveSum(arr, low, mid) + 
                      calculateRecursiveSum(arr, mid+1, high);
       }

Answer 2

Ваш подход был почти нормальным, здесь я исправил несколько проблем, чтобы ваша идея работала.

public class DivideAndConquerSum
{
   public static void main(String[] args)
   {
      int[] arr = new int[] { 2, 3, 4, 5 };
      System.out.println(calculateRecursiveSum(arr, 0, arr.length - 1));
   }

   // static long sum = 0;
   static long calculateRecursiveSum(int[] arr, int low, int high)
   {
      // long sum=0;
      if (high == low)
      {
         return arr[low];
      }
      else
      {
         int mid = (high + low) / 2;
         return (calculateRecursiveSum(arr, low, mid) + calculateRecursiveSum(arr, mid + 1, high));
      }
      // return sum;
   }
}

Вам не нужна дополнительная переменная stati c для хранения результата. Прямой ответ на рекурсивный вызов сделает это за вас.