Writing recursive method to compare even and odd digits within number

Question

Basically, I am trying to write a method where a number is inputted and if there are more odd digits than even digits in the number, it returns "true", and else, false. I think I need to use tail recursion but I cannot figure it out.

public static boolean moreOddThanEven(int x) {
    if (x == 0) {
        return false;
    }
    if (x % 2 == 0) {
        return moreOddThanEven(x / 10);
    } else {
        return moreOddThanEven(x / 10);
    }
}

public static boolean moreOddThanEven2(int x) {
    return moreOddThanEvenTR(x, 0, 0);
}

public static boolean moreOddThanEvenTR(int x, int odd, int even) {
    if (x == 0) {
        return false;
    }
    if (x%2==0) {
        return moreOddThanEvenTR(x / 10, odd, even+1);
    }
    if (x%2!=0) {
        return moreOddThanEvenTR(x / 10, odd+1, even);
    }

    if (odd <= even) {
        return false;
    } else {
        return true;
    }
}

Answer 1

If you have an easier time thinking about loops than tail recursion, it's worth knowing that you can translate any loop into tail recursion (and vice versa, but that's different topic). First, we need to get the loop into this shape:

initialize a, b, ... 
while (<some condition on a, b, ...>) {
  Update a, b, ... using old values of a, b, ...
}
return <any function of a, b ...>

it translates to:

TypeOfReturn while_loop(TypeOfA a, TypeOfB b, ...) {
  if (!(<some condition on a, b, ...>)) {
    return <any function of a, b, c ...>;
  }
  Update a, b, ... using old values of a, b, ...
  return while_loop(a, b, ...);
}

Let's apply this to your problem. As a loop:

// x is the input
int oddMinusEven = 0;
while (x) {
  oddMinusEven += 2 * (x % 2) - 1;
  x /= 10;
}
return oddMinusEven > 0;

We get:

bool hasMoreOddThanEvenDigits(int x, int oddMinusEven) {
  if (!x) return oddMinusEven > 0;
  oddMinusEven += 2 * (x % 2) - 1;
  x /= 10;
  return hasMoreOddThanEvenDigits(x, oddMinusEven);
}

We can clean this up a bit to make it less verbose:

int hasMoreOddThanEvenDigits(int x, int oddMinusEven) {
  return x ? hasMoreOddThanEvenDigits(x / 10,  oddMinusEven + 2 * (x % 2) - 1) : oddMinusEven > 0;
}

We run the loop with a "top level" function call that initializes variables:

return getMoreOddThanEvenDigits(x, 0) > 0;

It's fun to see what a good compiler does with the two codes. As you'd expect, they lead to nearly identical machine code. If we can do a rule-based transformation, so can the compiler.

Answer 2

Recursion is not needed (nor is more than one line):

public static boolean moreOddThanEven(int x) {
    return (""+x).replaceAll("[02468]", "").length() > ((int) Math.log10(x)+1) / 2;
}

or the longer, but non-mathy version:

public static boolean moreOddThanEven(int x) {
    return (""+x).replaceAll("[02468]", "").length() > ((int) (""+x).replaceAll("[13579]", "").length();
}

Answer 3

There is a simple reason why you are stuck: you have to count the evens/odds like in 77778888888999. In fact you need to count the sum of (odds - evens), the oddity.

public static boolean moreOddThanEven(int x) {
    assert x >= 0;
    return x != 0 && oddity(x) > 0;
}

private static int oddity(int x) {
    if (x == 0) {
        return 0;
    }
    if (x % 2 == 0) {
        return oddity(x / 10) - 1;
    } else {
        return oddity(x / 10) + 1;
    }
}

Answer 4

I think using tail recursion is the right idea. Here is my attempt, assuming we can use more than one parameter in the recursive function:

public static boolean compareOddEven(int x, int count) {
    //This is when we reach the end of the recursion (ones place).
    if(x<10) {
        //if odd, add 1, if even subtract 1
        count += (x%2==1) ? 1 : -1;
        return count>0;
    }
    else{
        int digit = x;
        
        //We use this loop in order to get the leftmost digit and read whether it is odd or even. 
        //Subsequently, we add or subtract 1 to the count based on the digit's parity and we pass this count into the next recursion in order to keep track.
        while (digit > 9) {
            digit /= 10;
        }
        count += (digit%2==1) ? 1 : -1;

        //Get rid of the first digit to get next number to use in recursive call.
        int removedFirstDigit = x % (int) Math.pow(10, (int) Math.log10(x));

        //tail recursion
        return compareOddEven(removedFirstDigit, count);
    }
}

Explanation. We can accomplish this with just one method if we keep track of the count of odd and even digits the second parameter of the method. It will be less cumbersome to keep track of the count rather than keeping track of both counts of the odd and even numbers (and avoids the comparisons at the end which would not make it a tail recursion).

With this in mind, our approach is to start at the leftmost digit of the number we input and move to the right with each new recursive call. It is possible to start from right and go left in counting the parity of the digits as well.

So with every new recursive call, we pass in the count to the function as an argument. When we finally reach the ones digit, the nonnegativity of the count tells us whether there are more odd or even digits. To see this more clearly, I recommend printing out some of the arguments right before the recursive call is made.

Further note that when we reach the ones place, the truth value of count>0 will be propagated up the chain of recursive calls to give the final result that we desire.

Example call:

System.out.println(compareOddEven(21468233, 0));

Output:

false