finding the minimum operations to get from x to y

Question

still struggling with recursion. I have a code that's supposed to get me the least amount of operations in order to get from x to y. only by multiplying by 2 or adding +1 e.g from 7 to 12... its 5 operations because you need +1 five times. My code is not working correctly for me, and I can't figure out what I'm missing in order for it to be right.

public static int minOps(int x,int y)
{
    if (x >= y) return 0;
        int add = 1 + minOps(x + 1, y);
        int mul = 1 + minOps(x * 2, y);
    return Math.min(add, mul);
}

Answer 1

@arjunkhera's answer has the right idea - return a "terrible" result when you've overshot, so you never select it - but needs to avoid the potential overflow when adding 1 to the result:

public static int minOps(int x,int y)
{
    // Return 1 less that MAX_VALUE, so adding 1 doesn't overflow.
    // You'll never get as far as here anyway, your stack will overflow long
    // before, so subtracting 1 makes no practical difference.
    if (x > y) return Integer.MAX_VALUE - 1;
    if (x >= y) return 0;

    int add = 1 + minOps(x + 1, y);
    int mul = 1 + minOps(x * 2, y);
    return Math.min(add, mul);
}

Alternatively, you could defer adding 1 until later:

    if (x > y) return Integer.MAX_VALUE;
    if (x >= y) return 0;

    int add = minOps(x + 1, y);
    int mul = minOps(x * 2, y);
    return 1 + Math.min(add, mul);

since at least one of add and mul will not be equal to MAX_VALUE.