Recursion going in infinite loop in Java for 2D array-CodePudding

I have a 2D array in JAVA and I want to mark all the 1s in the array as 2s. 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
    }
}

CodePudding user response：

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

CodePudding user response：

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
}

CodePudding user response：

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.