Recursion going in infinite loop in Java for 2D array

Question

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

your 'traverse' method moves on all places, you don't need your main loop to go on all places too — azro
– azro, Commented Jul 9, 2022 at 19:40

Oleksandr Myronets · Accepted Answer · 2022-07-09 19:49:19Z

3

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

answered Jul 9, 2022 at 19:49

Oleksandr Myronets

11010 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Valerij Dobler · Accepted Answer · 2022-07-09 19:54:40Z

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
}

P S · Accepted Answer · 2022-07-09 20:48:28Z

1

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.

answered Jul 9, 2022 at 20:48

P S

294 bronze badges

Collectives™ on Stack Overflow

Recursion going in infinite loop in Java for 2D array

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related