java complex if statement causes StackOverflowError

Question

I made a recursive method to find the least number of rallies that could be played before one or another team wins with given points team should score to win - k, current points of two teams - x and y.

So it looked like

public static int scores(int k, int x, int y, int rally) {
    if (x==k || y==k)
        return rally;
    else {
        rally++;
        return Math.min(scores(k, x + 1, y, rally), scores(k, x,y+1,rally));
    }
}

When I called this method with custom values in main method

scores(5,0,0,0)

It worked fine. But when I changed IF statement to check that the winner has at least two-point margin

if ((x==k || y==k) && Math.abs(x-y)>=2)

The program showed java.lang.StackOverflowError

I am extremely bad at this, please help me

You added one additional condition to the exit from recursion. As a result the method don't exit and invokes scores() until the exception — Maxim, Sep 16 '18 at 18:06
Take note that you never increase k value, that means that if x/y == k and difference isn't 2 points, it will pass on and x/y will never equal k again. — Worthless, Sep 16 '18 at 18:07
I don't see the difference between `if ((x==k || y==k) && (Math.abs(x-y))>=2)` and `if ((x==k || y==k) && Math.abs(x-y)>=2)`. (Other than the unnecessary brackets being removed). — Andy Turner, Sep 16 '18 at 18:08
[I downvoted because there was no effort to debug the code](http://idownvotedbecau.se/nodebugging/), e.g. printing the values of `k`, `x`, `y`, and `rally` inside the method. — Andreas, Sep 16 '18 at 18:08
Isn't the solution just trivially `Math.max(2, k)`? (The minimum number of rallies is where X always beats Y, or vice versa). No recursion needed. — Andy Turner, Sep 16 '18 at 18:25
@AndyTurner oh right, I messed up and pasted wrong code block — Ольга Кужикова, Sep 18 '18 at 13:19
@ОльгаКужикова after your edit, the answer is simply `k`. — Andy Turner, Sep 18 '18 at 13:20

score 2 · Answer 1 · edited Sep 16 '18 at 18:39

2

Take note that you never increase k value, that means that if x/y == k and difference isn't 2 points, it will pass on and x/y will never equal k again.

I will imagine that something like this, should work

public static int scores(int k, int x, int y, int rally) {
    if ((x>=k || y>=k) && (Math.abs(x-y))>=2)
        return rally;
    else {
        rally++;
        return Math.min(scores(k, x + 1, y, rally), scores(k, x,y+1,rally));
    }
}

Edit: As pointed out in the comments, there is another issue with this code, that causes SO when opposite players get one point each all the time.

You can fix the stack overflow error that occurs when X and y alternate in "winning" by keeping track of the minimum found so far:

public static int scores(int k, int x, int y, int rally) {
  return scores(k, x, y, rally, Integer.MIN_VALUE);
}

public static int scores(int k, int x, int y, int rally, int minSoFar) {
    if (rally >= minSoFar || ((x>=k || y>=k) && (Math.abs(x-y))>=2))
        return rally;
    else {
        rally++;
        minSoFar = Math.min(minSoFar, scores(k, x+1, y, rally));
        minSoFar = Math.min(minSoFar, scores(k, x, y+1, rally));
        return minSoFar;
    }
}

But it should be noted that the minimum path will always be the one where X always wins (or Y always wins). So:

return Math.max(2, k);

Is a much easier way to express the result.

edited Sep 16 '18 at 18:39

Andy Turner

137,514
11
162
243

answered Sep 16 '18 at 18:10

Worthless

531
3
7

This code will generate the same stack overflow exception, x or y being larger than k is irrelevant here. – Joakim Danielson Sep 16 '18 at 18:15
@JoakimDanielson are you thinking of the [Isner-esque situation](https://www.teamusa.org/News/2018/July/13/After-Second-Longest-Grand-Slam-Match-Ever-John-Isner-Falls-Just-Short-Of-Wimbledon-Final) of the increment x, increment y, increment x, increment y (etc) path? – Andy Turner Sep 16 '18 at 18:20
@JoakimDanielson I like how you point it out as irrelevant - when its one of problems with this code that causes SO. I will admit to my answer being incomplete (Didn't test it), but its not irrelevant. – Worthless Sep 16 '18 at 18:24
@AndyTurner yea, thats the second part (that I missed) - we end up always going back to equal scores. – Worthless Sep 16 '18 at 18:25
Yes you're right. The second part of my comment was _irrelevant_ – Joakim Danielson Sep 16 '18 at 18:38
@Worthless I've tacked on a lot to your answer, because I couldn't post my own. Hope that's ok. – Andy Turner Sep 16 '18 at 18:39

java complex if statement causes StackOverflowError

1 Answers1