Recursion going in infinite loop in Java for 2D array

user_2746466 0
Viewed 50

I am working on the infamous Land (1s) and Water (0s) problem where I have to see top, right, down and left node of every 1s. I am using recursion to perform this but somehow my code is going in infinite loop. In following code why my traverse function makes i and j as 0 again and again and goes in infinite loop.

package com.practice;

public class TwoDArray {
    public static void main(String[] args) {
        int[][] iArray = {       {1, 1, 0, 1},
                                 {1, 0, 1, 0},
                                 {0, 0, 1, 0},
                                 {1, 1, 0, 0} };

        int rowSize = iArray.length;
        int colSize = iArray[0].length;


        for(int i=0; i< iArray.length; i++){
            for(int j=0; j< iArray[i].length; i++){
                if(iArray[i][j] == 1){
                    traverse(i,j,iArray,rowSize,colSize);
                }
            }
        }
    }

    public static void traverse(int i, int j, int[][] iArray,int rowSize, int colSize){

        if(i < 0 || j < 0 || i >= rowSize || j >= colSize){
            return;
        }

        if(iArray[i][j] == 1){
            iArray[i][j] = 2;
        }

        traverse(i , j - 1, iArray,rowSize,colSize); //LEFT
        traverse(i - 1, j, iArray,rowSize,colSize); //UP
        traverse(i , j +1, iArray,rowSize,colSize);//RIGHT
        traverse(i + 1, j, iArray,rowSize,colSize);//DOWN
    }
}
recursion java
3 Answers

In your code nested for loop increments i, instead of j. If use of recursion is not some mandatory requirement I would suggest to go with much simpler approach:

for(int i=0; i< iArray.length; i++){
            for(int j=0; j< iArray[i].length; j++){
                if(iArray[i][j] == 1){
                    iArray[i][j] = 2;
                }
            }
        }
user_195161750

Your solutions breaks, because you don't keep track of where you already went. You go left and then right and then again left and so on. Same goes for up and down. The iteration in the main method is also very redundant, because even without the infinite recursion you would check every cell exponentially often.

You could go with Oleksandrs solution and iterate on every row and column.

An recursive solution would be starting at cell [0,0] and to only make a pass to the right and downwards stopping when surpassing the lowest row or when going past the most right column.

public static void traverse(int i, int j, int[][] iArray,int rowSize, int colSize){
    if(i >= rowSize || j >= colSize){
        return;
    }

    if(iArray[i][j] == 1){
        iArray[i][j] = 2;
    }

    traverse(i , j +1, iArray,rowSize,colSize);//RIGHT
    traverse(i + 1, j, iArray,rowSize,colSize);//DOWN
}
user_70829560

Don't think recursion is required in this case. You are already traversing all the elements with those nested loops.

    for(int i=0; i< iArray.length; i++){
        for(int j=0; j< iArray[i].length; i++){
            if(iArray[i][j] == 1){
                iArr[i][j] = 2;
            }
        }
    }
}

Should be sufficient.

user_181949180
Related