CODEWITHSUNDEEP
javarecursion
Kayla0x41
Kayla0x41

Reputation: 105

BinaryRecursion Error message: StackOverflowError

When I run the below program I am getting the following errors: (any ideas?)

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

Here is the code: I need to generate an array of random integers and use binary and linear recursion to add the values thereof... 

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

Upvotes: 0

Views: 381

Answers (3)

Philip Uren
Philip Uren

Reputation: 356

You're recursively calling your BinarySum method with it's third parameter as ceil/2, and floor/2 which will never change. ceil/2 is 0 and floor/2 is 50000, neither of these is 1, so you're getting infinite recursion. Seems like you probably want those values to be different for each recursive call...

My Java is a little rusty (maybe somebody more used to coding in Java can clean this up), but as an example, try something like this:

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

For each call we split what we're searching into two halves and recurse, until we get down to a single item.

Upvotes: 2

A.H.
A.H.

Reputation: 66273

binarySum gets an parameter n which is not used inside the function. Therefore your recursion does not split the work into two parts and therefore never ends.

Also: You are mixing array indices (n, i) with the contents of the array (ceil, floor). This is also quite simply wrong.

Hint: Insert a System.out.println at the start of binarySum which prints out all relevant variables. You will quickly see what's wrong.

Upvotes: 0

Miquel
Miquel

Reputation: 15675

In binary sum, if n==0, you will continue to recurse infinitely, and eventually run out of stack space. Try fixing that, see if it helps. Good luck!

Upvotes: 1

Related Questions