EDIT: Here is a linear time algorithm based on an optimization to Simon's!
Algorithm
We assume that the input consists of non-negative integers.
Simon's algorithm is an excellent improvement which does great on problems whose solution "alternates" between the two choices frequently, but performs very poorly for solutions which consist of long "streaks" of making the same choice. This is observed in the solution a=1, b=1, c=n, d=1. Simon's algorithm will count down from \$n\$ to \$1\$, which is an exponential running time (in terms of bits required to represent the input).
The solution is then to "compress" these paths.
As with Simon's algorithm, we start with c and d, and identify which is the largest. Say it's c (if not, simply apply symmetric reasoning). So then the previous step in any solution must have been to increase c by d. However, unlike Simon's algorithm, we will identify how many times this was the case. This is simple: it's just how many times larger c is than d, or c/d (using integer division). So instead of recursing on c-d, d, we then recurse on c - d*(c/d), d.
However we may now possibly "skip over" the starting position (a,b) we are seeking. This is, fairly easy to detect, though. We just return if b==d and (c - a)%d == 0.
Finally, a corner case not mentioned by Simon, which is necessary to consider when you allow \$0\$ as valid input (Simon does not, so his algorithm is fine): c == d. If this is the case, then there are in fact two valid previous steps: 0, d and c, 0. We must check if our solution is either of these, and then simply terminate.
Analysis
At each step, one of our two numbers shrinks by at least half (the worst case being when \$c = 2d - 1\$). Our algorithm terminates at worst when both numbers are 0. Thus, after \$O(\log c + \log d)\$ time the algorithm must terminate. This is linear in the size of the input.
This can be done in \$O(1)\$ space using a loop or tail recursion.
Code
Finally, here is my implementation in Java (compiled and tested for a few inputs)
public static boolean hasSolution(int a, int b, int c, int d){
if(a < 0 || b < 0 || c < 0 || d < 0){
throw new IllegalArgumentException("Negative inputs are not allowed");
}
if(c == 0 || d == 0){
//This is a fixed point, an inescapable blackhole!
return a == c && b == d;
}
while(true){
if(a == c && b == d){
//We're done!
return true;
}else if(c == d){
//weird corner case
return hasSolution(a, b, 0, d) || hasSolution(a, b, c, 0);
}else if(c > d){
int next = c - d*(c/d);
if(next < a){
//we're going to overshoot!
// Check if there exists a k such that
// a + k*d == c
return b == d && (c - a)%d == 0;
}else{
//recurse!
c = next;
}
}else{
//No really, c is > d
int temp;
temp = a; a = b; b = temp;
temp = c; c = d; d = temp;
}
}
}
Original Answer (a brief analysis of the OP's algorithm):
Here is a really bad example for your program:
a=1, b=1, c=999999999, d=1
Your program will continually follow the first recursive step until it has counted from a to c, and then return true.
Your program will run in \$\Omega(c)\$ time, which most would generally regard as "exponential", as it is exponential in the number of bits required to represent the input. In addition, your program will require \$\Omega(c)\$ space, as the first branch of your recursion cannot be tail-call optimized, so each iteration will push an entire stack-frame on top. So your space consumed is also exponential in the actual input size. Naive translation of this algorithm to be non-recursive (with a loop and a stack) would not solve this problem.
Note that this is only for this input. I have no idea what the true asymptotic running time of this algorithm is, because weirder inputs have weirder behaviours, and it's not clear to me what exactly the true worst case is. You're essentially doing depth-first search on a binary tree that can be something like \$O(c/b + d/a)\$ nodes deep. So that's definitely the worst-case on space (as exhibited by my example), but running time is unclear. The number of nodes in such a tree can be as much as \$2^{depth}\$, so maybe there's an input that exhibits \$\Omega(2^{c+d})\$ running time, (which is doubly exponential in input size) but I'm unclear as to how to trigger that (if possible). I'm inclined to think that there aren't nearly that many nodes in the tree, as the "middle" of the tree thins out much more rapidly than the sides (there are definitely always branches that are \$O(\log{(c + d)})\$ deep. You can always force the algorithm to search the whole tree by making the answer "no", though (assuming @janos's improvement that terminates when the correct answer is found).
If I had to guess, something like
a=2, b=2, c=2n+1, d=2n+1
exhibits the worst-case behaviour.
I believe the recurrence tree would something like the left- and right-most branches being size \$n\$, the next most outward branches are size \$n/2\$, then \$n/4\$, and so on (halving) until we reach two middle branches of size \$1\$. This gives us about \$4n\$ nodes, which is assymptotically the same as \$n\$. Thus I conjecture the algorithm "only" runs in exponential time and space in the worst case.
Simon's answer is, regardless, much better, and is also much easier to analyse (though it's still exponential in the worst-case).
a=0, b=1, c=1, d=1. It loops forever. But yes, this is a faithful interpretation of Simon's algorithm. It still takes exponential time on the inputa=1, b=1, c=n, d=1, though. To fix that would require a different algorithm such as the one suggested in my answer. \$\endgroup\$