How to prevent infinite recursion in a non-destructive way?

Question

that's my first question here, so I'm apologizing in advance if I didn't data-mined well enough and duplicate the question.

So I'm trying to create some sort of a game where at some point you have a matrix like this:

 _ _ _ _ _ _ |_|_|h|h|h|h| |_|_|_|_|_|_| |_|#|#|#|_|_| |_|_|_|#|_|_| |_|h|_|_|_|_| |_|h|#|_|_|_|

And I need a method that checks if there are "elements" made up only by 'h'-es and if it finds one, to change all chars from 'h' to something else like 'd' for example so it becomes:

 _ _ _ _ _ _ |_|_|d|d|d|d| |_|_|_|_|_|_| |_|#|#|#|_|_| |_|_|_|#|_|_| |_|h|_|_|_|_| |_|h|#|_|_|_|

While it shouldn't change the other 'h'-es, that touch '#'-s I can either use for-cycles to run through the whole matrix, or start directly from the element, as I have the arr[y][x] coordinates. Either way, I'm using recursion to check the neighbors, but how do I prevent the method from stepping in back to the previous element and oscillate between them until... StackOverflow occurs? So far this is where I am:

public class matrixRec { public static void main(String[] args) { char[][] matrix = { {' ',' ',' ',' ',' ',' '}, {' ','h','h','h','h',' '}, {' ',' ',' ',' ',' ',' '}, {' ',' ',' ','#','#',' '}, {' ','h',' ',' ','#','#'}, {' ','h','#',' ',' ',' '} }; System.out.println(elementChange(matrix, 1, 2)); } static boolean elementChange(char[][] matrix, int y, int x){ if (matrix[y][x] == ' '){ return true; } else if (matrix[y][x] == '#'){ return false; } else if (matrix[y][x] == 'h'){ return (elementChange(matrix, y, x-1) && elementChange(matrix, y, x+1)); } else { return false; } } }

So is there a way I prevent infinite recursion, without changing the 'h'-es, until I am sure that they're all 'h'?

Read up on graph searching (try breadth-first). You need to keep track of visited cells, either with a list or a boolean matrix. — Connor Clark
– Connor Clark, Commented Dec 3, 2015 at 22:17
What's your terminating case? That you visit all n cells? Why not keep a counter that when evaluated true against your n celled matrix, terminate the recursion — andrewdleach
– andrewdleach, Commented Dec 3, 2015 at 22:19
you will not get infinite loop, you will get ArrayOutOfBoudsException. add some checks that you don't get out of the array's size, and this should be your terminate case — Nir Levy
– Nir Levy, Commented Dec 3, 2015 at 22:22
Thanks guys, I though of making and accessory boolean array just after I went to bed last night :) I'm gonna try it out now About the ArrayIndexOutOfBounds - the upper code is just an example, I have coordinates-validation in the actual code — Dan
– Dan, Commented Dec 4, 2015 at 5:35

Brenden Smith · Accepted Answer · 2016-03-14 17:39:51Z

Couple of things to do:

Create a boolean aray to check visited cells each time we check an area

public class matrixRec { public static void main(String[] args) { char[][] matrix = { {' ',' ',' ',' ',' ',' '}, {' ','h','h','h','h',' '}, {' ',' ',' ',' ',' ',' '}, {' ',' ',' ','#','#',' '}, {' ','h',' ',' ','#','#'}, {' ','h','#',' ',' ',' '} }; boolean visited[][] = new boolean[6][6] //boolean arrays default to false System.out.println(elementChange(matrix, 1, 2, visited)); } static boolean elementChange(char[][] matrix, int y, int x. boolean[][] visited){ if(visited[y][x]) return ((matrix[y][x] == ' ' || matrix[y][x] == 'h')? true: false); visited[y][x] = true; //We have visited this cell if (matrix[y][x] == ' '){ return true; } else if (matrix[y][x] == '#'){ return false; } else if (matrix[y][x] == 'h'){ return elementChange(matrix, y, x-1,visited) && elementChange(matrix, y, x+1,visited); } else { return false; } } }

Are we just checking up left and right? What about up and down?

public class matrixRec { public static void main(String[] args) { char[][] matrix = { {' ',' ',' ',' ',' ',' '}, {' ','h','h','h','h',' '}, {' ',' ',' ',' ',' ',' '}, {' ',' ',' ','#','#',' '}, {' ','h',' ',' ','#','#'}, {' ','h','#',' ',' ',' '} }; boolean visited[][] = new boolean[6][6] //boolean arrays default to false System.out.println(elementChange(matrix, 1, 2, visited)); } static boolean elementChange(char[][] matrix, int y, int x. boolean[][] visited){ if(visited[y][x]) return ((matrix[y][x] == ' ' || matrix[y][x] == 'h')? true: false); visited[y][x] = true; //We have visited this cell if (matrix[y][x] == ' '){ return true; } else if (matrix[y][x] == '#'){ return false; } else if (matrix[y][x] == 'h'){ return elementChange(matrix, y, x-1,visited) && elementChange(matrix, y, x+1,visited) && elementChange(matrix, y-1, x,visited) && elementChange(matrix, y+1, x,visited); } else { return false; } } }

Use a conditional to only change areas that we want to

public class matrixRec { public static void main(String[] args) { char[][] matrix = { {' ',' ',' ',' ',' ',' '}, {' ','h','h','h','h',' '}, {' ',' ',' ',' ',' ',' '}, {' ',' ',' ','#','#',' '}, {' ','h',' ',' ','#','#'}, {' ','h','#',' ',' ',' '} }; boolean visited[][] = new boolean[6][6] //boolean arrays default to false System.out.println(elementChange(matrix, 1, 2, visited)); } static boolean elementChange(char[][] matrix, int y, int x. boolean[][] visited){ if(visited[y][x]) return ((matrix[y][x] == ' ' || matrix[y][x] == 'h')? true: false); visited[y][x] = true; //We have visited this cell if (matrix[y][x] == ' '){ return true; } else if (matrix[y][x] == '#'){ return false; } else if (matrix[y][x] == 'h'){ if((elementChange(matrix, y, x-1,visited) && elementChange(matrix, y, x+1,visited) && elementChange(matrix, y-1, x,visited) && elementChange(matrix, y+1, x,visited)) matrix[y][x] = 'd'; //Will only change areas that were searched to not be next to a # } else { return false; } } }

For the future

This is an area of algorithms that takes a little bit of thought and planning. For future research/programs be sure to do some searching on flood fills, recursive backtracking, graph searching, and recursive maze solving.

Collectives™ on Stack Overflow

How to prevent infinite recursion in a non-destructive way?

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related