CODEWITHSUNDEEP
javarecursionmultidimensional-array
RONOLULU
RONOLULU

Reputation: 1097

Calculating max value of paths inside of 2D int array using recursion

I was given an assignment and we are only allowed to use recursive methods to solve different problems given to us. I'm fairly new to programming and I'm having a hard time wrapping my head around it.

One of the objectives in the assignment is to calculate the max value of all possible paths in any given 2D integer array. Basically what this means is that when given a 2D int array, I need to use recursion to go through all different paths (abiding to the rules of only moving one element down or one element to the right at a time) in the array and return the value of the path with the highest sum value of elements in that path.

For example: (just a random example, could be any 2D int array with no particular order or size)

int[][] arr = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}};

the output should be: '48' (1 + 5 + 9 + 10 + 11 + 12)

This is what I have so far (but I have a feeling I'm way off):

public static int maxVal(int[][] arr) {
    return maxVal(arr, 0, 0);
} // end of method

// Returns the value of the maximal path in the
// given 2D array, starting at location (i,j)
private static int maxVal(int[][] arr, int i, int j) {
    // terminates when reaches last element
    if ((i + 1) == arr.length && (j + 1) == arr[0].length) { 
        return 0;
    } else {
        // if the elemnt is at the last column
        if ((i + 1) == arr.length) { 
            return maxVal(arr, i, j) + arr[i][j - 1];
        // if element is at the last row
        } else if ((j + 1) == arr[0].length) { 
            return maxVal(arr, i, j) + arr[i - 1][j];
        } else {
            return maxVal(arr, i, j) + arr[i - 1][j - 1];
        }
    }
}

I keep getting a StackOverFlowError. Any suggestions would be very helpful.

Upvotes: 0

Views: 887

Answers (1)

Bahij.Mik
Bahij.Mik

Reputation: 1484

If you look closely, you will see that you are calling the same method over and over again return maxVal(arr, i, j), this will cause the SOF exception because there will be infi recursion calls since nothing is changing that will trigger the base cases.

You should instead return the current value added to the max value of the right/bottom.

private static int maxVal(int[][] arr, int i, int j)
    {
        if (i >= arr.length || i < 0 || j >= arr[i].length || j < 0) return 0;
        int right = maxVal(arr, i, j + 1);
        int bottom = maxVal(arr, i + 1, j);
        return arr[i][j] + Math.max(right, bottom);
    }

Try not to get lost in the recursion rabbit hole, instead set the correct base case which is once you reach an invalid i or j, you should just return 0 (end of current path)

if (i >= arr.length || i < 0 || j >= arr[i].length || j < 0) return 0;

if both indicies are valid, you will then have to recursively calculate the right and bottom values until it eventually reaches the end of the path (invalid indicies)

After that's done you will have two values, that are the result of the max sum of possible paths from your current right and current bottom, then you add your current value to the max value (right/bottom) and return it.

Upvotes: 2

Related Questions