I'm getting a stackoverflow error when I use a for loop, but if the same thing is done using an if block, it doesn't produce the error

php editor Strawberry takes you to explore a common problem in Java programming: a stackoverflow error occurs when using a for loop, but no error occurs when using an if block. This phenomenon may result from repeated calls of the for loop causing stack overflow, and the if block avoids this situation. This problem can be better understood and solved by in-depth analysis of the root cause of the problem and the Java memory management mechanism.

Question content

I am solving the dsa problem

The language I use is java se

Link: https://www.codingninjas.com/studio/problems/ninja-s-training_3621003

I know my solution is correct, but for one of the test cases (I don't know what a test case is because it doesn't show test cases) I got a stackoverflow error, so I just replaced the for loop with some if statements , it's fixed, I'm wondering why I got the error

in the first place

The same solution in c (using for loop) also works without errors, does stack space work differently in java and c?

The amount of function calls in both methods remains the same, but one of the methods gives a stackoverflow error, which doesn't make sense. So the number of calls cannot exceed the stack space, it would be great if someone could solve this problem for me

This is the code with for loop:

public class solution {
    private static int dp[][];
    private static int rec(int day, int prev, int[][] points) {
        if (day == 0) {
            // no more days left.
            return 0;
        }

        if (dp[day][prev] != -1) {
            return dp[day][prev];
        }

        // merit points of ith task on nth day.
        int ans = points[day - 1][prev - 1];
        int mx = 0;
        for(int k=1;k<4;k++)
        {
            if(k!=prev)
            {
                int cur=rec(day-1, k, points);
                mx=math.max(cur,mx);
            }
        }
        

        dp[day][prev] = ans + mx;
        return ans + mx;
    }

    public static int ninjatraining(int n, int points[][]) {
        // dp table to memoize the solution.
        dp = new int[n + 1][4];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 4; j++) {
                dp[i][j] = -1;
            }
        }
        int ans = 0;
        ans = math.max(ans, rec(n, 1, points));
        ans = math.max(ans, rec(n, 2, points));
        ans = math.max(ans, rec(n, 3, points));

        return ans;
    }
}

Here is the code with the if block:

public class Solution {
    private static int dp[][];
    private static int rec(int day, int prev, int[][] points) {
        if (day == 0) {
            // No more days left.
            return 0;
        }

        if (dp[day][prev] != -1) {
            return dp[day][prev];
        }

        // Merit points of ith task on nth day.
        int ans = points[day - 1][prev - 1];
        int mx = 0;
        
        if (prev == 1) {
            mx = Math.max(rec(day - 1, 2, points), rec(day - 1, 3, points));
        }

        if (prev == 2) {
            mx = Math.max(rec(day - 1, 1, points), rec(day - 1, 3, points));
        }

        if (prev == 3) {
            mx = Math.max(rec(day - 1, 1, points), rec(day - 1, 2, points));
        }

        dp[day][prev] = ans + mx;
        return ans + mx;
    }

    public static int ninjaTraining(int n, int points[][]) {
        // DP table to memoize the solution.
        dp = new int[n + 1][4];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 4; j++) {
                dp[i][j] = -1;
            }
        }
        int ans = 0;
        ans = Math.max(ans, rec(n, 1, points));
        ans = Math.max(ans, rec(n, 2, points));
        ans = Math.max(ans, rec(n, 3, points));

        return ans;
    }
}

Solution

The first solution uses extra local variables k and cur, which are on the stack for each step of the recursive function. execution context allocation. This means your stack will grow a bit faster than the second solution.

Yes, each locale has its own limitations for managing its stack. They also usually allow changing the maximum size of the stack. See for Java and for C .

Note that you can also avoid the if block and handle all three cases at once:

int mx = Math.max(rec(day - 1, prev % 3 + 1, points), 
                  rec(day - 1, (prev + 1) % 3 + 1, points));

You can save more stack space if you store points as a static variable (just like dp) and don't pass it as an argument to the recursive function.

Stack used to get recursive function results Since there may be large input numbers n in the test, the allocation to int cur will overflow.

https://www.php.cn/link/efc9ea3e0c2ed2c2481fe1252019266e

The above is the detailed content of I'm getting a stackoverflow error when I use a for loop, but if the same thing is done using an if block, it doesn't produce the error. For more information, please follow other related articles on the PHP Chinese website!