Getting stackoverflow error when I use for loop but if the same thing is done using an if block no error is produced

Question

I was solving a DSA problem
the language I'm using 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 dont know what the test case is as it doesnt display the test case) I run into a stackoverflow error so I just replaced the for loop with a few if statements and it fixed it, I want to know why I ran into the error in first place

also the same solution(with for loop) in c++ gives no error, does stack space work differently for java and c++?

it just doesnt make sense the amount of function calls made remains the same in both the approaches but one gives a stackoverflow error. so there is no way the the number of calls is more than the stack space, If someone could figure this out for me it'd be great

Here is the code with the 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 if blocks:

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;
    }
}

Answer 1

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

does stack space work differently for java and c++?

Yes, each language environment manage their stacks with their own limits. They often allow to change the maximum size of the stack too. See for Java and for C++.

Note that you can also avoid the if blocks and deal with the three cases in one go:

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

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