Recursive FFT java algorithm returning null?

Question

I'm currently trying to implement the FFT algorithm in java and am having a bit of trouble with it! I've tested all other parts of the algorithm well and they seem to be working fine.

The trouble I'm getting is that in the base case it returns a Complex number array, within the base case A[0] is populated. After the base cases have been executed, the for loop is executed where y0[0] and y1[0] are found to be null, despite assigning them to the base cases, pretty confused by this. This is shown in the System.out.println line

Can anyone tell me the errors of my ways?

    //This method implements the recursive FFT algorithm, it assumes the input length
//N is some power of two
private static Complex[] FFT(Complex[] A, int N) { 
    double real, imag;
    Complex A0[] = new Complex[((int) Math.ceil(N/2))]; 
    Complex A1[] = new Complex[((int) Math.ceil(N/2))];
    Complex[] omega = new Complex[N];
    Complex[] y = new Complex[N];
    Complex[] y0 = new Complex[((int) Math.ceil(N/2))];
    Complex[] y1 = new Complex[((int) Math.ceil(N/2))]; 

    //base case
    if (N == 1) {
        return A;
    }
    else {
        real = Math.cos((2*Math.PI)/N); if (real < 1E-10 && real > 0) real = 0;
        imag = Math.sin((2*Math.PI)/N); if (imag < 1E-10 && imag > 0) imag = 0;
        omega[N-1] = new Complex(real, imag);
        omega[0] = new Complex(1, 0);
        A0 = splitInput(A, 1);
        A1 = splitInput(A, 0);
        //recursive calls
        y0 = FFT(A0, N/2);
        y1 = FFT(A1, N/2);
        for (int k = 0; k < ((N/2)-1); k++) {
            System.out.print("k: " + k + ", y0: " + y0[k]); System.out.println(", y1: " + y1[k]);
            y[k] = y0[k].plus(omega[k].times(y1[k]));
            y[k+(N/2)] = y0[k].minus(omega[k].times(y1[k]));
            omega[0] = omega[0].times(omega[N]);
        }
        return y;
    }
}

Here is the code for my splitInput method as requested

//This method takes a double array as an argument and returns every even or odd
//element according to the second int argument being 1 or 0
private static Complex[] splitInput(Complex[] input, int even) {
    Complex[] newArray = new Complex[(input.length/2)];

    //Return all even elements of double array, including 0
    if (even == 1) {
        for (int i = 0; i < (input.length/2); i++) {
            newArray[i] = new Complex(input[i*2].re, 0.0);
        }
        return newArray;
    }
    //Return all odd elements of double array
    else {
        for (int i = 0; i < (input.length/2); i++) {
            newArray[i] = new Complex (input[(i*2) + 1].re, 0.0);
        }
    return newArray;
    }
}

EDIT: I've updated my code according to your suggestions, still getting a null pointer exception from the line y[k] = y0[k].plus(omega[k].times(y1[k])); as y0 & y1 are still null after the base case :( any further ideas? Here's the updated algorithm

//This method implements the recursive FFT algorithm, it assumes the input length
//N is some power of two
private static Complex[] FFT(Complex[] A, int N) { 
    double real, imag;
    Complex[] omega = new Complex[N];
    Complex[] y = new Complex[N];
    Complex[] A0;
    Complex[] A1;
    Complex[] y0;
    Complex[] y1;

    //base case
    if (N == 1) {
        return A;
    }
    else {
        real = Math.cos((2*Math.PI)/N); if (real < 1E-10 && real > 0) real = 0;
        imag = Math.sin((2*Math.PI)/N); if (imag < 1E-10 && imag > 0) imag = 0;;
        omega[N-1] = new Complex(real, imag);
        omega[0] = new Complex(1, 0);
        A0 = splitInput(A, 1);
        A1 = splitInput(A, 0);
        //recursive calls
        y0 = FFT(A0, N/2);
        y1 = FFT(A1, N/2);
        for (int k = 0; k < ((N/2)-1); k++) {
            y[k] = y0[k].plus(omega[k].times(y1[k]));
            y[k+(N/2)] = y0[k].minus(omega[k].times(y1[k]));
            omega[0] = omega[0].times(omega[N-1]);
        }
        return y;
    }
}

Answer 1

A few thoughts:

Any time I see something repeated as often as Math.ceil(N/2) is here, I think it justifies having its own named variable. (I know naming variables isn't always easy, but I find it vital for legibility.)

Complex A0[] = new Complex[((int) Math.ceil(N/2))];
Complex A1[] = new Complex[((int) Math.ceil(N/2))];

Note that when N==1, the computation results in new Complex[0]. I'm not sure what this does, but I think I'd put the N == 1 base-case check before the memory allocations.

Complex[] y0 = new Complex[((int) Math.ceil(N/2))];
Complex[] y1 = new Complex[((int) Math.ceil(N/2))];
/* ... */
    y0 = FFT(A0, N/2);
    y1 = FFT(A1, N/2);

I believe you can skip the new Complex[...] allocations for these arrays because you never actually store anything into them.

Complex[] omega = new Complex[N];
/* ... */
        omega[0] = omega[0].times(omega[N]);

I'm surprised this hasn't blown up yet -- omega[N] should raise an IndexOutOfBounds exception.