Recursive splitting array method

Question

I'm trying to write a recursive method that takes an integer array and copies alternating elements into two separate arrays until there are no elements left to split.

For example:

[0 1 2 3 4 5 6 7 8 9]  
...  

[0 2 4 6 8]
[1 3 5 7 9] / 
[0 4 8]
[2 6] / 
[0 8]
[4] / 
[0]
[8] / 
[2]
[6] / 
[1 5 9]
[3 7] / 
[1 9]
[5] / 
[1]
[9] / 
[3]
[7]

So far I have been able to split the initial array, but my recursion won't terminate. Any suggestions?

Here is the method's code:

public static void halve(int[] a, int x)
{
    for (int i = 0; i < x; i = i + 2)
    {
        xList[i/2] = i;
        yList[i/2] = i + 1;
    }

    printList(xList);
    printList(yList);

    if (x-1 > 2)
        halve(xList, xList.length-1);
    else if (x-1 > 2)
        halve(yList, yList.length-1);
}

What is xList and yList?

Anton Savin
– Anton Savin

2014-09-15 22:20:42 +00:00
Commented Sep 15, 2014 at 22:20 — Anton Savin
– Anton Savin, Commented Sep 15, 2014 at 22:20

Anton Savin · Accepted Answer · 2014-09-18 09:07:58Z

2

It seems that xList and yList are int[]s. In that case xList.length-1 and yList.length-1 always return the same numbers so argument x for halve is always greater than 3 and your recursion never stops.

This is not to mention other problems like:

You are filling xList and yList with indices instead of elements of a.
The i + 1 is going out of bounds if x is odd.
The same conditions for if and else if - you definitely meant something else.

edited Sep 18, 2014 at 9:07

answered Sep 15, 2014 at 22:24

Anton Savin

41.4k8 gold badges57 silver badges94 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

jsurf · Accepted Answer · 2014-09-15 22:57:38Z

Ok this code outputs the results you wanted:

public class Recursive {
private static int[] array = {0,1,2,3,4,5,6,7,8,9};

public static void main(String[] args){
    half(array);
}
public static void half(int[] array){
    int[] evenarray,oddarray;
    if(array.length%2==1){
        evenarray = new int [array.length/2+1];
        oddarray = new int[array.length/2];
    }else{
        evenarray = new int [array.length/2];
        oddarray = new int[array.length/2];
    }
    for (int i=0; i<array.length; i++){
        if(i%2==0){
            evenarray[i/2]=array[i];
        }else{
            oddarray[i/2]=array[i];
        }
    }
    for(int i = 0; i<evenarray.length; i++){
        System.out.print(evenarray[i]);
    }
    System.out.println();
    for(int i = 0; i<oddarray.length; i++){
        System.out.print(oddarray[i]);
    }
    System.out.println();
    if(evenarray.length>1)half(evenarray);
    if(oddarray.length>1)half(oddarray);

}}

Collectives™ on Stack Overflow

Recursive splitting array method

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related