StackOverFlowError w/ Recursive Sort

Question

I'm getting a StackOverFlowError when I try and use my recursive sort on an array that has a length that is greater than around 50. The method sorts properly if the array is small enough to not throw this error. Is there any way around this?

public class RecursiveSort
{
    static double[] arr;
    static int count = 0;
    public static void main(String[] args)
    {
        double[] anArr = new double[50];

        for(int i = 0; i < anArr.length; i++) {

            anArr[i] = Math.random();

        }



        arr = anArr;
        recurseSort(arr.length - 1);
        display();
    }

    public static void recurseSort(int position)
    {

        if(position == 0)
        {
            position = arr.length - 1;
            count++;
        }
        if (arr[position] < arr[position - 1])
        {
            double n = arr[position - 1];
            arr[position - 1] = arr[position];
            arr[position] = n;
        }

        if(count <= arr.length)
            recurseSort(--position);

    }

    public static void display()
    {
        for(double n : arr)
            System.out.println(n);
    }

}

Answer 1

Your recursion is tail recursion so you may replace it with do-while

public static void recurseSort(int position)
    {

      do{

        if(position <= 0)
        {
            position = arr.length - 1;
            count++;
        }
        if (arr[position] < arr[position - 1])
        {
            double n = arr[position - 1];
            arr[position - 1] = arr[position];
            arr[position] = n;
        }


       position--;

       }while(count <= arr.length); //end while

    }

Answer 2

First of all, you seem to implement some kind of bubble sort. I have never any attempt to this using recursion, and don't see any point in doing so, as implementing this algorithm is generally straight-forward and consists of two nested loops, the inner of which conditionally swapping adjacent list elements. I don't see any way of recursive approach for that...

Not surprisingly, what you do there is not really recursion, as you are operating exclusively on static class members (arr, count) of constant dimensions. The beauty of recursion in sorting algorithms, however, is the reduction of respective parameter complexity at each recursion step; by having a method, getting passed an unsorted list as a parameter calling itself two times after splitting said list into two, sorting each of these two subsets becomes much easier every times the method is called. Such a method could look somewhat like this:

private static double[] sort(double[] arr) {
  int splt = arr.length >> 2;
  // terminate if sorting is trivial
  if (splt < 3) {
    if (splt < 2) return arr;
    if (arr[0] > arr[1]) {
      return new double[2]{arr[1], arr[0]};
    } else return arr;
  }
  // split array and sort separately
  double[] left = new double[splt];
  double[] rght = new double[arr.length-splt];
  System.arraycopy(arr, 0, left, 0, splt);
  System.arraycopy(arr, splt, rght, 0, rght.length);
  return mergeArraysSomehow(sort(left), sort(right));
}

Appropriate division can limit recursion depth to log(n), where n is array length. What you are doing is keeping on having a method call itself when it should actually just continue going through a loop. Every time recurseSort calls itself, its bytecode, parameters and private variables are copied onto the stack, without any invocation ever returning and thus freeing stack memory! It is only when the the stack is holding n² calls of recurseSort, that the method calls can start returning. An n of value 50 can suffice [since being squared] to fill up and exceed the entire stack size like this.

If you must do this recursively, at least stop recursing as soon as arr doesn't require any more swapping of elements. Or forget about bubble sort and implement quick sort or merge sort instead.

Answer 3

Problem is that recursion is based in defining two steps, a stopping step (or base case) and a recursion step. In the latter, you need to solve the whole problem using a recursion call, but with a smaller problem. For example, multiplication can be accomplished by summing up the same number as many times as the multiplier indicates (4 times 5 means summing up 4 as many times as 5). If you do it recursively it would be:

int multiply(int n, int multiplier)
{
    // Stopping step or base case
    if (multiplier == 1) return n;

    // Recursion step: Solving the whole problem using a recursion call
    return n + multiply(n, multiplier - 1);

}

In your program you have the base case, but in the recursion step you're not solving the whole problem. This is, you swap arr[position] and arr[position - 1] if they should be swapped, but this doesn't guarantee that the whole subarray in the recursive call will be ordered. If you solve the whole problem, you solve the recursion problem. This is why the quicksort algorithm (and others) split the array choosing an element, and putting every other element smaller than this to its left, and every other element bigger to its right to, finally, calling itself recursively to order both halves of the array.

Of course, this is besides problems J. Katzwinkel described.