C#•2y ago

❔ recursive calls result in stackoverflow

Hi I have a connect four game logic that I implemented and I try to find the problem. I have a 6 x 7 array that is initialized with minus one for everyone on each turn I put the player's number where he chose to put say computer 0 player 1 the check is recursive in the form of an asterisk from where the player put the coin to check sequences of his coins. I understand it's because a bad halt check but I don't understand why is that wrong this is the code:

 private int IsHorizontalWin(int x, int y, int playerFlag)
    {
        if (y < 0 || y >= IsFilled.GetLength(0) || x < 0 || x >= IsFilled.GetLength(1) || IsFilled[y, x] != playerFlag || IsFilled[y, x] == -1)
            return 0;
        return 1 + IsHorizontalWin(x + 1, y, playerFlag) + IsHorizontalWin(x - 1, y, playerFlag);
    }
    private int IsVerticalWin(int x, int y, int playerFlag)
    {
        if (y < 0 || y >= IsFilled.GetLength(0) || x < 0 || x >= IsFilled.GetLength(1) || IsFilled[y, x] != playerFlag || IsFilled[y, x] == -1)
            return 0;
        return 1 + IsVerticalWin(x, y - 1, playerFlag) + IsVerticalWin(x, y + 1, playerFlag);
    }

    private int IsDiagonalRightWin(int x, int y, int playerFlag)
    {
        if (y < 0 || y >= IsFilled.GetLength(0) || x < 0 || x >= IsFilled.GetLength(1) || IsFilled[y, x] != playerFlag || IsFilled[y, x] == -1)
            return 0;
        return 1 + IsDiagonalRightWin(x + 1, y - 1, playerFlag) + IsDiagonalRightWin(x - 1, y + 1, playerFlag);

    }

    private int IsDiagonalLeftWin(int x, int y, int playerFlag)
    {
        if (y < 0 || y >= IsFilled.GetLength(0) || x < 0 || x >= IsFilled.GetLength(1) || IsFilled[y, x] != playerFlag || IsFilled[y, x] == -1)
            return 0;
        return 1 + IsDiagonalLeftWin(x + 1, y + 1, playerFlag) + IsDiagonalLeftWin(x - 1, y - 1, playerFlag);

    }

 private int IsHorizontalWin(int x, int y, int playerFlag)
    {
        if (y < 0 || y >= IsFilled.GetLength(0) || x < 0 || x >= IsFilled.GetLength(1) || IsFilled[y, x] != playerFlag || IsFilled[y, x] == -1)
            return 0;
        return 1 + IsHorizontalWin(x + 1, y, playerFlag) + IsHorizontalWin(x - 1, y, playerFlag);
    }
    private int IsVerticalWin(int x, int y, int playerFlag)
    {
        if (y < 0 || y >= IsFilled.GetLength(0) || x < 0 || x >= IsFilled.GetLength(1) || IsFilled[y, x] != playerFlag || IsFilled[y, x] == -1)
            return 0;
        return 1 + IsVerticalWin(x, y - 1, playerFlag) + IsVerticalWin(x, y + 1, playerFlag);
    }

    private int IsDiagonalRightWin(int x, int y, int playerFlag)
    {
        if (y < 0 || y >= IsFilled.GetLength(0) || x < 0 || x >= IsFilled.GetLength(1) || IsFilled[y, x] != playerFlag || IsFilled[y, x] == -1)
            return 0;
        return 1 + IsDiagonalRightWin(x + 1, y - 1, playerFlag) + IsDiagonalRightWin(x - 1, y + 1, playerFlag);

    }

    private int IsDiagonalLeftWin(int x, int y, int playerFlag)
    {
        if (y < 0 || y >= IsFilled.GetLength(0) || x < 0 || x >= IsFilled.GetLength(1) || IsFilled[y, x] != playerFlag || IsFilled[y, x] == -1)
            return 0;
        return 1 + IsDiagonalLeftWin(x + 1, y + 1, playerFlag) + IsDiagonalLeftWin(x - 1, y - 1, playerFlag);

    }

13 Replies

HimmDawg•2y ago

There are a few things that have to be made clear first Why are your methods to check if somebody won returning int And why did you do it recursively

IdoS | Computer ScienceOP•2y ago

ok sorry for the misunderstood. Well the program eventually checks for score of 4 when there is a sequence of 4 I can be sure there is the same coin one after another. recursively was just for an elegant solution because sequentially would have too much if statements and different ways of checking.

HimmDawg•2y ago

Aight, I suspect this to be the culprit IsFilled[y, x] != playerFlag || IsFilled[y, x] == -1 Assuming that playerFlag is 1 Then you ask IsFilled[y, x] != 1 || IsFilled[y, x] == -1 Ah no

Kao•2y ago

Honestly, just avoid recursivity as much as you can dedinside

HimmDawg•2y ago

Right, I can now form a proper english sentence about what I wanted to say goblinnLaugh

the IsHorizontalWin method for example. Assume you are currently counting along 4 connected pieces from the player. That'd mean, you go down the recursive calls, right? So for the first player piece, you check the cells at x+1 and x-1, so we visited x, x-1 and x+1 Then we visit e.g. x+1. If that's also a player piece, we then call the method again for x-1 and x+1. Since we are currently at x+1, then a call to x-1 would result in x So you kinda ping pong between values here The solution would be to check, if the cell was already visited However, as Earl said, this would be a mess and way too much work for something like this 😄

IdoS | Computer ScienceOP•2y ago

yes maybe I should use BFS for that thanks .

HimmDawg•2y ago

There's no need to be fancy. Suppose you put a chip at (x, y). and imagine your grid. The point is somewhere on the grid. And if you draw a horizontal line through it, then it becomes clear, that you'd just need to check for this single line if you want to check for horizontal groups of 4 So a for loop would suffice

Florian Voß•2y ago

@idoscomputerscience it would make more sense to solve this recursively when the chips wouldn't always be in a straight line. If they could be L shaped for example, then it would make lot of sense to use BFS or DFS recursively because you gotta check top, left, bottom, right of each respective cell which could just be a seperate function call. But that's not the case here so a recursive approach IMO doesn't simplify the problem but rather overcomplicate it

IdoS | Computer ScienceOP•2y ago

Alright I just thought to check for nearer neighbors to avoid big complexity by checking all line diagonal horizontal or vertical but thanks but for small grid I guess it doesn't matter that much

HimmDawg•2y ago

It's still a valid approach tho!

IdoS | Computer ScienceOP•2y ago

Indeed It's a project for class and supposing need to impress in job interviews I don't know which approach would have been better for this

Florian Voß•2y ago

in job interviews you don't impress with best optimal algorithms but isntead with problem solving skills. If you can explain well why you have chosen the approach you go with and and how it works, you will impress.

Accord•2y ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

❔ recursive calls result in stackoverflow