Parity - Recursion java

I have the Parity checker problem: A binary string is a string that contains only '0' and '1'characters. The parity of a binary string is defined as follows. If the number of times that the character '1' appears in this string is even, the parity it 0; if it’s odd, the parity is 1. For example, the parity of "101" is 0, the parity of "10110" is 1, and the parity of "001001101" is 0. Write a function, using the signature

public static int parity(String binaryStr)
//no changes are allowed & only use recursive solution, no loops allowed

I managed to write it iteratively however my recursion is out of outOfboundries:

  public static int parity(String binaryStr) {
    int counter = 0;
    for (int i = 0; i < binaryStr.length () ; i++) {
        if (binaryStr.charAt (i) == 49) {
            counter++;
        }
    }
    if ( counter % 2 == 0 ) {
        return 0;
    }
    else {
        return 1;
    }
}

recursive:

private static int index = 0;
private static int ans = 0;

private static int parity(String binaryStr) {
    if ( index == binaryStr.length ()-1 ) {
        if ( ans % 2 == 0 ) {
            return 0;
        }
        else {
            return 1;
        }
    }
    else if ( binaryStr.charAt (index) == '1' ) {
        ans++;
        return parity (binaryStr.substring (index++));
    }
    return  parity (binaryStr.substring (index++));
}

please help me correct it

Solution

The major issue with your code is passing binaryStr.substring (index++) to the recursive call, which passes the original String instead of a substring. Hence you get infinite recursion. You can use ++index.

Instead of using static variables, I suggest the following:

private static int parity(String binaryStr) {
    if (binaryStr.length() == 0) {
        return 0;
    } else {
        return ((binaryStr.charAt(0) == '0') ? 0 : 1) ^ parity(binaryStr.substring(1));
    }
}

Explanation:

If the two operands of bit-wise XOR (^) are equal, it returns 0. If one operands is 0 and the other is 1, it returns 1.

That's exactly the logic you need:

If the first character is '1' and the rest of the String has parity 1 (i.e. odd number of '1's), the whole String's parity is 0.

If the first character is '1' and the result of the String has parity 0 (i.e. even number of '1's, the wholeString`'s parity is 1.

If the first character is '0', the parity of the whole String is the same as the parity of the rest of the String.