Return to Answer

Building on @Gankro's answer, notice that when c = X + Y * d, then instead of recursing on (c - d, d) many times, we could do the same in one step: (c - d * Y, d). With this the last lines of the implementation can be improved with:

Building on @Gankro's answer, notice that when c = X + Y * d, then instead of recursing on (c - d, d) many times, we could do the same in one step: (c - d * Y, d). With this the last lines of the implementation can be improved with:

If I can figure out to calculate this properly, I will post again. For now I'd rather not say something stupid.

If I can figure out to calculate this properly, I will post again. For now I'd rather not say something stupid. I would just say that, perhaps the worst case is when you cannot take shortcuts, and have to alternate subtraction from c and d, like with a set of Fibonacci numbers, for example going from (c, d) = (21, 34) to (1, 1):

21, 34
21, 13
8, 13
8, 5
3, 5
3, 2
1, 2
1, 1

But how to express and estimate the complexity of this based on (a, b, c, d), I don't know...

Recursive solutions are limited by the stack

Keep in mind that a recursive solution is not the best way here. You will inevitably get StackOverflowError with large enough N in (1, 1, N, 1), for example on my PC with default settings 9999 is large enough. You can refactor to use a loop instead of recursion, that will work for much larger values of N too.

Complexity

Using this implementation, the worst-case scenario input is:

• Reachable case: \$(1, 1, N, 1)\$ (or the equivalent \$(1, 1, 1, N)\$)
• Unreachable case: \$(2, 2, 2N + 1, 2)\$ (or the equivalent \$(2, 2, 2, 2N + 1)\$), the point being that you will never reach an even number by subtracting even numbers from an odd number.

In both cases it would take \$N\$ iterative steps (whether you use recursion or a loop) to find a positive or negative solution. As such the worst-case complexity is \$O(n)\$.

Building on @Gankro's answer, notice that when c = X + Y * d, then instead of recursing on (c - d, d) many times, we could do the same in one step: (c - Y * d, d). With this the last lines of the implementation can be improved with:

Since we don't know X, use c - d * (c / d - 1) instead of c - d * (c / d), so that we don't overshoot. The Math.max there is to make sure the multiplier is at least 1.

Keep in mind that a recursive solution is not the best way here. You will inevitably get StackOverflowError with large enough N in (1, 1, N, 1), for example on my PC with default settings 9999 is large enough. You can refactor to use a loop instead of recursion, that will work for much larger values of N too.

Building on @Gankro's answer, notice that when c = X + Y * d, then instead of recursing on (c - d, d) many times, we could do the same in one step: (c - d * Y, d). With this the last lines of the implementation can be improved with:

We don't know X and Y, but Y must be between c / d and c / d - 1. So we take c / d - 1, so that we don't overshoot and subtract too much. The Math.max is there is to make sure the multiplier is at least 1.

Complexity

If I can figure out to calculate this properly, I will post again. For now I'd rather not say something stupid.