java - 二进制递归错误消息 : StackOverflowError

Question

当我运行以下程序时，我收到以下错误:(有什么想法吗？)

Exception in thread "main" java.lang.StackOverflowError
at SumArray.binarySum(SumArray.java:31)
at SumArray.binarySum(SumArray.java:34)

<小时/>

这是代码:我需要生成一个随机整数数组，并使用二进制和线性递归来添加其值...

import java.io.*;
import java.util.ArrayList;
import java.util.Random;

class SumArray {
    static int floor = 100000;
    static int ceil = 0; 
    int result;
    int half; 
    int half2;

    //Linear Recursion
    int sum(int a[], int n) {
        if (n == 1)
            return a[0];
        else {
            result = sum(a, n - 1);
            result = result + a[n - 1];
            return result;
        }
    }

    //Binary Recursion
    int binarySum(int a[], int i, int n) {
        if (n == 1)
            return a[0];

        return binarySum(a, i, ceil/2) + binarySum(a, i + ceil/2, floor/2);
    }

    public static void main(String args[]) throws IOException {

        //Define ArrayList to hold Integer objects
        ArrayList<Integer> numbers = new ArrayList<Integer>();

        // User determines number of elements
        DataInputStream dis = new DataInputStream(System.in);
        System.out.println("Hello! Please enter the size of your array: ");
        int n = Integer.parseInt(dis.readLine());

        // Generate specified number of random integers
        Random randNumGenerator = new Random();
        int[] x = new int[n];

        // While still less than indicated number.. add more
        for (int i = 0; i < x.length; i++) {
            x[i] = (randNumGenerator.nextInt(100000));
            numbers.add(x[i]);

            //calculate min and max values
            if(ceil < x[i]) {
                ceil = x[i];
            }
            if(floor > x[i]) {
                floor = x[i];
            }
        }

        SumArray a1 = new SumArray();

        // Print array values
        System.out.println("Array values inlude: " + numbers);

        // Print the sum
        System.out.println("The sum of the array using Linear Recursion is: " + a1.sum(x, n));

        // Print the binary sum
        System.out.println("The sum of the array using Binary Recursion is: " + a1.binarySum(x, n, n));

        System.out.println("Ceiling: " + ceil);
        System.out.println("Floor: " + floor);
    }
}

Answer 1

您正在递归调用 BinarySum 方法，其第三个参数为 ceil/2 和 Floor/2，这永远不会改变。 ceil/2 为 0，floor/2 为 50000，这两个都不是 1，因此您将获得无限递归。看起来您可能希望每个递归调用的这些值都不同......

我的 Java 有点生疏(也许更习惯用 Java 编码的人可以解决这个问题)，但作为一个例子，尝试这样的事情:

class Accumulator {
  static int binarySum(int a[]) {
    return binarySum(a, 0, a.length-1);
  }

  static int binarySum(int a[], int s, int e) {
    if (e-s == 0) return a[s];
    int mid = s + ((e-s)/2);
    return binarySum(a, s, mid) + binarySum(a, mid+1, e);
  }

  public static void main(String args[]) {
    int[] vals = {2,3,4,5,6,7};
    System.out.println(binarySum(vals));
  }
}

对于每次调用，我们将搜索内容分成两半并递归，直到找到单个项目。